Задача коммивояжера и её реализация

 

ВСТУП

 

    Актуальність. Задача про комівояжера - traveling salesman problem (TSP, ЗК) - є NP-складною задачею дискретної оптимізації. Для неї не знайдено, і можливо, не існує швидких, поліноміальних алгоритмів. На графах вона формулюється наступним чином: потрібно знайти гамільтонів цикл найменшої вартості у зваженому графі. Тобто, вийшовши з стартової вершини, відвідати кожну вершину графа рівно один раз і повернутися в початкову по найкоротшому шляху. Пошук точних і наближених розв’язків задачі комівояжера залишається актуальним і з теоретичної, і з практичної точок зору. 

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

    Програмні коди, призначені для вирішення на оптимальність задачі комівояжера, за останні 30 років розвинулися від  вирішення задач розмірності  100 до 10 000[11,с 737-749].

    Серед застовувань ЗК, що зустрічаються в літературі[2,80], можна відзначити:

    • оптимізацію в мережах;

    • оптимізацію маршрутів;

    • програми в кристалографії;

    • управління роботами;

    • обробку друкованих плат;

    • дослідження ДНК.

    «Містами» у різних задачах можуть виступати як фізичні об'єкти, так і процеси, і інші сутності.

    Мета. Ознайомлення з постановкою задачі комівояжера на графах та детальне вивчення різних алгоритмів розв’язання задачі комівояжера.

    Об’єкт. Задача комівояжера та алгоритми її розв’язку.

    Предмет. Розробка середовища та програмна реалізація деяких алгоритмів розв’язку задачі комівояжера

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

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

    РОЗДІЛ  І. ЗАДАЧА КОМІВОЯЖЕРА ТА ДЕЯКІ АЛГОРИТМИ ЇЇ РОЗВ’ЯЗКУ

    1.1 Постановка задачі  комівояжера

 

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

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

    Існує ще одна постановка, в якій додатково до попередньої задачі треба, щоб кожний пункт обслуговування комівояжер відвідував тільки один раз. Очевидно, в такій постановці задача комівояжера не завжди має розв'язок, а якщо має, то маршрут комівояжера в графі G є найкоротшим гамільтоновим ланцюгом або циклом. У зв'язку із сказаним будемо називати останню постановку «гамільтоновою» задачею комівояжера (на відміну від «загальної»). Якщо шукається замкнений маршрут, то для розв'язності «гамільтонової» задачі комівояжера необхідно і достатньо, щоб граф G був гамільтоновим, для незамкненого гамільтонового маршруту — граф G повинен бути трасовним.

    В орієнтованому зваженому графі G зустрічається також задача пошуку загального орієнтованого маршруту комівояжера — найкоротшого орієнтованого маршруту, що містить всі вершини графа, і відповідно, орієнтованого шляху або контуру комівояжера (що містить кожну вершину один раз). Замкнений орієнтований (або неорієнтований) маршрут комівояжера при загальній негамільтоновій постановці задачі не обов'язково є гамільтоновим контуром (відповідно гамільтоновим циклом).

    

    Рис. 1.1. (a, b), (b, а), (а, с), (с, а) – найкоротший замкнений маршрут 

    Наприклад, граф G на рис. 1.1. має один гамільтонів контур і кілька гамільтонових циклів, всі їх довжини дорівнюють 24, і кожний містить три

    дуги. Однак найкоротшим  замкненим маршрутом комівояжера (непростим)      є замкнений  маршрут з чотирма дугами (a, b), (b, а), (а, с), (с, а), який проходить через кожну вершину двічі і має довжину 8.

    Гамільтонів контур (або цикл) є розв'язком загальної задачі комівояжера у випадку, коли виконується теорема:

    Теорема 1.1[2, c 315]. Якщо функція d(x, v) ваг (довжин) ребер (або дуг) між парами вершин х, v у графі G = (X, Y) з числом вершин n = |Х| 3 задовольняє нерівність трикутника: 

    d(x, v) < d(x, z) + d(z, v), Vz * x, z Ф v, z є X,     (1.1) 

      та існує розв'язок загальної задачі комівояжера, то існує також розв'язок «гамільтонової» задачі комівояжера.

    Умова трикутника означає, що у графі  G довжина «однокрокового» шляху (ланцюга) між вершинами х і v, скінченна або нескінченна, не перевершує довжини будь-якого «двохкрокового» (х, v)-шляху ((х, v)-ланцюга) з однією проміжною вершиною.

    1.2 Гамільтонові цикли  і шляхи

 

    Гамільтоновим циклом у графі G = (X, У) називається простий цикл   

    Q = (X, У₀), що містить всі вершини графа, незалежно від того, чи є G орієнтованим. Вимога простоти циклу є принциповою: за гамільтоновим циклом Q можна обійти всі вершини х графа G, відвідуючи кожну проміжну (тобто не початкову і не кінцеву) вершину тільки один раз. Сам граф G, в якому існує гамільтонів цикл, називається гамільтоновим графом. Зрозуміло, що гамільтонів граф є зв'язним і, більш того, двозв'язним, оскільки між кожною парою вершин існує не менш ніж два різних простих ланцюга. При будь-якому повний простий граф К_n є гамільтоновим. Повний двочастковий граф К_р,р з рівнопотужними частками (однокольоровими множинами) також гамільтонів, див. К_2,2, K_3,3, К₅ на рис. 1.2.

      

    Рис. 1.2. Гамільтонові графи К_2,2, K_3,3, К₅ 

    Безпосередньо перевіряється, що графи G₁, G₂, G₃ на рис. 1.2. не містять гамільтонових циклів і, отже, не є гамільтоновими графами. Однак всі ці графи містять гамільтонові ланцюги. Гамільтоновим ланцюгом у графі

    G = (X, У) називається простий ланцюг Z = (X, У_z), що містить всі вершини графа. Граф, що має гамільтоновий ланцюг, називається трасовним. Гамільтоновим ланцюгом у графі G₁ є ланцюг 23 514, у графі G₂ — ланцюг 623 451, у графі G₃ — ланцюг 643 215, а також 264 315. Відзначимо, що граф G₃ не є двозв'язним, так що для трасування вимога двозв'язності графа G зайва. 

    

    Рис. 1.3. Гамільтонові ланцюги 

    Теорема 1.2.[2, c 306] Якщо двозв'язний граф не містить гамільтонового циклу, то він містить тета-підграф.

    Доведення.  Нехай Q — простий цикл максимальної довжини у нашому графі G = (X, У). За умовою цикл (3 не може бути гамільтонавим, тому число його вершин повинне бути  менше, ніж n = |Х|. Легко переконатися, що при

    n = 3 або n = 4 двозв'язний простий граф G є гамільтоновим, тому n > 5. Число вершин Х_q циклу Q (і ребер) не менше 4: |Х_q| > 4. Дійсно, якщо у двозв'язному графі G є цикл довжини 3, то до нього можна додати ланцюг з новою проміжною вершиною так, щоб виник простий цикл довжини більшої, ніж 3 (див. рис. 1.2, G₁). Існує таке ребро (х, v) У, що X Q, v У\Q. Позначимо через а, b вершини циклу Q, суміжні з вершиною х (див. рис. 1.3). Оскільки цикл Q максимальний, то вершина c не суміжна ані з вершиною а, ані з вершиною b: у протилежному випадку можна побудувати цикл більшої довжини.

    Видалимо  з графа G вершину х разом з інцидентними їй ребрами, до множини яких належить і ребро (х, v). В графі, що залишився, для кожної вершини w на циклі Q (крім x) існує простий (v, w) — ланцюг Р_w, з'єднуючий вершини w і v. Серед всіх таких ланцюгів Р_w(w Q, w х) оберемо найкротший ланцюг Р_с, з'єднуючий вершину v з деякою вершиною с Q. Очевидно, і , інакше цикл Q не був би максимальним простим циклом у графі G. Ланцюг Р_с не містить вершин циклу Q, відмінних від с, бо у протилежному випадку Р_с не є найкоротший шлях із всіх ланцюгів Р_w. Побудуємо у графі G підграф G₀ = , об'єднуючий цикл Q, ребро і ланцюг Р_с разом з інцидентними вершинами. Зрозуміло, що G₀ є тета-граф, у якому вершини третього степеня х і с з'єднуються трьома різними простими ланцюгами. 

    

    Рис. 1.4. Граф, що містить тетапідграф 

    Зауваження. Існування тета-підграфа є лише необхідною умовою для негамільтоновості двозв'язного графа. В двозв'язному графе К_3,3 рис. 1.2 існують тета-підграфи, однак К_3,3 — гамільтонів. Аналогічно граф G₂ на рис. 1.2 також має гамільтонів цикл (6, 2, 3, 1, 5, 4, 6) і одночасно має тетапідграф з трьома ланцюгами (2, 3, 4), (2, 6, 4), (2, 1, 5, 4) між вершинами 2, 4 третього степеня. З іншого боку, вимога двозв'язності у теоремі 1.1 істотна: негамільтонів граф G₃ на рис. 1.1 однозв'язний і не містить жодного тета-підграфа.

    Постановка  задачі про гамільтонів цикл з однократним проходженням всіх вершин графа може виглядати схожою або в якому-небудь сенсі двоїстою до постановки задачі про ейлерів цикл з однократним проходженням всіх ребер графа. Однак це не так. Задача про гамільтонів цикл, на жаль, не має на сьогодні ані повного теоретичного розв'язку, ані задовільного алгоритму відшукання циклу для не дуже маленьких n. Історично першим розглядав задачу обходу простим циклом всіх вершин графа відомий ірландський математик У. Гамільтон у 1859 р. Він побудував низку таких циклів на ребрах додекаедра — правильного опуклого багатогранника з 20 вершинами і 12 п'ятикутними гранями. Плоске зображення додекаедра, яке можна трактувати як його проекцію на одну «розтягнуту» грань, зображено на рис. 1.4. Один з гамільтонових циклів зображено на рисунку жирною ламаною. Гамільтон трактував свою задачу у вигляді гри «Навколосвітня подорож», у якій пропонується обрати маршрут відвідування двадцяти міст на земній кулі, рухаючись по дорогах-ребрах додекаедра. Він навіть продав свою гру торговцеві іграшками за 25 гіней. 

    

    Рис. 1.5. Плоске зображення додекаедра 

    В орієнтованому графі поряд з  гамільтоновим циклом або гамільтоновим  ланцюгом часто доводиться шукати гамільтонів контур або шлях, обхід яких здійснюється тільки за напрямками дуг. Гамільтонів шлях — це простий -шлях у графі G, що містить всі вершини графа. Якщо       , то це — гамільтонів контур. Будь-який гамільтонів шлях є гамільтонів ланцюг, зворотне, взагалі кажучи, неправильно. Графи К_2,2, і К₅ на рис. 1.2 є гамільтоновими без врахування орієнтації дуг, однак вони не мають гамільтонових контурів. При цьому граф К₅ має гамільтонів шлях, у якому послідовність проходження вершин є 1, 4, 5, 2, 3. В графі К_2,2 рис. 1.1 гамільтонів шлях відсутній.

    Подібна ситуація неможлива у симетричному графі: кожному гамільтоновому ланцюгу (циклу) неорієнтованого графа відповідає пара протилежно спрямованих гамільтонових шляхів (контурів) у відповідному орієнтованому симетричному графі.

    Застосування  гамільтонових ланцюгів і шляхів досить численні. В теорії розкладів окремі процедури (дії) зображуються

    1.3 Ознаки існування  гамільтонових циклів, шляхів і контурів

 

    Одержання умов гамільтоновості графів є популярною задачею, до кінця не розв'язаною на сьогодні. Популярність «живиться» не тільки прикладною цінністю умов, але і рідкісною простотою та природністю самої постановки задачі про гамільтонів цикл, що не вимагає попередніх математичних знань і символьних позначень у формулюванні.