di,j+dj,k>di,k.
di,j+dj,k>di,k. Рассмотрим идею алгоритма.
Шаг1. Строится каркас минимального веса (алгоритмы Прима или Краскала).
Примечание. Это не есть первое приближение, как в предыдущем алгоритме.
Шаг 2. Путем дублирования каждого ребра каркас преобразуется в эйлеров граф.
Шаг 3. Находим в построенном графе эйлеров цикл.
Шаг 4. Эйлеров цикл преобразуем в гамильтонов цикл (или маршрут коммивояжера). Метод преобразования: последовательность вершин эйлерова цикла сокращается так, чтобы каждая вершина графа в получившемся цикле встречалась ровно один раз.
Шаг 5. Закончить работу алгоритма. Получено приближенное решение задачи коммивояжера.
Покажем , что стоимость приближенного решение CostAp не превосходит удвоенной стоимости оптимального решения CostBet. Пусть стоимость каркаса - CostFr. Тогда CostFr<CostBet, так как при удалении из оптимального пути коммивояжера ребра получаем каркас с весом не большим, чем CostAp. Из правила построения эйлерова графа получаем, что вес построенного эйлерова
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
