Материал: 62_201
Це, загалом, означає, що заміна ребер тільки покращила підсумковий результат. На малюнку 103 Lrez = 29.
5. Завершення алгоритму.
Коментар. У результаті для повного графа, що описує задачу про комівояжера, побудовано гамільтонів цикл, довжину яко го можна оцінити так: Lrez < 2Lmin, тобто довжина гамільтонового циклу не перевищує подвоєну довжину мінімального остовного дерева.
Визначена оцінка результату зверху. А знизу цією оцінкою може бути лише довжина невідомого нам мінімального гамільтонового циклу. У найкращих випадках можна буде саме його й отримати, застосувавши алгоритм Ейлера, але у більшості задач про комівояжера буде отримано лише приблизний розв'язок, більший за мінімальний, але точно менший за по двоєну довжину мінімального остовного дерева.
а) |
б) |
в) |
г) |
|
Мал. 104 |
|
На малюнку 104 зображено гамільтонові цикли у заданому |
повному графі. Як бачимо, гамільтонів цикл найменшої дов жини зображений на малюнку 104, в і його довжина стано вить 29. У результаті виконання алгоритму Ейлера отримано такий самий результат. Але це та сама ідеальна випадковість, про яку йшлося вище. Однак найчастіше при великій кількості міст можна отримати лише наближений розв'язок конкретної задачі про комівояжера, хоча у таких випадках і це досить не поганий результат.
Реалізація основної частини описаного алгоритму мовою програмування може бути запропонована так:
165
kruskal; {Визначення остовного дерева мінімальної довжини;} і := 1; {результат роботи процедури kruskal міститься парами вершин у масиві krus.) while І < к do {Занесення ребер, що увійшли до остовного дерева у масив h]
begin
h[krus[i], krus[i + 1]] := 1; h[krus[i + 1], krus[i]] := 1 ;{з урахуванням їх подвоєння.}
inc(i, 2) |
|
|
end; |
|
|
euler; |
{Визначення ейлерового циклу.} |
|
s : = [ ] ; j : = 1 ; |
|
|
for і := rez_top downto 1 do |
|
{Виключення вершин,} |
if not (eul[i] in s) then |
{що повторюються в ейлеровому циклі,} |
|
begin |
|
{і створення масиву} |
І hamil[j] :=eul[i]; s :=s + [eul[i]]; inc(j); {з вершинами гамільтоновогоциклу.} |
||
end; |
|
|
hamil[j] := hamil[1]; |
{Замкнення гамільтонового циклу.} |
|
L:-0; |
|
|
for і := 1 to j - 1 do |
{Створення вихідного файлу.} |
|
begin |
|
{Визначення ребер} |
write(f_Out, '(', hamil[i], ',', hamil[i + 1], ') '); |
{гамільтоновогоциклу.} |
|
L := L + d[hamil[i], hamil[i + 1 ]] {Визначення довжини гамільтонового циклу.} end;
writeln(fout);
writeln(f out, 'Minimum way: ', L);
Слід зауважити, що процедури kruskal та euler, як уже відо мі, для використання у даному алгоритмі потребують деяких модифікацій.
Оцінка ефективності роботи алгоритму є досить непогана при можливому досить непоганому отриманому результаті. Адже алгоритм складається із послідовного використання вже відо мих алгоритмів. Нагадаємо їх оцінки: побудова мінімального остовного дерева - 0(п + т); подвоєння ребер остовного дерева - 0(п), оскільки ребер в остовному дереві (п - 1); побудова ейлеро вого циклу - 0{т); утворення гамільтонового циклу з ейлерово го - 0(2п), оскільки до нього можуть увійти всі вершини по два рази. Склавши всі ці оцінки, отримаємо 0(4п + 2т)« 0(п + т).
Для тестування алгоритму Ейлера наближеного розв'язан ня задачі про комівояжера раціональнішим буде використання тих тестів, на яких перевірялася коректність роботи повнопереборного алгоритму.
Метод гілок і границь
Алгоритм, який реалізується методом гілок і границь, можна характеризувати як евристичний. У чому полягає евристика, по бачимо, розглядаючи безпосередньо цей алгоритм. Але наперед можна сказати, що, застосовуючи певні міркування, логічні вис новки, можна дещо скоротити кількість повних переборів під
166
час розв'язування NP-повних задач. Саме це і є основою евристи ки: здогадки, міркування, висновки і, як результат цього, деякі удосконалення знаходження розв'язку поставленої задачі.
Розглянемо таблицю суміжності Ct • для прикладу задачі про комівояжера із попереднього алгоритму (мал. 105, а). Граф, що описує задачу про комівояжера, є повним неорієнтованим і зва женим. Саме тому таблиця суміжності є симетричною відносно головної діагоналі. Оскільки елементами таблиці є значення вартості відповідного ребра графа, а вони можуть бути і нульо вими, тому позначимо Си символами «-», що означатиме відсутність ребра від вершини і до вершини і. Надалі відсут ність ребер у графі позначатимемо так само.
Ми знаємо точну відповідь на поставлену задачу. А саме шлях комівояжера у даному випадку оцінюється так: 71>3 + 53 2 + 32 5 + + 85 4 + 64д = 29. На малюнку 105, а елементи таблиці, що утво рюють шлях комівояжера, виділено темним кольором, а значен ня - півжирним шрифтом. Порівнявши кожне із цих значень у своєму рядку і стовпці з іншими значеннями, можна побачити, що вони не завжди є найменшими, але не є і найбільшими.
|
1 |
2 |
3 |
4 |
5 |
тіп |
|
|
1 |
2 |
3 |
4 |
5 |
|
|
|
1 |
2 |
3 |
4 |
5 |
|
|
|
•6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
- |
8 |
5 |
5 |
|
1 |
- |
3 |
:І< |
1 |
0 |
|
|
1 |
- |
3 |
1 |
0 |
0 |
||
2 |
8 |
- |
5 |
10 |
3 |
3 |
|
2 |
5 |
- |
2 |
7 |
0 |
«0 |
|
2 |
5 |
- |
1 |
6 |
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
3 |
7 |
|
- |
12 |
4 |
4 |
|
3 |
3 |
1 |
- |
8 |
0 |
|
3 |
3 |
.'£і |
- |
7 |
0 |
|
5 |
|
§• |
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
4 |
в |
10 |
12 |
- |
8 |
6 |
|
4 |
|
4 |
6 |
- |
2 |
|
4 |
|
4 |
5 |
- |
2 |
|
|
# ' |
а |
|
# |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
К |
|
|
|
|
|
|
|
5 |
5 |
3 |
4 |
8 |
- |
3 |
|
5 |
2 |
0 |
1 |
5 |
- |
|
5 |
2 |
0 |
0 |
>4І- |
||
|
О |
|
|||||||||||||||||||
Сума |
приведення |
21 |
|
тіп |
0 |
0 |
1 |
1 |
0 |
2 |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Як можна тлумачити інформацію, що міститься у першому рядку таблиці? Нехай це буде вартість виїзду з міста під номе ром 1. Тоді, відповідно, інформація у першому стовпці - це вартість в'їзду до міста під номером 1. Оскільки вартість - це одиниця відносна, тобто її можна для всіх на один і той самий коефіцієнт зменшити або збільшити, то вчинимо так само й з елементами нашої таблиці.
Розглянемо перший стовпець. Якщо при в'їзді до міста з но мером 1 відповідно до встановленої платні, нехай це буде мито на ввезення певної кількості товару, комівояжер, ввозячи товар з міста 2, платить 8 одиниць, з міста 3 - 7 і т. д., то можна цю платню всім в'їжджаючим до даного міста умовно зменшити на однакове відповідне значення. При цьому відносність платні при в'їзді до міста і не зміниться. Залишається тільки за пам'ятати значення, на яке зменшено платню за в'їзд у кожне
167
місто. Назвемо це значення константою приведення і позначимо для кожного рядка у додатковому стовпці (мал. 105, а). Просу - мувавши всі п'ять констант приведення, отримаємо їх суму, яка для рядків таблиці становить 21. Результат приведення рядків таблиці показано на малюнку 105, б. Позиції шляху комівояже ра на ній також виділено темним кольором. Як бачимо, якщо просумувати виділені клітинки на малюнку 105, б, то саме на 21 зменшилась вартість об'їзду комівояжером усіх міст.
Тепер виконаємо ті самі дії зі стовпцями таблиці, зображе ної на малюнку 105, б. Константи приведення її по кожному стовпцю визначені у додатковому нижньому рядку. Сума при ведення по стовпцях становить 2, а результат приведення представлений на малюнку 105, в.
Таким чином, загальна сума приведення таблиці як по ряд ках, так і по стовпцях становить 23. Саме на таке число змен шено реальну вартість об'їзду всіх 29 міст завдяки виконаним діям. Можна ще інакше сформулювати цю думку: вартість об'їзду, яка буде результатом розв'язку задачі зі значеннями із таблиці (мал. 105, в), необхідно буде збільшити на 23, щоб отримати реальний результат.
Але наша задача полягає у тому, щоб, користуючись інфор мацією із таблиці (мал. 105, в), отримати правильний розв'я зок задачі про комівояжера.
Продовжимо подальші евристичні міркування. Якщо не бу ло б відомо точного розв'язку поставленої задачі, то, аналізую чи таблицю (мал. 105, в), хотілося б знайти мінімальний гамільтонів цикл, а таким, зрозуміло, може бути лише той, що скла дається з нульових значень. Тобто його оцінка становитиме 0. Враховуючи сумарне значення приведення початкової таблиці, його реальна оцінка становитиме 23. Отже, можна стверджува ти, що отримати розв'язок задачі про комівояжера з результа том, меншим за 23, неможливо. Це і є нижньою границею оцін ки майбутнього розв'язку задачі, і його отримано у результаті приведення заданої таблиці суміжності по рядках і стовпцях.
Наступні кроки алгоритму будуть пов'язані з побудовою де рева розв'язків, з одночасним відсіканням тих його гілок, що ведуть до неоптимальних результатів. Тепер стає зрозумілим, чому метод носить назву «гілок і границь».
До визначення нижньої границі задачі ми підійшли з жа дібними міркуваннями, розглянувши лише варіант існування розв'язку тільки на нульових значеннях таблиці (мал. 105, в). Однак це не завжди може бути саме так, і наведений приклад у цьому переконує. Встановлена границя виконує роль нижнього бар'єра, і можна переконатися лише у тому - результат розв'яз ку задачі буде таким або більшим за це значення.
168
Звичайно, дуже хотілося б побудувати гамільтонів шлях, використовуючи тільки ребра з нульовими значеннями, але та ка жадібність може відвести вбік від правильного результату. Тому спробуємо зробити один крок уперед і оцінити шанси у разі, коли буде обрано інший варіант формування гамільтонового циклу.
Розглянемо нульовий елемент таблиці (мал. 105, в), який знаходиться у позиції [1,4]. Якщо для формування результую чого циклу вибрати ребро (1,4), то нижня оцінка вартості тако го вибору залишиться незмінною, тобто 23. Це означатиме, що здійснюється виїзд з міста 1 і в'їзд у місто 4 з платнею 0. Роз глянемо рядок з номером 1, де міститься інформація, в які міста і за яку платню можна в'їхати з міста 1. Виявляється, що можна з міста 1 в'їхати і в інше місто з платнею, близькою до цієї. Таким містом у рядку 1 є місто з номером 5. Вартість пе реїзду туди так само дорівнює 0. Поки що заміна міста в'їзду 4 на місто 5 не змінила нижньої межі загальної вартості 23, хоча
ізмінює множину ребер, які формують результуючий цикл.
Зтакими самими міркуваннями підійдемо і до питання в'їзду до міста 4, розглянувши стовпець з номером 4. З нього видно, що у місто 4 можна в'їхати за нульову платню тільки з міста 1, а з тих міст, що залишилися, найдешевший в'їзд вар тістю 4 можливий лише з міста 5. Тому найдешевша альтерна тива для в'їзду у місто 4 місту 1 буде місто 5 і коштуватиме во на 4. Таким чином, включення ребра (1,4) у шуканий цикл коштуватиме 0, а відмова від його включення - щонайменше 4. Величину 4 назвемо вартістю ризику для ребра (1,4). Оскільки треба буде розглядати всі можливі варіанти формування шука ного циклу, то при розгляді варіанта з ребром (1,4) нижня гра ниця платні 23 не збільшуватиметься, а у варіанті виключення цього ребра із розгляду збільшиться на 4 і становитиме 27.
Визначимо вартості ризику для всіх Сл• = 0 таблиці (мал. 105, в). Насправді це зробити дуже просто: для кожного елемента таб лиці зі значенням 0 необхідно знайти суму мінімумів у рядку і та стовпці j, не враховуючи сам цей елемент (мал. 106, а). Найбільший ризик 4 мають ребра (1,4) і (4,1). Виберемо будьяке з них, наприклад ребро (1,4).
Існує два варіанти подальших дій: включити це ребро до шу каного циклу, при цьому фактично виключивши його із по дальшого пошуку, або не включати і намагатися знайти якийсь інший шлях побудови циклу. Найменша вартість першого варіанта залишається 23, а другого - на 4 більша за рахунок вартості ризику, при якій не враховується це ребро як складо ва результуючого гамільтонового циклу. Окрім цього, у пер шому варіанті надалі розглядатиметься таблиця (мал. 105, а) без 1-го рядка і 4-го стовпця, оскільки виїзд з міста 1 і в'їзд у
169