4551
правка
Нахождение ближайшей подстроки: различия между версиями
Перейти к навигации
Перейти к поиску
м
Нахождение ближайшей подстроки (посмотреть исходный код)
Версия от 22:54, 11 января 2020
, 11 января 2020→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 22: | Строка 22: | ||
'''Теорема 1 [4, 5]. Задача CLOSEST SUBSTRING является NP-полной и остается таковой в специальном случае CLOSEST STRING, в котором искомая строка s должна иметь ту же длину, что и исходные строки. Задача CLOSEST STRING является NP-полной даже в случае ограничения | '''Теорема 1 [4, 5]. Задача CLOSEST SUBSTRING является NP-полной и остается таковой в специальном случае CLOSEST STRING, в котором искомая строка s должна иметь ту же длину, что и исходные строки. Задача CLOSEST STRING является NP-полной даже в случае ограничения бинарным алфавитом.''' | ||
| Строка 30: | Строка 30: | ||
В рандомизированной версии упомянутая в теореме 2 схема PTAS с высокой вероятностью находит решение с расстоянием Хэмминга <math>(1 + \epsilon)d_{opt}</math> для оптимального значения <math>d_{opt}</math> за время <math>(k^2 m)^{O(log|\Sigma| / \epsilon^4)}</math>. | В рандомизированной версии упомянутая в теореме 2 схема PTAS с высокой вероятностью находит решение с расстоянием Хэмминга <math>(1 + \epsilon)d_{opt}</math> для оптимального значения <math>d_{opt}</math> за время <math>(k^2 m)^{O(log|\Sigma| / \epsilon^4)}</math>. Эту рандомизированную версию PTAS можно дерандомизировать с увеличением накладных расходов. Прямолинейная и эффективная аппроксимация задачи CLOSEST STRING с коэффициентом 2 достигается путем проверки всех подстрок одной из входных строк, имеющих длину L. | ||