Решение задачи коммивояжера методом ветвей и границ

Задача коммивояжёра заключается в разовом посещение всех городов по минимальному пути (маршруту) и возвращение в искомый город.

Рассмотрим пример решения задачи коммивояжёра методом ветвей и границ

пример

Первая итерация 

Найдём минимальные значения по строкам di

Задача коммивояжёра первая итерация

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

редукцию по строкам

Найдём минимальные значения по столбцам dj

Задача коммивояжёра минимальное по строкам

Аналогично производим редукцию по столбцам.

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

В получившейся матрице таблице находим нулевые значения

таблица

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

оценка значений таблица

Выберем значения в таблице с максимальной оценкой

таблица максимальная оценка

Сократим матрицу потерь за счёт исключения строки и столбца с наибольшей оценкой в нашем случае 5→3, так как это оптимальный путь, которые соответствует как городу отправления, так и городу назначения, при этом, расстоянии равно нулю.

Получаем новую матрицу потерь

матрица потерь

В третьей строке необходимо вместо нуля (минимального значения) поставить ∞, чтобы отсечь посещённые города.

Задача коммивояжёра матрица потерь

Вторая итерация решения задачи коммивояжера методом ветвей и границ, здесь всё аналогично, как и впервой итерации, проделываем те же самые операции

вторая итерация метод ветвей и границ

задача коммивояжера метод ветвей и границ вторая итерация

Максимальная оценка нулевого значения находится в 4 строке и 5 столбце, поэтому их сокращаем. Получаем путь 50 ед. и 4→5. Матрица потерь примет вид

матрица потерь вторая итерация

Ставим в ячейке знак ∞ на посещённые города. В нашем случае обратных путей к посещённым городам нет, поэтому в ячейке не ставим знак ∞ и матрицу оставляем без изменений.

матрица потерь вторая итерация

Третья итерация решения задачи коммивояжера

метод ветвей и границ коммивояжер третья итерация

решение задачи коммивояжера методом ветвей и границ третья итерация

Максимальная оценка нулевого значения находится в 1 строке и 2 столбце. Получаем путь 100 ед. и 1→2.

Получим матрицу потерь 2 на 2

матрица

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

Города 1 4
2 50
3 0 0

Четвертая итерация задачи коммивояжера методом ветвей и границ

Города 1 4 di
2 50 50
3 0 0 0
Города 1 4 di
2 0 50
3 0 0 0
Города 1 4
2 0
3 0 0
dj 0 0
Города 1 4
2 0
3 0 0
dj 0 0
Города 1 4
2 0()
3 0() 0(0)
Города 1 4
2 0()
3 0() 0(0)

Сокращаем с максимальной оценкой нулевого значения — это строка 3 и столбец 1 и получаем примитивную матрицу, в которой отсутствует обратный путь. В нашем случае оптимальный путь равен 50 ед. и 3→1.

Города 4
2 0

Эта матрица говорит о том, что город 2 и город 4 не замкнуты, длина пути равна 50 ед.

Таким образом, мы решили сложную задачу коммивояжёра методом ветвей и границ и нашли кратчайший путь, который равен

1→2→4→5→3→1

и длина его равна 250.

См. также

Решение данной задачи коммивояжёра в Excel

Leave a Reply

Ваш e-mail не будет опубликован.