Задача №1. Задача комівояжера. Метод розгалужень і границь
Визначити найкоротший маршрут (довжину) в задачі комівояжера методом розгалужень і границь
Місто |
М1 |
М2 |
М3 |
М4 |
М1 |
|
3 |
5 |
2 |
М2 |
3 |
|
1 |
7 |
М3 |
5 |
1 |
|
8 |
М4 |
2 |
7 |
8 |
|
Рішення
Крок 1. Приведемо матрицю відстаней по строках:
Таблиця 1.1 |
Таблиця 1.2 |
Таблиця 1.3 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
М1
М2
М3
М4
М1
3
5
7
М2
3
1
2
М3
5
1
8
М4
7
2
8
|
М1
М2
М3
М4
Min
М1
3
5
7
3
М2
3
1
2
1
М3
5
1
8
1
М4
7
2
8
2
∑
7 |
М1
М2
М3
М4
М1
0
2
4
М2
2
0
1
М3
4
0
7
М4
5
0
6
|
Крок 2. Приведемо отриману матрицю відстаней по стовбцях:
Таблиця 1.4 |
Таблиця 1.5 |
Таблиця 1.6 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
М1
М2
М3
М4
М1
0
2
3
М2
0
0
0
М3
2
0
6
М4
3
0
6
|
Мінімально можлива довжина маршруту складає 7+3=10.
Крок 3. Визначимо «вагу» кожного нуля («вагою» нуля є сума мінімальних елементів стовпця і строки за виключенням його самого в яких стоїть нуль):
Таблиця 1.7 |
|||||||||||||||||||||||||
М1
М2
М3
М4
М1
02
2
3
М2
02
02
03
М3
2
02
6
М4
3
03
6
|
Крок
4. В якості розгалуження оберемо
переміщення, для яких «вага» нуля
найбільша, наприклад:
та
.
Для
забороняємо стан
і отримуємо:
Таблиця 1.8 |
||||||||||||||||
|
Крок 5. Повторимо кроки 1-4 для отриманої матриці відстаней:
Таблиця 1.9 |
Таблиця 1.10 |
Таблиця 1.11 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Таблиця 1.12 |
Таблиця 1.13 |
Таблиця 1.14 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
Тобто, перехід М4–М2 збільшує мінімально можливу довжину маршруту на 4+1=5. Загальна довжина маршруту після переходу складає 5+10=15.
Оцінка нулів
Таблиця 1.15 |
||||||||||||||||
|
В
якості розгалуження оберемо переміщення,
для яких «вага» нуля найбільша, наприклад:
та
.
Для
забороняємо стан
і отримуємо:
Таблиця 1.15 |
|||||||||
|
Т.я. отримана матриця відстаней нульова, то можна обрати міста, що залишилися, в будь-якій послідовності (М2–М3 та М3–М1). Таким чином, опорний маршрут складається з наступної послідовності міст:
М2–М3–М1–М4–М2
Довжина опорного маршруту складає:
∑di=1+5+7+2=15
Крок 6. Перевіримо варіанти, які входили в розгалуження.
6.1 Розгалуження
Т.я. після розгалуження довжина маршруту не збільшувалась, то альтернативне розгалуження , також не може дати нам більш короткий маршрут.
6.2 Розгалуження
Матриця відстаней в разі використання розгалуження прийме вигляд:
Таблиця 1.16 |
|||||||||||||||||||||||||
|
Приведемо отриману матрицю по строках:
Таблиця 1.17 |
Таблиця 1.18 |
Таблиця 1.19 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
Таким чином, мінімально можлива довжина маршруту при використанні розгалуження складає 10+3=13 < 15 (довжина опорного маршруту). Т.я. на цьому напрямку можливо отримати більш короткий маршрут, то повторимо кроки 3-4. Оцінимо «вагу» нулів:
Таблиця 1.20 |
|||||||||||||||||||||||||
|
В
якості розгалуження оберемо переміщення,
для яких «вага» нуля найбільша, наприклад:
та
.
Для
стан
вже заборонено. Отримуємо:
Таблиця 1.21 |
||||||||||||||||
|
Приведемо матрицю відстаней по стовпцях (вочевидь, по строках мінімальні елементи в кожній строки дорівнюють нулю).
Таблиця 1.22 |
|
Таблиця 1.23 |
|
Таблиця 1.24 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
Таким чином, розгалуження збільшує мінімально можливий маршрут на 2, а його довжина становить 13+2=15 = 15 (довжина опорного маршруту). Розглядати далі не має сенсу, т.я. довжина маршруту вже не може бути менше довжини опорного.
Залишилось розглянути останнє розгалуження на попередньому кроці:
за
умови
.
Матриця відстаней прийме вигляд:
Таблиця 1.25 |
|||||||||||||||||||||||||
|
Приведемо отриману матрицю по стовпцях:
Таблиця 1.26 |
Таблиця 1.27 |
Таблиця 1.28 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
Розгалуження за умови збільшує мінімально можливий маршрут на 3. Довжина мінімально можливого маршруту становить: 13+3=16 > 15 (довжина опорного маршруту).
Таким чином мінімальна довжина маршруту відповідає опорному маршруту і дорівнює 15 (див. рис. 2).
Рисунок 2 – Граф пошуку мінімальної довжини маршруту
Відповідь: 15.
.