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