Рішення задачі комівояжера методом гілок і меж

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Рішення задачі комівояжера методом гілок і меж

Визначення
Графом називається непорожня скінченна множина, що складається з двох підмножин і . Перше підмножина (Вершини) складається з будь-якого безлічі елементів. Друге підмножина (Дуги) складається з упорядкованих пар елементів першого підмножини . Якщо вершини і такі, що , То це вершини суміжні.
Маршрутом в графі називається послідовність вершин не обов'язково попарно різних, де для будь-якого суміжно з . Маршрут називається ланцюгом, якщо всі його ребра попарно різні. Якщо то маршрут називається замкнутим. Замкнута ланцюг називається циклом.

Постановка завдання

Комівояжер повинен об'їздити n міст. Для того щоб скоротити витрати, він хоче побудувати такий маршрут, щоб об'їздити всі міста точно по одному разу і повернутися у вихідний з мінімумом витрат.
У термінах теорії графів завдання можна сформулювати наступним чином. Визнач n вершин і матриця {c ij}, де c ij ≥ 0 - довжина (або ціна) дуги (i, j), . Під маршрутом комівояжера z будемо розуміти цикл i 1, i 2, ..., i n, i 1 точок 1,2, ..., n. Таким чином, маршрут є набором дуг. Якщо між містами i і j немає переходу, то в матриці ставиться символ «нескінченність». Він обов'язково ставиться по діагоналі, що означає заборону на повернення в точку, через яку вже проходив маршрут комівояжера, довжина маршруту l (z) дорівнює сумі довжин дуг, що входять в маршрут. Нехай Z - множина всіх можливих маршрутів. Початкова вершина i 1 - фіксована. Потрібно знайти маршрут z 0 Î Z, такий, що l (z 0) = min l (z), z Î Z.

Рішення завдання

Основна ідея методу гілок і меж полягає в тому, що спочатку будують нижню межу φ довжин безлічі маршрутів Z. Потім безліч маршрутів розбивається на дві підмножини таким чином, щоб перше підмножина складалося з маршрутів, які містять деяку дугу (i, j), а інше підмножина не містило цієї дуги. Для кожного з підмножин визначаються нижні межі за тим же правилом, що і для початкового безлічі маршрутів. Отримані нижні межі підмножин і виявляються не менше нижньої межі множини всіх маршрутів, тобто φ (Z) ≤ φ ( ), Φ (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

Мінімуми по стовпцях: h 1 = 5, h 2 = h 3 = h 4 = h 5 = h 6.
Після їх вирахування за стовпцями отримаємо наведену матрицю:
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 нульових елементів цієї матриці (суми мінімумів по рядку і стовпцю). Θ 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).
Нижня межа для безлічі залишається рівною 47. Для всіх маршрутів безлічі   з міста A ми не подорожуємо у місто D. У матриці це позначається виставленням в клітинку (1, 4) знака ∞. У цьому випадку вихід з міста A додає до оцінки нижньої межі принаймні найменший елемент першого рядка. Φ ( ) = 47 + 10.
У матриці, відповідної   вважаємо c 14 = ∞.

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 1 = 10 отримаємо нову нижню межу 57 + 10 = 67.
У матриці, відповідної , Викреслюємо перший рядок і четвертий стовпець і покладемо c 41 = ∞, щоб запобігти появи циклу 1 → 4 → 1. Отримаємо нову платіжну матрицю {c 1 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 = 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 нульових елементів цієї матриці Θ 21 = 16, Θ 36 = 5, Θ 42 = 2, Θ 56 = 2, Θ 62 = 0, Θ 63 = 9, Θ 65 = 2. Найбільший ступінь Θ 21. Потім безліч розбивається дузі (2, 1) на два нових і .
У матриці для викреслюємо рядок 2 і стовпець 1. дуги (1, 4) і (2, 1) складають зв'язний шлях (2, 1, 4), покладемо c 42 = ∞, щоб запобігти появи циклу 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 4 = 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 нульових елементів цієї матриці Θ 36 = 5, Θ 45 = 0, Θ 56 = 22, Θ 62 = 13, Θ 63 = 7, Θ 65 = 0. Найбільший ступінь Θ 56. Потім безліч розбивається дузі (2, 1) на два нових   і .
Нижня межа для   дорівнює 50 + 22 = 72. У матриці для викреслюємо рядок 5 і стовпець 6 і вважаємо c 65 = ∞. Отримаємо матрицю:
2
3
5
3
13

5
4

7
0
6
0
0

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


Рис. 3 Галуження на третьому кроці
Наведена платіжна матриця для
2
3
5
3
8

0
4

7
0
6
0
0

Ступені Θ ij нульових елементів цієї матриці Θ 35 = 8, Θ 45 = 7, Θ 62 = 8, Θ 63 = 7. Вибираємо Θ 35 = 8. Розбиваємо   на   і .
Нижня межа для   дорівнює 55 + 8 = 64. У матриці для   викреслюємо рядок 3 і стовпець 5 і вважаємо c 63 = ∞. Отримаємо
2
3
4

7
6
0

Для приведення треба відняти мінімум по рядку 4: r4 = 7. При цьому нижня межа стане рівною 55 +7 = 62. Після приведення отримаємо
2
3
4

0
6
0

З матриці 2'2 отримуємо два переходи з нульовою довжиною: (4, 3) і (6, 2).

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).
Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Завдання
139.8кб. | скачати


Схожі роботи:
Рішення задачі про комівояжера
Рішення транспортної задачі методом потенціалів
Рішення задачі лінійного програмування графічним методом
Рішення задачі лінійного програмування симплекс методом
Рішення задачі лінійного програмування симплексним методом
Рішення задачі оптимального резервування системи методом динамічного програмування
Використання методу гілок і меж при адаптації робочого навантаження до параметрів обчислювального
Експертна система для вирішення задачі про комівояжера
Метод програмування і схем гілок у процесах рішення задач дискретної оптимізації
© Усі права захищені
написати до нас