4551
правка
Задача коммивояжера с несколькими внутренними точками: различия между версиями
Перейти к навигации
Перейти к поиску
м
Задача коммивояжера с несколькими внутренними точками (посмотреть исходный код)
Версия от 11:02, 25 мая 2018
, 25 мая 2018→Применение
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 60: | Строка 60: | ||
Метод, разработанный Кнауэром и Спиллнером [12], можно применить и к задаче коммивояжера. Согласно их результату, наилучшая известная на данный момент временная сложность алгоритма для TSP составляет | Метод, разработанный Кнауэром и Спиллнером [12], можно применить и к задаче коммивояжера. Согласно их результату, наилучшая известная на данный момент временная сложность алгоритма для TSP составляет <math>2^{O(\sqrt{k} \; log \; k)} poly(n).</math> | ||
== Открытые вопросы == | == Открытые вопросы == | ||