Метод гілок і границь

Розглянемо більш детально метод гілок та границь, про який вже йшла мова у цілочисловому програмуванні. Нехай U-множина варіантів рішення деякої задачі. Якщо ці варіанти перенумерувати від 1 до т, то під U можна розуміти множина номерів варіантів рішення, тобто покласти U={1,..., т}.

Позначимо через q_i значення деякого параметра, що характеризує якість рішення в i-м варіанті. Оптимальним рішенням буде таке, котре дає мінімальне значення

(4.6)

критерію якості, що є точною нижньою границею для множини {q₁,...,q_т}.

Уведемо поняття оцінки знизу для множини U, під якою будемо розуміти таке значення , яке задовольняє співвідношенню

(4.7)

Якщо в співвідношенні (4.7) стоїть знак нестрогої нерівності , то оцінку будемо називати досяжною.

Метод гілок і границь складається в послідовному поліпшені оцінки і наближенні її до значення q*. Припустимо, що маємо можливість одержати оцінку знизу як для всієї множини U, так і для її різних підмножин.

Розіб'ємо множину U на дві підмножини A і B з точними нижніми границями критерію якості q* і q*, зв'язаними з q* очевидним співвідношенням

(4.8)

Оскільки в множинах А та B є присутнім менше число елементів, ніж у множині U, то мається можливість одержати оцінки , , більш близькі до значень q*, q*, чим у первісній множині U, що означає, що оцінка тin ( , ) буде більш близька до q*, чим оцінка .

Існує також велика імовірність того, що оптимальний варіант, тобто варіант із найменшим значенням q = q*, виявиться у тій з підмножин A і B, що має меншу оцінку знизу. Ця імовірність буде тим більше, чим більше відрізняються одна від одної оцінки і , тому розбивати множину U на підмножини A і B бажано так, щоб оцінки знизу для цих підмножин відрізнялися якнайбільше.

Якщо виявилося, що < , то є підстави підозрювати, що оптимальний варіант входить у множину В і цю множину треба досліджувати детальніше. Для цього розбиваємо її у свою чергу на дві підмножини С и D так, щоб оцінки і розрізнялися якнайбільше. Якщо виявилося, що < , то подібній же розбивці піддаємо множину D і т.д. доти, поки не прийдемо до підмножини, що складається усього з одного елемента зі значенням параметра q = q₀. Усю процедуру розбивки зручно представити у виді дерева розбивок, наведеного на рисунку 4.1.

Рис. 4.1

Однак знайдений елемент зі значенням q = q₀ може лише підозрюватися як оптимальний. Необхідно перевірити, чи немає серед нерозглянутих множин A, С і т. д. елемента зі значенням q < q₀. При цьому множини, у яких > , можуть не розглядатися, оскільки елемента q<q₀ у них бути не може.

Розбивка вищевказаних множин приведе до елемента q<q₀, тоді цей елемент і повинний бути прийнятий за оптимальний, що приведе до оцінок знизу > . У цьому випадку елемент зі значенням параметра і буде шуканим варіантом рішення задачі.

4.11. Застосування методу гілок і границь до розв’язання задачі комівояжера

Вважаємо, що задача комівояжера задана у виді матриці відстані по типу табл. 4.4. Для конкретності задамося чисельними значеннями відстаней, що приводяться в чисельнику табл. 4.5.

Таблиця 4.5

	1	2	3	4	5
1	х	7/5	7/4	2/0	4/2
2	6/5	х	2/0	4/3	1/0
3	6/5	1/0	х	9/8	2/1
4	2/0	3/1	8/5	х	5/3
5	6/5	1/0	2/0	5/4	х

Таблиця 4.6

	2	3	4	5
1	5/3	4/2	x	2/0
2	x	0/0	3/0	0/0
3	0/0	x	8/5	1/1
5	0/0	0/0	4/1	x

Таблиця 4.7

	2	3	4
2	x	0	0
3	0	x	5
5	0	0	x

Для одержання оцінки знизу довжин множини всіх гамільтонових контурів скористаємося тим, що в кожен гамільтонів контур входить тільки по одному елементу з кожного рядка і з кожного стовпця матриці відстаней. Тому якщо елементи будь-якого рядка чи будь-якого стовпця зменшити на яке-небудь число, то на це ж число зменшаться довжини всіх гамільтонових контурів. На цій властивості заснований метод приведення матриці відстаней.

Приведення матриці може відбуватися по рядках і стовпцям. Приведення матриці відстаней по рядках полягає в тому, що з елементів кожного рядка i віднімають найменший елемент цього рядка, що позначається h_i. При цьому довжини всіх гамільтонових контурів зменшаться на суму віднятих з кожного рядка чисел, тобто на величину , залишаючись у той же час невід’ємними. Тому величина , рівна в розглянутому прикладі 7, дає деяку оцінку знизу довжин всіх гамільтонових контурів. Отримана оцінка може бути поліпшена шляхом повторного приведення матриці відстаней по стовпцях. При цьому зі значень елементів кожного стовпця i приведених по рядках матриці відстаней віднімається найменший елемент цього стовпця, що позначається g_i. Сума віднятих при цьому чисел . Уточнена оцінка знизу довжин гамільтонових контурів

(4.9)

Одержувана після приведення матриця відстаней (значення в знаменнику) дана у виді табл. 4.5.

Метод приведення матриці відстаней будемо застосовувати і далі для одержання оцінок знизу різних підмножин множини гамільтонових контурів.

Розглянемо тепер спосіб розбивки множини гамільтонових контурів на підмножини. Візьмемо деяку дугу (i,j). До першої підмножини віднесемо всі гамільтонові контури, у які ця дуга входить. Позначимо цю множина [(i,j)]. До другої множини віднесемо всі гамільтонові контури, у які дуга (i,j) не входить. Цю множина позначимо .

Таблицю відстаней для множини легко одержати, якщо врахувати, що включення дуги (i,j) у гамільтонів контур виключає можливість включення інших дуг, що стоять у i-му рядку чи j-му стовпці. Отже, таблиця відстаней для множини [(i,j)] виходить з первісної таблиці викреслюванням i-го рядка і j-го стовпця.

Для того щоб одержати таблицю відстаней для множини , необхідно в первісній таблиці заборонити рух по дузі (i,j), поклавши її довжину рівній нескінченності. Цю заборону руху по дузі (i,j) будемо відзначати хрестом у відповідній клітці первісної таблиці.

Тепер виникає питання: яку дугу покласти в основу розбивки множини маршрутів на підмножини? Помітимо, що по кількості елементів множини [(i,j)] і не однакові. Загальне число гамільтонових контурів у задачі з n містами дорівнює (n-1)!. Якщо зафіксували дугу (і,j), тобто вибрали дві вершини, то існує n-2 способів вибрати третю, n-3 способів — четверту і т.д. Отже, існує (n-2)! гамільтонових контурів, що включають дугу (i,j), та (n-1)!-(n-2)!=(n-2)(n-2)! гамільтонових контурів, що не включають дугу (i,j). Тому при n>2 множина буде містити більшу кількість елементів, чим множина . А оскільки множину з меншим числом елементів досліджувати простіше, то як дугу (i,j) варто брати таку, при якій множина має меншу оцінку, чим множина . З множини дуг, що задовольняють цій умові, варто віддати перевагу тій, яка дає найбільшу різницю в оцінках для множин [(i,j)] і .

Якщо як дугу (i,j) узяти таку, у якої в приведеній таблиці di,j≠0, то для групи [(i,j)] оцінка знизу зростає на d_ij, оскільки заздалегідь відомо, що ця дуга увійде в усі гамільтонові контури. Вона може ще зрости, якщо таблиця при викреслюванні i-го рядка і j-го стовпця буде допускати подальше приведення. У той же час при заміні елемента d_ij на нескінченність таблиця відстаней залишиться приведеною, тобто оцінка знизу для не зросте. Отже, менше значення оцінки знизу буде для множини , що небажано. Тому як дугу (i,j) треба брати таку, у якої в приведеній таблиці відстаней величина d_ij=0.

Але таких дуг декілька. Яку ж з них вибрати? Очевидно, ту, для якої збільшення оцінки для множини [(i,j)] буде найбільшим, тому що при цьому вийде найбільша різниця в оцінках для множин [(i,j)] і .

Позначимо збільшення оцінки множини через ∆(і,j). Значення цієї величини одержуємо шляхом додавання найменших чисел у i-му рядку і j-му стовпці.

Звернемося знову до розглянутого приклада. Для табл. 4.5 (знаменник) значення ∆ (і,j) наступні:

∆(1, 4) =2+3=5; ∆(2, 3)=0;

∆(2,5)=1; ∆(3,2)=1; ∆(4,1)=6;

∆(5,2)=0; ∆(5,3)=0.

Найбільше збільшення оцінки для групи виходить для дуги (4,1). Крім четвертого рядка і першого стовпця з приведеної матриці, приходимо до табл. 4.6 (чисельник), що представляє собою таблицю відстаней для множини [(4, 1)].

При одержанні подібних матриць треба строго стежити за тим, щоб не могло вийти контурів, що не є гамільтоновими. Оскільки дуга [(4,1)] уже введена в намічуваний гамільтонів контур, то потрібно накласти заборону на дугу [(1,4)], відзначивши клітинку [(1,4)] хрестом, тому що дуга [(1,4)] разом з дугою [(4,1)] утворить контур. У табл. 4.6 (знаменник) дана приведена таблиця відстаней зі збільшенням оцінки ∆ =2+3=5.

Для табл. 4.6 (знаменник) значення ∆ (і,j) наступні:

∆(1,5)=2; ∆(2,3)=0; ∆(2,4)=1;

∆(2,5)=0; ∆(3,2)=1; ∆(5,2)=0;

∆(5,3)=0.

Найбільше збільшення оцінки для групи виходить для дуги [(1,5)], що також вводимо в намічуваний гамільтонів контур, одержуючи ланцюжок [(4,1,5)]. Крім першого рядка і п'ятого стовпця з матриці табл. 4.6 (знаменник), приходимо до табл. 4.7 для множини [(4,1) (1,5)], у якій необхідно накласти заборону на дугу [(5,4)], що утворить контур з ділянкою [(4,1,5)]. Отримана таблиця є приведеною. Тому для неї відразу ж знаходимо значення ∆(i,j):

∆(2,3)=0; ∆(2,4)=5; ∆(3,2)=5;

∆(5,2)=0; ∆(5,3)=0.

Як бачимо, найбільші значення ∆(i,j) вийшли рівними для дуг (2,4) і (3,2). Тому обидві ці дуги можна віднести до намічуваного гамільтонову контуру, одержуючи, таким чином, послідовність дуг [(3,2)], [(2,4)], [(4,1)], [(1,5)], для замикання якої не вистачає лише дуги [(5,3)]. Додаючи цю дугу, одержуємо передбачуваний оптимальний гамільтонів контур [(3,2,4,1,5,З)] довжиною 13.

Аналізуючи нерозглянуті раніше підмножини , [(4,1)], , 1, [(4, 1), (1, 5), , переконуємося, що їх оцінки знизу більше, ніж 13, так що ці підмножини не можуть містити гамільтонові контури коротше знайденого. Отже, подальша перевірка не потрібна й отриманий гамільтонів контур є оптимальним.

На рисунку 4.2 приведене дерево розбивок, що будується по ходу розв’язання задачі.

Рис. 4.2