4551
правка
Метрическая задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Метрическая задача коммивояжера (посмотреть исходный код)
Версия от 17:25, 24 августа 2016
, 24 августа 2016→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 82: | Строка 82: | ||
== Применение == | == Применение == | ||
Экспериментальный анализ показывает, что алгоритм Кристофидеса сам отклоняется от оптимального обхода на величину от 10 до 15% [ ]. Однако он может служить хорошей отправной точкой для других эвристик обхода – таких как эвристика Лина-Кернигана. | Экспериментальный анализ показывает, что алгоритм Кристофидеса сам отклоняется от оптимального обхода на величину от 10 до 15% [3]. Однако он может служить хорошей отправной точкой для других эвристик обхода – таких как эвристика Лина-Кернигана. | ||
[[Файл:M_TSP.png]] | |||
Рисунок 1. Пример для алгоритма Кристофидеса. В графе 2n + 1 вершин. Сплошные ребра имеют вес 1, пунктирные – вес <math>1 + \epsilon \;</math>. | |||
== Открытые вопросы == | == Открытые вопросы == | ||