Материал: 62_201

Завдання

1.Розробити та реалізувати у вигляді програми алгоритм ви­ значення максимального паросполучення у заданому дво­ дольному графі.

2.Виконати завдання 1 для дводольного графа з кількістю вер­ шин N ^ 10, визначивши кількість необхідних для одержан­ ня результату ітерацій. Результат виконання програми ви­ вести у файл.

3.Виконати завдання 1 для графа з кількістю вершин N > 10, визначивши кількість необхідних для одержання результа­ ту ітерацій. Результат виконання програми вивести у файл.

4.Виконати порівняльний аналіз виконання завдань 2-3 щодо ефективності роботи алгоритму.

уЗапитання для самоконтролю

1.Які графи називають дводольними? Наведіть власні приклади.

2.Що розуміють під паросполученням у дводольному графі?

3.Яке паросполучення називається максимальним?

4.Чи завжди однозначно розв'язується задача побудови макси­ мального паросполучення? Обґрунтуйте свою відповідь на влас­ ному прикладі.

5.Сформулюйте класичну задачу, яка розв'язується за допомогою побудови максимального паросполучення на дводольних графах.

6.Яким чином можна застосувати алгоритм побудови максималь­ ного потоку до задачі про визначення максимального пароспо­ лучення у дводольних графах?

7.Продемонструйте роботу алгоритму побудови максимального потоку для визначення максимального паросполучення у дво­ дольному графі на власному прикладі.

8.Яким чином необхідно модифікувати алгоритм Форда-Фалкер- сона при його застосуванні до визначення максимального па­ росполучення у дводольному графі?

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

10.Як виглядатиме основний блок програми, визначає максималь­ не паросполучення у дводольному графі?

11.Якою є оцінка алгоритму побудови максимального паросполу­ чення у дводольному графі? Обґрунтуйте свою відповідь.

Наближений розв'язок задачі про комівояжера

У даному розділі розглянуто методи, які тим чи іншим чи­ ном визначають оптимальні розв'язки поставлених задач. Де­ які з них можна назвати жадібними, оскільки розв'язки задач визначаються за допомогою вибору наиоптимальнішого ходу на кожному кроці виконання алгоритму. Докладніше питання визначення коректності використання жадібних алгоритмів розглядатимемо пізніше в окремому розділі.

160

Досить часто на практиці використовують евристичні (з грец. heurisko - відшуковую) методи розв'язування поставлених задач. Суть евристичних методів - нехтування деякими харак­ теристиками алгоритму під час побудови його оптимального варіанта. Такий підхід дає можливість розробити алгоритм, що для більшості тестів дає очікуваний результат. Саме еврис­ тичні алгоритми подекуди розробляються учасниками олімпіадних змагань, коли їм не вдається досягнути авторського розв'язку запропонованої задачі. Якщо для такого алгоритму пройде більшість запропонованих тестів, то можна вважати, що він максимально наближений до авторського. Однак до евристичних алгоритмів вдаються і науковці. Це можливо під час роботи над складними досліджуваними задачами, для яких ще не знайдено оптимального алгоритму, наприклад потужни­ ми моделюючими програмами.

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

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

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

Як відомо, безвихідних ситуацій бути не може. У разі, коли немає можливості отримати точний розв'язок задачі, намагаю­ ться віднайти якомога близький до нього. Існують методи зна­ ходження наближених розв'язків задач. І саме до таких звер­ немося на прикладі задачі про комівояжера.

Нехай алгоритм А - це поки що не розроблений оптималь­ ний алгоритм розв'язання поставленої задачі. Однак за допомо­ гою алгоритму з повним перебором визначено точний розв'язок задачі rezA. Нехай також розроблено деякий наближений алго­ ритм В, який дає розв'язок цієї самої задачі rezB. Якщо йдеть­ ся про розв'язання задачі про комівояжера щодо знаходження найкоротшого шляху, то зрозуміло, що rezB= rezA+ є, де є - це похибка побудованого алгоритму. Оскільки ведеться пошук найкоротшого шляху, то точна відповідь завжди менша за будь-яку іншу наближену. Тому чим менше значення є, тим кращий знайдений наближений розв'язок задачі.

Алгоритм Ейлера

Алгоритм Ейлера, що реалізовує наближений розв'язок задачі про комівояжера, базується на вже розглянутих вище алгоритмах.

Для наочності пояснення розглянемо приклад повного графа (мал. 101, а).

Мал. 101

На початку слід зауважити, що алгоритм Ейлера, який будує гамільтонів цикл мінімальної довжини для повного графа, пра­ цює лише за умови, що для кожної трійки вершин і, /, k вико­ нується нерівність трикутника: dij<dik + dkj. Ця умова тлума­ читься дуже просто: відстань між двома містами і та ] завжди менша, ніж відстань між ними через третє місто k (мал. 101, б).

Наступна послідовність міркувань є такою. По-перше, граф, що описує схему міст, якими їздить комівояжер, є повним. Подруге, комівояжер повинен відвідати кожне місто, побувавши в ньому лише один раз. Це означає, що його шлях є гамільтоновим циклом. Оскільки у повному графі для комівояжера є {N - 1) варіант відвідування міст, то це свідчить про те, що і гамільтонових циклів є стільки само. Отже, задача, врешті-решт, зводить­ ся до побудови найкоротшого гамільтонового циклу в повному графі. Як отримати найкоротший гамільтонів цикл?

Нагадаємо ще один алгоритм, результатом роботи якого є підграф, що містить усі вершини заданого графа. Це алгоритм Прима і Краскала, який дає змогу побудувати остовне дерево мінімальної довжини. Таке остовне дерево буде складатися з ребер заданого графа, сумарна довжина яких є мінімальною, буде містити всі вершини заданого графа, однак не буде цик­ лом, а тим більше гамільтоновим (мал. 101, в). Яким же чином перейти від остовного дерева до гамільтонового циклу?

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

162

усіх вершин повинні мати парні значення. Для графа, яким є побудоване мінімальне остовне дерево, ця умова порушена. Тож штучно утворимо ейлеровий граф із остовного дерева, до­ давши до нього ще такі самі ребра. Наприклад, до ребра (3,5) додамо ребро (5,3) і т. д. (мал. 102, а). Довести, що утворений граф є ейлеровим, дуже просто: будь-яке число, а у нашому ви­ падку це степінь вершини, після множення на 2 стає парним.

б)

Мал. 102

Тепер уже можна у графі, яким стало перетворене мінімаль­ не остовне дерево, визначити ейлеровий цикл. Почнемо, на­ приклад, із вершини 1. Застосувавши алгоритм визначення ейлерового циклу, отримаємо таку послідовність ребер: (1,4), (4,1), (1,5), (5,2), (2,5), (5,3), (3,5), (5,1). Як бачимо, до ейлеро­ вого циклу ввійшли всі ребра графа, зображеного на малюнку 102, а, - реальні і фіктивні і двічі всі вершини. На малюнку 102, б позначено послідовність входження ребер перетворено­ го остовного дерева до ейлерового циклу. Зрозуміло, що такий цикл не є гамільтоновим. Спробуємо одержати його з ейлеро­ вого циклу.

Запишемо послідовно всі вершини, які необхідно відвідати, обходячи граф ейлеровим циклом: 1 4 4 1 1 5 5 2 2 5 5 3 3 5 5 1 . Як бачимо, у цій послідовності одні й ті самі вершини входять більш як один раз, що для гамільтонового циклу неприпусти­ мо. Вчинимо примітивно просто: виключимо з послідовності ті вершини, які вже в ній зустрічалися, але при цьому збережемо порядок цих вершин: 1 4 4 і і 5 5 2 й 6 6 3 3 6 £ 1 . Як видно, за­ лишено повторно тільки останню вершину 1 як ту, що завер­ шує цикл обходу графа. У результаті отримано таку послідов­ ність: 14 5 2 3 1.

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

•

Мал. 103

-

Отже, те, що на малюнку 103 зображено гамільтонів цикл, побудований на заданому повному графі (мал. 101, а), сумнівів немає. А от щодо його мінімальної довжини - питання зали­ шається відкритим. Досить багато кроків у послідовності дій зроблено штучно. Запишемо ці дії у вигляді алгоритму і одно­ часно проаналізуємо, якою може бути довжина побудованого гамільтонового циклу.

1. Будуємо остовне дерево мінімальної довжини, сума ребер якого £„,,„.

Коментар. Якби цей граф визначав і гамільтонів цикл, то задача була б одразу розв'язана. Однак остовне дерево ніколи не є циклом! На малюнку 101, в довжина мінімального остовно-

го дерева Lmln = 18.

2. Подвоюємо всі ребра.

Коментар. Довжина нового графа стає вдвічі більшою від довжини мінімального остовного дерева 2Lnin. На малюнку

102,aL = 2Lmin=36.

3. Будуємо ейлеровий цикл, у який входять усі ребра. Коментар. При цьому довжина його становить також 2Lmln.

На малюнку 102,6 Leuler = 2Lmin = 36.

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

Коментар. Повернемося до послідовності вершин в ейлеровому циклі: 1444 - 4 - 5&236633661 . Виключення ребер (4,1), (1,5), що відповідають першій частині виключених вершин, спричинило введення нового ребра (4,5). Як при цьому зміни­ лася довжина цієї частини циклу? За умови існування нерівності трикутника між будь-якими трьома вершинами за­ даного графа виконується умова: L4 5 < L4l + L1 5. Таким чи­ ном, у цій частині побудованого гамільтонового циклу його довжина, порівняно з ейлеровим циклом, зменшилася. Ана­ логічна ситуація повториться і для двох інших виключених груп ребер: L2 з < 1-2,5 + ^5 3' -^з і к ^з,5 + -^5 і- Додавши всі ці нерівності, отримаємо:

•^4,5 + "^2,3 + -^3,1 < ^4,1 + -^1,5 + "^2,5 + -^5,3 + ^3,5 + Lb,V

164