Рішення задачі комівояжера методом гілок і меж
ВизначенняГрафом
Маршрутом в графі
Постановка завдання
Комівояжер повинен об'їздити n міст. Для того щоб скоротити витрати, він хоче побудувати такий маршрут, щоб об'їздити всі міста точно по одному разу і повернутися у вихідний з мінімумом витрат.У термінах теорії графів завдання можна сформулювати наступним чином. Визнач n вершин і матриця {c ij}, де c ij ≥ 0 - довжина (або ціна) дуги (i, j),
Рішення завдання
Основна ідея методу гілок і меж полягає в тому, що спочатку будують нижню межу φ довжин безлічі маршрутів Z. Потім безліч маршрутів розбивається на дві підмножини таким чином, щоб перше підмножинаПорівнюючи нижні межі φ (
Потім одна з підмножин
Якщо ж такий знайдеться, то аналіз обірваних гілок триває щодо нового значення довжини маршруту. Його називають другим рекордом. Процес рішення закінчується, коли будуть проаналізовані всі підмножини.
Для практичної реалізації методу гілок і меж стосовно до задачі комівояжера вкажемо прийом визначення нижніх меж підмножин і розбиття множини маршрутів на підмножини (розгалуження).
Для того щоб знайти нижню межу скористаємося наступним міркуванням: якщо до елементів будь-якого ряду матриці задачі комівояжера (рядку або стовпцю) додати або відняти від них деяке число, то від цього оптимальність плану не зміниться. Довжина ж будь-якого маршрутом комівояжера зміниться на цю величину.
Віднімемо з кожного рядка число, рівне мінімального елементу цього рядка. Віднімемо з кожного стовпця число, рівне мінімального елементу цього стовпця. Отримана матриця називається наведеної по рядках і стовпцях. Сума всіх вичтенних чисел називається константою приведення.
Константу приведення слід вибирати в якості нижньої межі довжини маршрутів.
Розбиття множини маршрутів на підмножини
Для виділення претендентів на включення в безліч дуг, за якими проводиться розгалуження, розглянемо у наведеній матриці всі елементи, рівні нулю. Знайдемо ступеня Θ ij нульових елементів цієї матриці. Ступінь нульового елемента Θ ij дорівнює сумі мінімального елемента в рядку i і мінімального елемента в стовпці j (при виборі цих мінімумів c ij - Не враховується). З найбільшою ймовірністю шуканого маршрутом належать дуги з максимальним ступенем нуля.
Для отримання платіжної матриці маршрутів, що включає дугу (i, j) викреслюємо в матриці рядок i і стовпець j, а щоб не допустити утворення циклу в маршруті, замінюємо елемент, який замикає поточну ланцюжок на нескінченність.
Безліч маршрутів, що не включають дугу (i, j) отримуємо шляхом заміни елемента c ij на нескінченність.
Приклад розв'язання задачі комівояжера методом гілок і меж
Комівояжер повинен об'їздити 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 1 = 15, r 2 = 1, r 3 = 0, r 4 = 16, r 5 = 5, r 6 = 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 | ∞ |
Після їх вирахування за стовпцями отримаємо наведену матрицю:
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 | ∞ |
Для виділення претендентів на включення в безліч дуг, за якими проводиться розгалуження, знайдемо ступеня Θ ij нульових елементів цієї матриці (суми мінімумів по рядку і стовпцю). Θ 14 = 10 + 0,
Θ 24 = 1 + 0, Θ 36 = 5 +0, Θ 41 = 0 + 1, Θ 42 = 0 + 0, Θ 56 = 2 + 0, Θ 62 = 0 + 0,
Θ 63 = 0 + 9, Θ 65 = 0 + 2. Найбільший ступінь Θ 14 = 10. Галуження проводимо по дузі (1, 4).
Нижня межа для безлічі
У матриці, відповідної
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 | ∞ |
У матриці, відповідної
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 | ∞ |
φ (
Рис. 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 | ∞ |
У матриці для
2 | 3 | 5 | 6 | |
3 | 13 | ∞ | 5 | 0 |
4 | ∞ | 9 | 2 | 2 |
5 | 41 | 22 | ∞ | 0 |
6 | 0 | 0 | 0 | ∞ |
Нижня межа для
Рис. 2 Галуження на другому кроці
Наведена платіжна матриця для
2 | 3 | 5 | 6 | |
3 | 13 | ∞ | 5 | 0 |
4 | ∞ | 7 | 0 | 0 |
5 | 41 | 22 | ∞ | 0 |
6 | 0 | 0 | 0 | ∞ |
Нижня межа для
2 | 3 | 5 | |
3 | 13 | ∞ | 5 |
4 | ∞ | 7 | 0 |
6 | 0 | 0 | ∞ |
Рис. 3 Галуження на третьому кроці
Наведена платіжна матриця для
2 | 3 | 5 | |
3 | 8 | ∞ | 0 |
4 | ∞ | 7 | 0 |
6 | 0 | 0 | ∞ |
Нижня межа для
2 | 3 | |
4 | ∞ | 7 |
6 | 0 | ∞ |
2 | 3 | |
4 | ∞ | 0 |
6 | 0 | ∞ |
SHAPE \ * MERGEFORMAT
(3,5) |
55 |
(5, 6) |
63 |
62 |
(3, 5) |
Рис. 4 Галуження на четвертому кроці
SHAPE \ * MERGEFORMAT
62 +0 +0 = 62 |
63 |
67 |
(1, 4) |
64 |
72 |
(5, 6) |
50 |
(2, 1) |
55 |
(5, 6) |
(3, 5) |
62 |
(3, 5) |
47 |
Z |
48 |
(1,4) |
(2, 1) |
(4, 3) (6, 2) |
Рис. 5 Дерево розгалуження з оцінками
Отриманий маршрутом комівояжера z 0 = (1, 4, 3, 5, 6, 2, 1) або (ADCEFBA).