Евклидова задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 64: | Строка 64: | ||
'''Теорема 6 (Рао и Смит [15]). Существует | '''Теорема 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>.''' | '''Существует рандомизированный алгоритм Монте-Карло, который не достигает успеха с вероятностью менее 1/2, вычисляя (1 + 1/c)-аппроксимацию для оптимальной траектории движения коммивояжера за ожидаемое время <math>O(n 2^{c^{O(1)}} + n \; log \; n)</math>.''' | ||