Задание № 2. Задача о коммивояжере. Метод ветвей и границ
Расстояния между пунктами заданы матрицей:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
С = |
1 |
∞ |
1 |
5 |
4 |
1 |
3 |
2 |
5 |
∞ |
1 |
6 |
7 |
2 | |
3 |
6 |
2 |
∞ |
3 |
4 |
1 | |
4 |
1 |
5 |
4 |
∞ |
6 |
7 | |
5 |
3 |
6 |
1 |
1 |
∞ |
4 | |
6 |
7 |
3 |
6 |
5 |
1 |
∞ |
Решение задачи о коммивояжере методом ветвей и границ начинается с приведения матрицы (вычитания из каждой строки (столбца) матрицы C минимального элемента этой строки (столбца).
Произведем приведение матрицы Cпо строкам:
hν=min(i)hνi
|
|
1 |
2 |
3 |
4 |
5 |
6 |
hν |
С’= |
1 |
∞ |
1 |
5 |
4 |
1 |
3 |
1 |
2 |
5 |
∞ |
1 |
6 |
7 |
2 |
1 | |
3 |
6 |
2 |
∞ |
3 |
4 |
1 |
1 | |
4 |
1 |
5 |
4 |
∞ |
6 |
7 |
1 | |
5 |
3 |
6 |
1 |
1 |
∞ |
4 |
1 | |
6 |
7 |
3 |
6 |
5 |
1 |
∞ |
1 |
Произведем приведение матрицы Cпо столбцам:
gi= min(υ)gνi
|
|
1 |
2 |
3 |
4 |
5 |
6 |
С’= |
1 |
∞ |
0 |
4 |
3 |
0 |
2 |
2 |
4 |
∞ |
0 |
5 |
6 |
1 | |
3 |
5 |
1 |
∞ |
2 |
3 |
0 | |
4 |
0 |
4 |
3 |
∞ |
5 |
6 | |
5 |
2 |
5 |
0 |
0 |
∞ |
3 | |
6 |
6 |
2 |
5 |
4 |
0 |
∞ | |
|
gi |
0 |
0 |
0 |
0 |
0 |
0 |
В итоге получаем полностью приведенную (редуцированную) матрицу:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
hν |
С0= |
1 |
∞ |
0 |
4 |
3 |
0 |
2 |
1 |
2 |
4 |
∞ |
0 |
5 |
6 |
1 |
1 | |
3 |
5 |
1 |
∞ |
2 |
3 |
0 |
1 | |
4 |
0 |
4 |
3 |
∞ |
5 |
6 |
1 | |
5 |
2 |
5 |
0 |
0 |
∞ |
3 |
1 | |
6 |
6 |
2 |
5 |
4 |
0 |
∞ |
1 | |
|
gi |
0 |
0 |
0 |
0 |
0 |
0 |
|
Величины hνиgiназываютсяконстантами приведения.
Нижняя граница цикла: d0=1+1+1+1+1+1+0+0+0+0+0+0 = 6
().
Шаг №1.
Определяем ребро ветвленияи разобьем все множество допустимых значенийQ0относительно этого ребра на два непересекающихся подмножества () и (), т.е., где
В приведенной матрице исследуем все нулевые переходы.
|
|
1 |
2 |
3 |
4 |
5 |
6 |
αν |
C0 = |
1 |
∞ |
0(1) |
4 |
3 |
0(0) |
2 |
0 |
2 |
4 |
∞ |
0(1) |
5 |
6 |
1 |
1 | |
3 |
5 |
1 |
∞ |
2 |
3 |
0(2) |
1 | |
4 |
0(5) |
4 |
3 |
∞ |
5 |
6 |
3 | |
5 |
2 |
5 |
0(0) |
0(2) |
∞ |
3 |
0 | |
6 |
6 |
2 |
5 |
4 |
0(2) |
∞ |
2 | |
|
βi |
2 |
1 |
0 |
2 |
0 |
1 |
|
Наибольшая сумма констант приведения равна
υ41= α4+β1=3+2=5, следовательно,
множество разбивается на два подмножества и.
Оценка длины цикла: .
Исключение ребра (4,1) проводим путем замены элемента υ41= 0 на ∞, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (), в результате получим редуцированную матрицу.
|
|
1 |
2 |
3 |
4 |
5 |
6 |
αν |
С0' = |
1 |
∞ |
0 |
4 |
3 |
0 |
2 |
0 |
2 |
4 |
∞ |
0 |
5 |
6 |
1 |
0 | |
3 |
5 |
1 |
∞ |
2 |
3 |
0 |
0 | |
4 |
∞ |
4 |
3 |
∞ |
5 |
6 |
3 | |
5 |
2 |
5 |
0 |
0 |
∞ |
3 |
0 | |
6 |
6 |
2 |
5 |
4 |
0 |
∞ |
0 | |
|
βi |
2 |
0 |
0 |
0 |
0 |
0 |
|
Включение ребра (4,1) проводится путем исключения всех элементов 4-ой строки и 1-го столбца, в которой элемент υ14заменяем на ∞, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (5x5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
|
2 |
3 |
4 |
5 |
6 |
hν |
|
1 |
0 |
4 |
∞ |
0 |
2 |
0 |
|
2 |
∞ |
0 |
5 |
6 |
1 |
0 |
C1= |
3 |
1 |
∞ |
2 |
3 |
0 |
0 |
|
5 |
5 |
0 |
0 |
∞ |
3 |
0 |
|
6 |
2 |
5 |
4 |
0 |
∞ |
0 |
|
gi |
0 |
0 |
0 |
0 |
0 |
|
d1=0
Шаг №2.
Определяем ребро ветвленияи разобьем все множество допустимых значенийQ1относительно этого ребра на два непересекающихся подмножества.
В приведенной матрице исследуем все нулевые переходы.
|
|
2 |
3 |
4 |
5 |
6 |
αν |
|
1 |
0(1) |
4 |
∞ |
0(0) |
2 |
0 |
|
2 |
∞ |
0(1) |
5 |
6 |
1 |
1 |
C1= |
3 |
1 |
∞ |
2 |
3 |
0(2) |
1 |
|
5 |
5 |
0(0) |
0(2) |
∞ |
3 |
0 |
|
6 |
2 |
5 |
4 |
0(2) |
∞ |
2 |
|
βi |
1 |
0 |
2 |
0 |
1 |
|
Наибольшая сумма констант приведения равна
υ36=1+1=2, следовательно,
множество разбивается на два подмножества и.
Оценка длины цикла: .
Оценка на перспективном множестве:
В результате получим другую сокращенную матрицу (4x4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
|
2 |
3 |
4 |
5 |
hν |
C2 = |
1 |
0 |
4 |
∞ |
0 |
0 |
2 |
∞ |
0 |
5 |
6 |
0 | |
5 |
5 |
0 |
0 |
∞ |
0 | |
6 |
2 |
∞ |
4 |
0 |
0 | |
|
gi |
0 |
0 |
0 |
0 |
|
d2=0
Шаг №3.
Определяем ребро ветвленияи разобьем все множество допустимых значенийQ2относительно этого ребра на два непересекающихся подмножества.
В приведенной матрице исследуем все нулевые переходы.
|
|
2 |
3 |
4 |
5 |
αν |
C2 = |
1 |
0(2) |
4 |
M |
0(0) |
4 |
2 |
M |
0(5) |
5 |
6 |
0 | |
5 |
5 |
0(0) |
0(4) |
M |
0 | |
6 |
2 |
M |
4 |
0(2) |
2 | |
|
βi |
0 |
2 |
4 |
0 |
|
Наибольшая сумма констант приведения равна
υ23=5+0=5, следовательно,
множество разбивается на два подмножества и.
Оценка длины цикла: .
Оценка на перспективном множестве:
В результате получим другую сокращенную матрицу (3x3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
|
1 |
3 |
6 |
hν |
|
1 |
0 |
∞ |
0 |
0 |
C3 = |
2 |
5 |
0 |
∞ |
0 |
|
4 |
2 |
4 |
0 |
0 |
|
gi |
0 |
0 |
0 |
|
d3=0
Шаг №4.
Определяем ребро ветвленияи разобьем все множество допустимых значенийQ3относительно этого ребра на два непересекающихся подмножества.
В приведенной матрице исследуем все нулевые переходы.
|
|
2 |
4 |
5 |
αν |
|
1 |
0(5) |
∞ |
0(0) |
0 |
C3 = |
5 |
5 |
0(9) |
∞ |
5 |
|
6 |
∞ |
4 |
0(4) |
4 |
|
βi |
5 |
4 |
0 |
|
Наибольшая сумма констант приведения равна
υ54=5+4=9, следовательно,
множество разбивается на два подмножества и.
Оценка длины цикла: .
Оценка на перспективном множестве:
В результате получим другую сокращенную матрицу (2x2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
|
2 |
5 |
hν |
C4 = |
1 |
0 |
0 |
0 |
6 |
∞ |
0 |
0 | |
|
gi |
0 |
0 |
|
d4=0
В соответствии с этой матрицей включаем в маршрут и.
Ответ: l* =C41+C36+C23+C54+C12+C65=1+1+1+1+1+1=6.
Дерево решения имеет следующий вид: