4551
правка
Евклидова задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 14:56, 23 января 2014
, 23 января 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 48: | Строка 48: | ||
'''Теорема 4 (Арора [1]). Для | '''Теорема 4 (Арора [1]). Для любого константного значения d евклидова задача коммивояжера на <math>\mathbb{R} ^d</math> имеет PTAS.''' | ||
Для каждого фиксированного значения 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>. | Для каждого фиксированного значения 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>. | ||