Евклидова задача коммивояжера: различия между версиями

Евклидова задача коммивояжера (посмотреть исходный код)

Нет изменений в размере , 23 января 2014

4430

правок

@@ Строка 64: / Строка 64: @@
 '''Теорема 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>.'''
 == Применение ==