4551
правка
Евклидова задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 14:37, 23 января 2014
, 23 января 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 55: | Строка 55: | ||
'''Теорема 5 (Рао и Смит [15]). Существует детерминированный алгоритм, вычисляющий | '''Теорема 5 (Рао и Смит [15]). Существует детерминированный алгоритм, вычисляющий (1 + 1/c)-аппроксимацию оптимальной траектории движения коммивояжера за время <math>O(2^{(cd)^{O(d)}} n + (cd)^{O(d)} n log \; n)</math>.''' | ||
Также существует рандомизированный алгоритм Монте-Карло, который достигает успеха с вероятностью не менее 1/2, вычисляя | '''Также существует рандомизированный алгоритм Монте-Карло, который достигает успеха с вероятностью не менее 1/2, вычисляя (1 + 1/c)-аппроксимацию для оптимального пути коммивояжера за ожидаемое время <math>(c \sqrt{d})^{O(d(c \sqrt{d})^{d-1})} n + O(d \; n \; log \; n)</math>.''' | ||
Для отдельного, наиболее интересного случая, при d = 2, Рао и Смит продемонстрировали следующий результат. | Для отдельного, наиболее интересного случая, при d = 2, Рао и Смит продемонстрировали следующий результат. | ||
Существует рандомизированный алгоритм Монте-Карло, который не достигает успеха с вероятностью менее 1/2, вычисляя (1 + 1/c)-аппроксимацию для оптимального пути коммивояжера за ожидаемое время O(n | '''Теорема 6 (Рао и Смит [15]). Существует рандомизированный алгоритм, который вычисляет (1 + 1/c)-аппроксимацию для оптимального пути коммивояжера за время <math>O(n 2^{c^{O(1)}} + c^{O(1)} n \; log \; n)</math>.''' | ||
''' | |||
Существует рандомизированный алгоритм Монте-Карло, который не достигает успеха с вероятностью менее 1/2, вычисляя (1 + 1/c)-аппроксимацию для оптимального пути коммивояжера за ожидаемое время <math>O(n 2^{c^{O(1)}} + n \; log \; n)</math>.''' | |||
== Применение == | == Применение == | ||