Методы решения задачи коммивояжера

1. метод ветвей и границ (алгоритм Литтла или исключения подциклов). Пример решения методом ветвей и границ;

2. венгерский метод. Пример решения венгерским методом.

ПРИМЕР. В качестве начального маршрута выбирается любой, например, X₀ = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1). Оценка для этого маршрута равна F(X₀) = 43 + 65 + 73 + 22 + 8 + 80 = 291. Для определения нижней границы множества используют операцию редукции, для чего в каждой строке матрицы D находят минимальный элемент: d_i = min(j) d_ij

Затем вычитают d_i из элементов рассматриваемой строки. Поэтому во вновь полученной матрице в каждой строке будет как минимум один ноль.

Такую же операцию редукции проводят по столбцам: d_j = min(i) d_ij

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины d_i и d_jназываются константами приведения.

Сумма констант приведения определяет нижнюю границу H = ∑d_i + ∑d_j = 9+52+13+17+8+10+0+20+0+5+0+0 = 134. Элементы матрицы d_ij соответствуют расстоянию от пункта i до пункта j. Длина маршрута определяется выражением: F(M_k) = ∑d_ij. Причем каждая строка и столбец входят в маршрут только один раз с элементом d_ij.

Затем в ходе последующих итераций, определяется ребро ветвлений. Все множество маршрутов относительно этого ребра разбивается на два подмножества (i,j) и (i*,j*).