0

Дана строка $%s$% в алфавите $%\Sigma_1$% и строка $%t$% в алфавите $%\Sigma_2$%, требуется найти инъективную функцию $%f{:}\,\Sigma_1\rightarrow\Sigma_2$%, минимизирующую расстояние Левенштейна (edit distance) между строками $%f\!\left(s\right)$% и $%t$% (функция $%f$% задаёт гомоморфизм на строках). Размеры алфавитов не ограничены.

Что известно об алгоритмах (точных и приближённых) для этой задачи, о её сложности? Есть ли для неё хорошие известные эвристики?

задан 16 Фев '17 21:50

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

регистрация »

отмечен:

×304
×213
×106
×103
×84

задан
16 Фев '17 21:50

показан
924 раза

обновлен
16 Фев '17 21:50

Связанные вопросы

1 Построить алгоритм, проверяющий за время $%O(logn)$%, найдётся ли такое $%i$%, что $%A[i]=i$%

0 Построить алгоритм, который по $%A[1…n]$% выводит его мин. $%\sqrt{n}$% элементов по возрастанию

1 Как использовать алгоритм, чтобы за линейное время найти любую порядковую статистику массива?

1 Сдача минимальным количеством монет

0 Функции T1(n) и T2(n) заданы рекуррентными формулами

0 Нужны примеры NP-полных задач

0 Приведите полиномиальный алгоритм сведения задачи о существовании гамильтонова пути в НГ

-1 Докажите, что TIME(2^n) является собственным подмножеством TIME(2^2n)

0 Известно, что f(n) = O(n^2), g(n) = Ω(1), g(n) = O(n).

0 Постройте как можно более быстрый алгоритм

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru