Материал: 62_201

місто 4 вже остаточно визначені (мал. 106, б), а у другому - таб­ лиця (мал. 105, а) з виключеним ребром (1,4) (С1 4 = «-»), оскільки вирішено далі його не розглядати (мал. 106, в). Зазна­ чимо, що при подальшому виключенні рядків і стовпців таб­ лиці зберігатимемо їх початкову нумерацію, оскільки ці номе­ ри визначають реальні вершини заданого графа.

Можна говорити про побудову бінарного дерева розв'язку задачі. У вершині 1 цього дерева розміщено вихідну таблицю (мал. 106, а) і дії щодо визначення сумарної константи її приве­ дення (23), що є одночасно нижньою границею, та визначення найбільшої вартості ризику нульового ребра (4) (мал. 106, г). Ця вершина дерева розв'язку має двох нащадків. У вершині 2 розміщено перший варіант, розглянутий вище, а у вершині 3 - другий. На ребрах цього дерева вказано нижню границю вар­ тості переходу до відповідних вершин.

Подальші дії розгалужуються: у лівій гілці дерева розв'язку розглядатиметься побудова гамільтонового циклу з поточною нижньою границею 23 з урахуванням того, що ребро (1,4) уві­ йшло до нього, а у правій - з поточною нижньою границею 27 з урахуванням того, що до шуканого циклу поки не включено жодного ребра, а ребро (1,4) зовсім виключене з перегляду.

Оскільки все одно треба буде розглянути обидві гілки, домо­ вимося надалі рухатися спочатку лівою, а потім уже правою. Розглянемо таблицю (мал. 106, б) і приведемо її по рядках (мал. 107, о) та стовпцях (мал. 107, б). Сумарна константа при­ ведення становить 4. Вартість ризику нульових ребер таблиці (мал. 105, б) визначена на малюнку 107, в. Наступним ребром для дослідження буде (4,5), оскільки саме воно має найбільшу вартість ризику 2. Вчинимо з ним так само, як і з ребром (1,4): в одному варіанті включимо його до шуканого циклу й інфор­ мацію про це розмістимо у вершині 4 дерева розв'язку, а у дру­ гому виключимо з перегляду, про що свідчитиме вершина 5 де­ рева розв'язку (мал. 107, г).

У вершині 2 дерева розв'язку уточнимо інформацію: у ре­ зультаті приведення матриці, що розглядалася у цій вершині, отримано сумарну константу приведення 4; вартість переходу

170

від вершини 2 до вершини 4 збільшить нижню границю вар­ тості 23 на це значення і тепер становитиме 27; перехід до вершини 5 збільшить значення нижньої границі вартості 27 на максимальну вартість ризику ребра (4,5), що становить 2. Та­ ким чином, вартість переходу від вершини 2 до вершини 5 де­ рева розв'язку буде обмежена значенням нижньої границі 29.

Для вершини 4 дерева розв'язку (мал. 107, г) розглядається таблиця (мал. 107, в) без 3-го рядка і 4-го стовпця, представлена на малюнку 108, а, що відповідає виходам з 4-ї і входам у 5-ту вершину графа. Для вершини 5 - таблиця, представлена на малюнку 108, б, де виключене з розгляду ребро (4,5). У таблиці (мал. 108, а), окрім викреслених 4-го рядка і 5-го стовпця, еле­ мент С5 х набув значення «-». Слушне запитання: чому? Якщо розглядається вершина 4 дерева розв'язку, то це означає, що шуканий цикл містить два ребра (1,4) і (4,5) гілки, які скла­ даються з вершин 1, 2, 4. Оскільки визначення циклу ще не за­ вершено, то «зациклювати» будь-яке ребро або послідовність ребер зарано. Ребра (4,1) і (5,4) у таблиці на малюнку 108, а відсутні, тому залишається виключити ребро (5,1).

За традицією перейдемо до вершини 4 дерева розв'язку. Вартість цього переходу обмежуватиметься нижньою границею 27. Приведе­ мо таблицю (мал. 109, а): по рядках константа приведення дорівню-

171

регляду додасть ще 2 (вершина 7 дерева розв'язку). Продовжимо по­ будову дерева розв'язку на малюнку 109, б.

Розглянемо переваги включення ребра (2,3) до шуканого цик­ лу, тобто перейдемо до вершини 6 у дереві розв'язку. Виключимо 2-й рядок і 3-й стовпець, заблокуємо ребро (3,2) як те, що може передчасно зациклити процес, і отримаємо таблицю, представле­ ну на малюнку 110, а. Спроби її приведення по рядках і стовпцях дадуть сумарну константу зі значенням 0. Визначення вартості

172

ризику для її нульових елементів так само дасть результат зі зна­ ченням 0. Отже, за умовами попередніх дій можна вибрати будьяке ребро з вартістю ризику 0 для включення його до шуканого циклу. Нехай це буде ребро (3,1). У дереві розв'язку отримаємо нову вершину 8. Подальший розгляд лівої гілки дерева розв'язку (мал. 110, г) приводить до отримання таблиці (мал. 110, б), де присутнє лише одне ребро (5,2), яке необхідно включити до цик­ лу (вершина 10 дерева розв'язку). Оцінка нижньої границі вар­ тості включення цього ребра лишається незмінною і дорівнює 29. Таким чином, проаналізувавши ліву гілку дерева розв'язку, яка привела до умови відсутності продовження пошуку, отримано та­ ку послідовність ребер, сума довжин яких становить 29: (1,4), (4,5), (2,3), (3,1), (5,2). Можна стверджувати, що вони утворюють гамільтонів цикл у заданому повному зваженому неорієнтованому графі (1,4), (4,5), (5,2), (2,3), (3,1).

Однак пошук коректної відповіді на поставлену задачу не можна завершувати, оскільки є не оброблені праві гілки дерева, де можуть також знаходитися правильні результати. Оскільки вже отримано послідовність ребер, що утворюють гамільтонів цикл вартістю 29, то резонно надалі розглядати лише ті послідов­ ності ребер, сумарна вартість яких не перевищує знайденої.

Розглянемо останню справа гілку, тобто вершину 11 дерева розв'язку, яка одержана виключенням із розгляду ребра (5,2). До неї веде така послідовність вершин дерева: 1,2,4, 6, 8, 9. Невключення ребра (5,2) до послідовності ребер (1,4), (4,5), (2,3), (3,1) втрачає будь-який сенс, оскільки у цьому разі цикл не буде утворено.

Повертаємося до вершини 9. На цьому кроці до шуканого циклу включено ребра (1,4), (4,5), (2,3) і виключено з перегля­ ду ребро (3,1). Поточна нижня границя вартості дорівнює 29, тобто ще не перевищена довжина визначеного гамільтонового циклу. Розглянемо таблицю, представлену на малюнку 110, в, з виключеним ребром (3,1) (С3 1 = «-»). Претендентом на вклю­ чення до шуканого циклу залишається тільки ребро (5,2), але при цьому, як і попереднього разу, цикл утворено не буде. Вис­ новок такий: дерево у вершині 9 неможливо добудувати.

Піднімаємося до вершини 7. Розгляд цієї гілки так само безпер­ спективний, оскільки нижня границя переходу до неї 31 більша за значення довжини побудованого гамільтонового циклу 29.

Вершина 5 дає привід для розгляду, оскільки її нижня гра­ ниця не перевищує знайденого результату. Розглянемо табли­ цю, представлену на малюнку 108, б. її приведення показано на малюнку 111, а, б, звідки видно, що сума обох констант приве­ дення дорівнює 2. Тобто перехід до будь-якої з вершин-на- щадків вершини 5 збільшить нижню границю вартості май-

173

бутнього циклу до значення 31, що не дає можливості продов­ жувати пошук у цьому напрямі.

Залишилося розглянути тільки одну праву вершину З (мал. 110, г). Значення нижньої границі вартості 27 - досить непоганий привід для подальшого пошуку. Розглянемо таблицю, зображену на малюнку 110, в, і виконаємо її приведення по ряд­ ках і стовпцях (мал. 111, а, б). Результатом такого приведення є значення суми констант 4. Таким чином, перехід до лівого на­ щадка вершини 5 коштуватиме щонайменше 31. Прийняття рішення щодо розгляду цієї гілки дерева розв'язку може бути тільки таким: він безперспективний, оскільки на першому ж кроці нижня границя вартості гамільтонового циклу 31 (27 + 4 = = 31) вже перевищила знайдену 29, а з урахуванням вартості ризику виключення ребра (4,1) (мал. 111, в) ще збільшить її на 4.

Таким чином, можна визнати факт, що знайдено розв'язок задачі про комівояжера вартістю 29, яка складається з таких ребер: (1,4), (4,5), (5,2), (2,3), (3,1). Ця відповідь повністю збігається з визначеною раніше.

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

1.Задати матрицю суміжності досліджуваного повного гра­ фа А, що складається з N вершин.

2.ЯкщоЛ^= 1 іА1 д = 0, то перейти до п. 9.

3.Привести задану таблицю по рядках і стовпцях і визначи­ ти сумарну константу приведення.

4.Визначити вартість шуканого гамільтонового циклу на даному кроці, додавши сумарну константу приведення.

5.Обчислити вартість ризику кожного нульового ребра, що відображено у таблиці.

6.Визначити нульове ребро з максимальним ризиком.

7.Розглянути випадок, коли ребро з максимальною вартіс­ тю ризику включається до шуканого циклу: дописати ребро з максимальною вартістю ризику до списку ребер, що утворюють

174