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

Нижняя граница для множества

остается равной 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).