4446
правок
Задачи поиска ближайшей строки и ближайшей подстроки: различия между версиями
Материал из WEGA
Задачи поиска ближайшей строки и ближайшей подстроки (посмотреть исходный код)
Версия от 13:43, 27 октября 2019
, 27 октября 2019нет описания правки
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 26: | Строка 26: | ||
Теорема 1. Существует схема аппроксимации с полиномиальным временем выполнения для задачи поиска ближайшей строки. | '''Теорема 1. Существует схема аппроксимации с полиномиальным временем выполнения для задачи поиска ближайшей строки.''' | ||
Теорема 2. Существует схема аппроксимации с полиномиальным временем выполнения для задачи поиска ближайшей подстроки. | '''Теорема 2. Существует схема аппроксимации с полиномиальным временем выполнения для задачи поиска ближайшей подстроки.''' | ||
| Строка 48: | Строка 48: | ||
Теорема 3. Существует схема аппроксимации с полиномиальным временем выполнения для задачи выбора различающей подстроки. А именно, для | '''Теорема 3. Существует схема аппроксимации с полиномиальным временем выполнения для задачи выбора различающей подстроки. А именно, для любого константного значения <math>\epsilon > 0</math> алгоритм находит строку длины L, такую, что для каждого <math>s_i \in B</math> существует имеющая длину L подстрока <math>t_i</math> строки <math>s_i</math> с <math>d(t_i, s) \le (1 + \epsilon)d_b</math> и для каждой подстроки <math>u_i</math> длины L каждой строки <math>g_i \in G, d(u_i, s) \ge (1 — \epsilon) d_g</math>, если существует решение для исходной пары <math>(d_b \le d_g)</math>. Поскольку существует полиномиальное количество таких пар <math>(d_b, d_g)</math>, мы можем за полиномиальное время перебрать все возможности и найти наиболее подходящую аппроксимацию для соответствующей конкретной задачи.''' | ||
== Открытые вопросы == | == Открытые вопросы == | ||
