4551
правка
Евклидова задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 13:49, 23 января 2014
, 23 января 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
== Основные результаты == | == Основные результаты == | ||
Известно, что в графах общего вида задача коммивояжера является NP-полной; то же верно для евклидовой задачи коммивояжера [11], [14]. | Известно, что в графах общего вида задача коммивояжера является NP-полной; то же верно для евклидовой задачи коммивояжера ([11], [14]). | ||
| Строка 62: | Строка 62: | ||
Существует рандомизированный алгоритм Монте-Карло, который не достигает успеха с вероятностью менее 1/2, вычисляя (1 + 1/c)-аппроксимацию для оптимального пути коммивояжера за ожидаемое время O(n 2cO(1) + n log n). | Существует рандомизированный алгоритм Монте-Карло, который не достигает успеха с вероятностью менее 1/2, вычисляя (1 + 1/c)-аппроксимацию для оптимального пути коммивояжера за ожидаемое время O(n 2cO(1) + n log n). | ||
== Применение == | == Применение == | ||