1.3.3. Метод гілок і меж

До ідеї методу гілок і меж приходили багато дослідників, але Літтл зі співавторами на основі зазначеного методу розробили вдалий алгоритм розв'язання ЗК і тим самим сприяли популяризації підходу. З тих пір метод гілок і меж був успішно застосований до багатьох завдань, для вирішення ЗК було придумано кілька інших модифікацій методу, але в більшості підручників викладається піонерська робота Літтла.

Загальна ідея тривіальна: потрібно розділити величезне число перебираються варіантів на класи і отримати оцінки (знизу - в задачі мінімізації, зверху - в задачі максимізації) для цих класів, щоб мати можливість відкидати варіанти не по одному, а цілими класами. Складність полягає в тому, щоб знайти такий поділ на класи (гілки) і такі оцінки (межі), щоб процедура була ефективною.

  Викладемо алгоритм Літтла на прикладі 1 попереднього розділу .. Повторно запишемо матрицю:

-	1	2	3	4	5	6
1	-	6	4	8	7	14
2	6	-	7	11	7	10
3	4	7	-	4	3	10
4	8	11	4	-	5	11
5	7	7	3	5	-	7
6	14	10	10	11	7	-
табл. 2

-	1	2	3	4	5	6
1	-	2	0	4	3	10
2	0	-	1	5	1	4
3	1	4	-	1	0	7
4	4	7	0	-	1	7
5	4	4	0	2	-	4
6	7	3	3	4	0	-
табл. 3

-	1	2		3		4		5	6
1	-	0		0		3		3	6
2	0	-		1		4		1	0
3	1	2		-		0		0	3
4	4	5		0		-		1	3
5	4	2		0		1		-	0
6	7	1		3		3		0	-
			2		1				4
табл. 4

Нам буде зручніше трактувати Сij як вартість проїзду з міста i в місто j. Припустимо, що добрий мер міста j видав указ виплачувати кожному в'їхали в місто комівояжеру 5 доларів. Це означає, що будь-який тур подешевшає на 5 доларів, оскільки в будь-якому турі потрібно в'їхати в місто j. Але оскільки всі тури рівномірно подешевшали, то колишній мінімальний тур буде і тепер коштувати менше всіх. Добрий же вчинок мера можна представити як зменшення всіх чисел j-го шпальти матриці С на 5. Якби мер хотів спровадити комівояжерів з j-го міста і встановив нагороду за виїзд в розмірі 10 доларів, це можна було б висловити відніманням 10 з усіх елементів j-й тієї рядки. Це знову б змінило вартість кожного туру, але мінімальний тур залишився б мінімальним. Отже, доведена наступна лема.

Віднімаючи будь-яку константу з усіх елементів будь-якого рядка або стовпця матриці С, ми залишаємо мінімальний тур мінімальним.

Для алгоритму нам буде зручно отримати побільше нулів в матриці С, не отримуючи там, однак, негативних чисел. Для цього ми віднімемо з кожного рядка її мінімальний елемент (це називається приведенням по рядках, див. Табл. 3), а потім віднімемо з кожного шпальти матриці, наведеної по рядках, його мінімальний елемент, отримавши матрицю, наведену по стовпцях, див. Табл . 4).

Прочерки по діагоналі означають, що з міста i в місто i ходити не можна. Зауважимо, що сума констант приведення по рядках дорівнює 27, сума по стовпцях 7, сума сум дорівнює 34.

   Тур можна задати системою з шести підкреслених (виділених іншим кольором) елементів матриці С, наприклад, такий, як показано на табл. 2. Підкреслення елемента означає, що в турі з i-го елемента йдуть саме в j-тий. Для туру з шести міст підкреслених елементів має бути шість, так як в турі з шести міст є шість ребер. Кожен стовпець повинен містити рівно один підкреслений елемент (в кожне місто комівояжер в'їхав один раз), в кожному рядку повинен бути рівно один підкреслений елемент (з кожного міста комівояжер виїхав один раз); крім того, підкреслені елементи повинні описувати один тур, а не кілька менших циклів. Сума чисел підкреслених елементів є вартість туру. На табл. 2 вартість дорівнює 36, це той мінімальний тур, який отримано лексикографічним перебором.

Тепер будемо міркувати від наведеної матриці на табл. 2. Якщо в ній вдасться побудувати правильну систему підкреслених елементів, тобто систему, що задовольняє трьом вищеописаним вимогам, і цими підкресленими елементами будуть лише нулі, то ясно, що для цієї матриці ми отримаємо мінімальний тур. Але він же буде мінімальним і для вихідної матриці С, тільки для того, щоб отримати правильну вартість туру, потрібно буде назад додати всі константи приведення, і вартість туру зміниться з 0 до 34. Таким чином, мінімальний тур не може бути менше 34. Ми отримали оцінку знизу для всіх турів.

Тепер приступимо до розгалуження. Для цього виконаємо крок оцінки нулів. Розглянемо нуль у клітині (1,2) наведеної матриці. Він означає, що ціна переходу з міста 1 в місто 2 дорівнює 0. А якщо ми не підемо з міста 1 в місто 2? Тоді все одно потрібно в'їхати в місто 2 за ціни, зазначені у другому стовпці; найдешевше за 1 (з міста 6). Далі, все одно треба буде виїхати з міста 1 за ціну, зазначену в першому рядку; найдешевше в місто 3 за 0. Підсумовуючи ці два мінімуму, маємо 1 + 0 = 1: якщо не їхати «по нулю» з міста 1 в місто 2, то треба заплатити не менше 1. Це і є оцінка нуля. Оцінки всіх нулів поставлені на табл. 5 правіше і вище нуля (оцінки нуля, рівні нулю, не ставилися).

Виберемо максимальну з цих оцінок (у прикладі є кілька оцінок, рівних одиниці, виберемо першу з них, у клітці (1,2)).

Отже, вибрано нульове ребро (1,2). Розіб'ємо всі тури на два класи - включають ребро (1,2) і не включають ребро (1,2). Про другий клас можна сказати, що доведеться доплатити ще 1, так що тури цього класу коштують 35 або більше.

Що стосується першого класу, то в ньому треба розглянути матрицю на табл. 6 з викресленої першим рядком і другим стовпцем.

	1	2	3	4	5	6
1	-	01	0	3	3	6
2	01	-	1	4	1	0
3	1	2	-	01	0	3
4	4	5	01	-	1	3
5	4	2	0	1	-	0
6	7	1	3	3	01	-
табл. 5

	1	3	4	5	6
2	01	1	4	1	0
3	1	-	01	0	3
4	4	01	-	1	3
5	4	0	1	-	0
6	7	3	3	01	-
табл. 6

	1	3	4	5	6
2	01	1	4	1	0
3	03	-	01	0	3
4	3	01	-	1	3
5	3	0	1	-	0
6	6	3	3	01	-
табл. 7

	3	4	5	6
2	1	4	1	0
4	01	-	1	3
5	0	1	-	0
6	3	3	01	-
табл. 8

Д одатково в зменшеної матриці поставлений заборона в клітці (2,1), т. К. Вибрано ребро (1,2) і замикати передчасно тур руба (2,1) не можна. Зменшену матрицю можна привести на 1 по першому стовпцю, так що кожен тур, їй відповідає, коштує не менше 35. Результат наших розгалужень і отримання оцінок показаний на рис.6.

Г уртки представляють класи: верхній гурток - клас всіх турів; нижній лівий - клас всіх турів, що включають ребро (1,2); нижній правий - клас всіх турів, що не включають ребро (1,2). Числа над кружками - оцінки знизу.

Продовжимо розгалуження в позитивну сторону: вліво - вниз. Для цього оцінимо нулі в зменшеної матриці C [1,2] на табл. 7. Максимальна оцінка в клітці (3,1) дорівнює 3. Таким чином, оцінка для правої нижньої вершини на рис. 7 є 35 + 3 = 38. Для оцінки лівої нижньої вершини на рис. 7 потрібно викреслити з матриці C [1,2] ще рядок 3 і стовпець 1, отримавши матрицю C [(1,2), (3,1)] на табл. 8. У цю матрицю потрібно поставити заборону в клітку (2,3), так як вже побудований фрагмент туру з ребер (1,2) і (3,1), тобто [3,1,2], і потрібно заборонити передчасне замикання (2,3). Ця матриця наводиться по стовпцю на 1 (табл. 9), таким чином, кожен тур відповідного класу (тобто тур, що містить ребра (1,2) і (3,1)) стоїть 36 і більше.

	3	4	5	6
2	1	3	1	0
4	01	-	1	3
5	0	02	-	0
6	3	2	03	-
табл. 9

	3	4	6
2	1	3	03
4	03	-	3
5	0	03	0
табл. 10

	3	4
4	0	-
5	0	0
табл.11

Оцінюємо тепер нулі в наведеній матриці C [(1,2), (3,1)] нуль з максимальною оцінкою 3 знаходиться в клітці (6,5). Негативний варіант має оцінку 38 + 3 = 41. Для отримання оцінки позитивного варіанта прибираємо сходинку 6 і стовпець 5, ставимо заборона у клітину (5,6), див. Табл. 10. Ця матриця непріводімим. Отже, оцінка позитивного варіанта не збільшується (рис.8).

Оцінюючи нулі в матриці на табл. 10, отримуємо розгалуження за вибором ребра (2,6), негативний варіант отримує оцінку 36 + 3 = 39, а для отримання оцінки позитивного варіанта викреслюємо другий рядок і шостий стовпець, одержуючи матрицю на табл. 11.

У матрицю треба додати заборона у клітину (5,3), бо вже побудований фрагмент туру [3,1,2,6,5] і треба заборонити передчасний повернення (5,3). Тепер, коли залишилася матриця 2х2 із заборонами по діагоналі, добудовуємо тур ребрами (4,3) і (5,4). Ми не даремно гілкувалися, по позитивним варіантів. Зараз отриманий тур: 1 → 2 → 6 → 5 → 4 → 3 → 1 вартістю в 36. При досягненні низу по дереву перебору клас турів звузився до одного туру, а оцінка знизу перетворилася в точну вартість.

О тже, всі класи, що мають оцінку 36 і вище, кращого туру не містять. Тому відповідні вершини викреслюються. Викреслюються також вершини, обидва нащадка якої викреслені. Ми колосально скоротили повний перебір. Залишилося перевірити, чи не містить кращого туру клас, відповідний матриці С [Not (1,2)], тобто наведеній матриці С із забороною в клітці 1,2, наведеної на 1 по стовпцю (що дало оцінку 34 + 1 = 35). Оцінка нулів дає 3 для нуля в клітці (1,3), так що оцінка негативного варіанту 35 + 3 перевершує вартість вже отриманого туру 36 і негативний варіант відсікається.

Для отримання оцінки позитивного варіанта виключаємо з матриці перший рядок і третій стовпець, ставимо заборона (3,1) і отримуємо матрицю. Ця матриця наводиться по четвертому рядку на 1, оцінка класу сягає 36 і гурток закреслюється. Оскільки у вершини «все» вбиті обидва нащадка, вона убивається теж. Вершин не залишилося, перебір закінчено. Ми отримали той же мінімальний тур, який показаний підкресленням на табл. 2.

Задовільних теоретичних оцінок швидкодії алгоритму Літтла та споріднених алгоритмів немає, але практика показує, що на сучасних ЕОМ вони часто дозволяють вирішити ЗК з n = 100. Це величезний прогрес у порівнянні з повним перебором. Крім того, алгоритми типу гілок і меж є, якщо немає можливості доводити їх до кінця, ефективними евристичними процедурами.