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

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

72 байта добавлено , 23 января 2014

4551

правка

@@ Строка 57: / Строка 57: @@
 '''Теорема 5 (Рао и Смит [15]). Существует детерминированный алгоритм, вычисляющий <math>(1 + 1/c) \; </math>-аппроксимацию оптимальной траектории движения коммивояжера за время <math>O(2^{(cd)^{O(d)}} n + (cd)^{O(d)} n log \; n)</math>.'''
-Существует рандомизированный алгоритм Монте-Карло, который достигает успеха с вероятностью не менее 1/2, вычисляя (1 + 1/c)-аппроксимацию для оптимального пути коммивояжера за ожидаемое время {c\fd)°^c^d:) ) n + O(d n log n).
+Также существует рандомизированный алгоритм Монте-Карло, который достигает успеха с вероятностью не менее 1/2, вычисляя <math>(1 + 1/c) \; </math>-аппроксимацию для оптимального пути коммивояжера за ожидаемое время <math>(c \sqrt{d})^{O(d(c \sqrt{d})^{d-1})} n + O(d \; n \; log \; n)</math>.
 Для отдельного, наиболее интересного случая, при d = 2, Рао и Смит продемонстрировали следующий результат.