end; 2.10.3. Алгоритм
end;
2.10.3. Алгоритм Кристофидеса
Отличается от предыдущего логикой построения маршрута из каркаса минимального веса. Неравенство треугольника выполняется.
Шаг 1. Строится каркас минимального веса (алгоритм Прима или Краскала).
Шаг 2. На множестве вершин каркаса(обозначим их через V), имеющих нечетное число ребер каркаса, находится паросочетание минимального веса. Таких вершин в любом каркасе четное число. Метод поиска паросочетания - чередующиеся цепочки.
Шаг 3. Каркас преобразуется в эйлеров граф путем присоединения ребер, соответствующих найденному паросочетанию.
Шаг 4. В построенном графе находится эйлеров маршрут.
Шаг 5. Эйлеров маршрут преобразуется в маршрут коммивояжера:
Итак, данный метод отличается от предыдущего только шагами 2 и 3.
Все этапы реализуются за полиномиальное время. Известно[1], что для этого метода оценка приближенного метода имеет вид CostAp<1.5*CostBest и эта оценка является лучшей для приближенных полиномиальных алгоритмов решения задачи о
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
