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

 

Коммивояжер должен объездить 6городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город A. Затраты на перемещение между городами заданы следующей матрицей:

 

	A	B	C	D	E	F
A	∞	26	42	15	29	25
B	7	∞	16	1	30	25
C	20	13	∞	35	5	0
D	21	16	25	∞	18	18
E	12	46	27	48	∞	5
F	23	5	5	9	5	∞

Решение задачи

Для удобства изложения везде ниже в платежной матрице заменим имена городов (A, B, …, F) номерами соответствующих строк и столбцов (1, 2, …, 6).

Найдем нижнюю границу длин множества всех маршрутов. Вычтем из каждой строки число, равное минимальному элементу этой строки, далее вычтем из каждого столбца число, равное минимальному элементу этого столбца, и таким образом приведем матрицу по строкам и столбцам. Минимумы по строкам: r₁=15, r₂=1, r₃=0, r₄=16, r₅=5, r₆=5.

После их вычитания по строкам получим:

 

	1	2	3	4	5	6
1	∞	11	27	0	14	10
2	6	∞	15	0	29	24
3	20	13	∞	35	5	0
4	5	0	9	∞	2	2
5	7	41	22	43	∞	0
6	18	0	0	4	0	∞

 

Минимумы по столбцам: h₁=5, h₂=h₃=h₄=h₅=h₆.

После их вычитания по столбцам получим приведенную матрицу:

 

	1	2	3	4	5	6
1	∞	11	27	0	14	10
2	1	∞	15	0	29	24
3	15	13	∞	35	5	0
4	0	0	9	∞	2	2
5	2	41	22	43	∞	0
6	13	0	0	4	0	∞

 

Найдем нижнюю границу φ(Z) = 15+1+0+16+5+5+5 = 47.

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, найдем степени Θ_ij нулевых элементов этой матрицы (суммы минимумов по строке и столбцу). Θ₁₄ = 10 + 0,
Θ₂₄ = 1 + 0, Θ₃₆ = 5+0, Θ₄₁ = 0 + 1, Θ₄₂ = 0 + 0, Θ₅₆ = 2 + 0, Θ₆₂ = 0 + 0,
Θ₆₃ = 0 + 9, Θ₆₅ = 0 + 2. Наибольшая степень Θ₁₄ = 10. Ветвление проводим по дуге (1, 4).

Нижняя граница для множества  остается равной 47. Для всех маршрутов множества  из города A мы не перемещаемся в город D. В матрице это обозначается выставлением в ячейку (1, 4) знака ∞. В этом случае выход из города A добавляет к оценке нижней границы по крайней мере наименьший элемент первой строки. φ ( ) = 47 + 10.

В матрице, соответствующей  полагаем c₁₄= ∞.

 

	1	2	3	4	5	6
1	∞	11	27	∞	14	10
2	1	∞	15	0	29	24
3	15	13	∞	35	5	0
4	0	0	9	∞	2	2
5	2	41	22	43	∞	0
6	13	0	0	4	0	∞

 

После проведения процедуры приведения с r₁=10 получим новую нижнюю границу 57 + 10 = 67.

В матрице, соответствующей , вычеркиваем первую строку и четвертый столбец и положим c₄₁= ∞, чтобы предотвратить появления цикла 1→ 4 → 1. Получим новую платежную матрицу {c¹_ij}:

 

	1	2	3	5	6
2	1	∞	15	29	24
3	15	13	∞	5	0
4	∞	0	9	2	2
5	2	41	22	∞	0
6	13	0	0	0	∞

 

Для приведения надо вычесть минимум по первому столбцу: h₁=1. При этом нижняя граница станет равной 47+1 = 48. Сравнивая нижние границы
 φ ( ) = 67 и φ ( ) = 48 < 67 выделяем подмножество маршрутов , которое с большей вероятностью содержит маршрут минимальной длины.

 

Рис. 1 Ветвление на первом шаге

Приведенная платежная матрица для

	1	2	3	5	6
2	0	∞	15	29	24
3	14	13	∞	5	0
4	∞	0	9	2	2
5	1	41	22	∞	0
6	12	0	0	0	∞

 

Далее продолжаем процесс ветвления. Найдем степени Θ_ij нулевых элементов этой матрицы Θ₂₁ =16, Θ₃₆ = 5, Θ₄₂ = 2, Θ₅₆ = 2, Θ₆₂ = 0, Θ₆₃ =9, Θ₆₅ = 2. Наибольшая степень Θ₂₁. Затем множество  разбивается дуге (2, 1) на два новых  и .

В матрице для  вычеркиваем строку 2 и столбец 1. дуги (1, 4) и (2, 1) образуют связный путь (2, 1, 4), положим c₄₂= ∞, чтобы предотвратить появления цикла 2→1→ 4 → 2.

 

	2	3	5	6
3	13	∞	5	0
4	∞	9	2	2
5	41	22	∞	0
6	0	0	0	∞

 

Для приведения надо вычесть минимум по строке 4: r₄=2. При этом нижняя граница станет равной 48+2 = 50.

Нижняя граница для , полученная как на предыдущем шаге ветвления, равна 48 + 16 = 64. Сравнивая нижние границы φ ( ) = 64 и φ ( ) = 50 < 64 выбираем для дальнейшего разбиения подмножество маршрутов .

Рис. 2 Ветвление на втором шаге

 

Приведенная платежная матрица для

 

	2	3	5	6
3	13	∞	5	0
4	∞	7	0	0
5	41	22	∞	0
6	0	0	0	∞

 

Степени Θ_ij нулевых элементов этой матрицы Θ₃₆ = 5, Θ₄₅ = 0, Θ₅₆ = 22, Θ₆₂ = 13, Θ₆₃ =7, Θ₆₅ = 0. Наибольшая степень Θ_56. Затем множество  разбивается дуге (2, 1) на два новых  и .

Нижняя граница для  равна 50 + 22 = 72. В матрице для  вычеркиваем строку 5 и столбец 6 и полагаем c₆₅= ∞. Получим матрицу:

 

	2	3	5
3	13	∞	5
4	∞	7	0
6	0	0	∞

 

Для приведения надо вычесть минимум по строке 3: r₃=5. При этом нижняя граница станет равной 50+5 = 55. Выбираем для дальнейшего разбиения подмножество маршрутов .

 

Рис. 3 Ветвление на третьем шаге

 

Приведенная платежная матрица для

 

	2	3	5
3	8	∞	0
4	∞	7	0
6	0	0	∞

 

Степени Θ_ij нулевых элементов этой матрицы Θ₃₅ = 8, Θ₄₅ = 7, Θ₆₂ = 8, Θ₆₃ =7. Выбираем Θ₃₅ = 8. Разбиваем  на  и .

Нижняя граница для  равна 55 + 8 = 64. В матрице для  вычеркиваем строку 3 и столбец 5 и полагаем c₆₃= ∞. Получим

 

	2	3
4	∞	7
6	0	∞

 

Для приведения надо вычесть минимум по строке 4: r4=7. При этом нижняя граница станет равной 55+7 = 62. После приведения получим

 

	2	3
4	∞	0
6	0	∞

 

Из матрицы 2´2 получаем два перехода с нулевой длинной: (4, 3) и (6, 2).

Рис. 4 Ветвление на четвертом шаге

 

Рис. 5 Дерево ветвления с оценками

 

Полученный маршрутом коммивояжера z₀ = (1, 4, 3, 5, 6, 2, 1) или (A-D-C-E-F-B-A).