24. Задача коммивояжера, методы ее решений

Коммивояжер (бродячий торговец) должен объехать городов, побывав в каждом из них по одному разу, и вернуться обратно таким образом, чтобы суммарные затраты на передвижение были минимальными.

  Метод ветвей и границ.

1. Решить задачу о назначениях любым методом. Если при решении задачи получен один цикл, то он будет решением задачи коммивояжера. Закончить поиск. В противном случае запомнить значение оценки пути и перейти к п.2.

2. Выбрать решение задачи о назначении с минимальной стоимостью. Исключить один из элементов матрицы стоимостей, который находится на незамкнутом пути присвоением ему максимального в матрице значения. Вернуться к п.1.

 Метод ветвей и границ 2.

1. Решить задачу о назначениях венгерским методом. Если при решении задачи получен один цикл, он будет решением задачи коммивояжера. Закончить поиск. В противном случае перейти к п.2.

2. Склеить циклы в один. Вычислить текущее значение верхней оценки z. Перейти к шагу 3.

3. Ветвление вариантов. Строим дерево решений для новой матрицы, продолжая только те ветви которые могут давать меньшее значение верхней границы z''<z'. Начинаем с любой вершины. Около ребер указывает затраты на путь. Выбираем ветвь с наименьшей стоимостью, переходим на следующий уровень. Повторяем действия на следующем уровне. Поступаем так до тех пор, пока ветвь не будет достроена полностью. Подсчитываем стоимость выбранного пути и далее используем это число при анализе оставшихся ветвей. Если есть ветви, которые могут дать стоимость меньше основной, то продолжаем эти ветви указанным выше способом. Остальные ветви ограничиваем. Полученный путь будет оптимальным, а стоимость минимальной.