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

ВСТУП

    Актуальність. Задача про комівояжера - 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 Ознаки існування  гамільтонових циклів, шляхів і контурів

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

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

    Всі графи припускаються зв'язними і простими.

    Теорема 1.3.[2, c 310] (Г.Дірак, 1952 р.) Якщо число n вершин графа G не менше трьох і степінь будь-якої вершини x₁ не менше то граф G є гамільтоновим.

    Сформульована ознака Дірака є очевидним наслідком  більш загальної ознаки гамільтоновості, що встановлена у 1960 р. Оре.

    Теорема 1.4[4, c 310] (О. Оре, 1960 р.) Якщо у графі G з n вершинами

    (n > 3) сума степенів будь-яких двох вершин u, v є не меншою, ніж то граф G гамільтонів.

    В свою чергу, ознаку гамільтоновості  Оре можна вивести з більш  «пізніх» ознак Л. Поша і В. Хватала.

    Теорема 1.4[4, c 310] (В. Хватал, 1972 р.) Нехай для упорядкованої за зростанням послідовності степенів вершин

    графа G виконані імплікації тоді G — гамільтонів граф.

    Існують ознаки гамільтоновості графів, що є похідними від деяких інших графів, зокрема, для степенів G^p і реберних графів L(G). Bершини реберного (або дуального) графа L(G) знаходяться у взаємно однозначній відповідності з ребрами графа G, а дві вершини у L(G) з'єднані ребром, якщо і тільки якщо відповідні ребра у G суміжні. Степінь G^p графа G = (X, У) тут розуміється як граф з тією ж множиною вершин X, в якій вершини з'єднані ребром (суміжні), якщо і тільки якщо у G відстань між не більше р: у графі G. Наприклад, якщо C₅ — цикл з п'ятьма вершинами і п'ятьма ребрами, то (С₅)² = К₅ — повний п'ятивершинний граф. Цей приклад і саме визначення G^p підказує, що у будь-якого зв'язного графа G деякий степінь G^p повинен бути гамільтоновим графом. Із гамільтоновості степеня G^p виходить гамільтоновість G^p+1.

    Теорема 1.5[4, c 311] (Д. Караганіс, 1968 р.)

    Для зв'язного графа G з числом вершин степінь G³ є гамільтоновим графом.

    Теорема 1.6[4, c 311] (Г. Флейшнер, 1971 р.)

    Якщо G — двозв'язний граф з числом вершин , то G² — гамільтонів граф.

    Теорема 6.7[4, c 311] (Ф. Харарі, С. Неш-Вільямс, 1965 р.)

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

    Наслідок. Якщо граф G або ейлерів, або гамільтонів, то реберний граф L(G) гамільтонів.

    Теорема 6.17[4, c 312] (Кеніг)

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

    В самому несприятливому випадку (повний граф і фатальна, невдача) оптимальний  гамільтонів ланцюг або цикл у  графі G, що починається у заданій вершині x_i, можна побудувати шляхом різних перестановок на множині решти вершин {х₂, х₃, х_n}. Отже, обчислювальна складність задач Гамільтона і комівояжера має порядок (n - 1)! Внаслідок такої значної обчислювальної складності для розв'язку задачі комівояжера створено багато алгоритмів, як автономних, так і таких, що базуються на інших оптимізаційних алгоритмах, — потокових, що будують мінімальний остів тощо. При цьому точні алгоритми, що гарантують одержання маршруту комівояжера у будь-якому випадку, є трудомісткими і застосовні до мереж не дуже високої розмірності. Наближені алгоритми у більшості випадків застосовні до більш громіздких мереж, однак іноді призводять до неоптимального маршруту. Розглянемо далі алгоритми для розв’язання задачі комівояжера.

    1.4 Метод гілок та меж

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

    Основна ідея методу гілок та меж полягає в тому, що спочатку будують нижню межу φ довжин множини маршрутів Z. Потім множина маршрутів розбивається на дві підмножини таким чином, щоб перше підмножина складалася з маршрутів, що містять деяку дугу (i, j), а інша підмножина не містило цієї дуги. Для кожної з підмножин визначаються нижні межі по тому ж правилу, що і для початкової множини маршрутів. Отримані нижні межі підмножин і виявляються не менше нижньої межі множини всіх маршрутів, тобто φ(Z)≤ φ( ), φ(Z) ≤ φ( ).

    Порівнюючи нижні межі φ( ) і φ( ), можна виділити ту, підмножину маршрутів, яка з більшою ймовірністю містить маршрут мінімальної довжини.

    Потім одна з підмножин або за аналогічним правилом розбивається на дві нових і . Для них знову відшукуються нижні межі φ ( ), і φ ( ) і т.д. Процес розгалуження продовжується до тих пір, поки не відшукається єдиний маршрут. Його називають першим рекордом. Потім переглядають обірвані гілки. Якщо їх нижні межі більше довжини першого рекорду, то задача вирішена. Якщо ж є такі, для яких нижні межі менше, ніж довжина першого рекорду, то підмножина з найменшою нижньою межею піддається подальшому розгалуження, поки не переконаємося, що вона не містить кращого маршруту. Якщо ж такий знайдеться, то аналіз обірваних гілок проводиться щодо нового значення довжини маршруту. Його називають другим рекордом. Процес розв’язання закінчується, коли будуть проаналізовані всі підмножини.

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

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

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

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

    Множину маршрутів, які не включають дугу (i, j) одержуємо шляхом заміни елементу С_ij на нескінченність.

    Використовуючи наведений алгоритм, розв’яжемо приклад:

    Комівояжер повинен об'їздити 6 міст. Для того щоб скоротити витрати, він хоче побудувати такий маршрут, щоб об'їздити всі міста точно по одному разу і повернутися у вихідний з мінімум витрат. Початковим містом, виберемо місто A. Витрати на переміщення між містами задані наступного матрицею (табл. А.1): 

«Таблиця 1.1 Платіжна Матриця»

     Розв’язок

     Для зручності викладу, нижче, в платіжній матриці, замінимо імена міст (A,B, ...,F) номерами відповідних рядків і стовпців (1,2,...,6). Знайдемо нижню межу довжин для множини всіх маршрутів. Віднімемо з кожного рядка число, рівне мінімальному елементу цього рядка, далі віднімемо з кожного стовпця число, рівне мінімальному елементу цього стовпця, і таким чином зведемо матрицю по рядках і стовпцях.

     Мінімум по рядкам: r₁=15, r₂=1, r₃=0, r₄=16, r₅=5, r₆=5.

     Після віднімання маємо матрицю(табл. 1.2): 
 
 
 

«Таблиця 1.2. Платіжна Матриця»

     Мінімум по стовпчиках: h₁=5, h₂=h₃=h₄=h₅=h₆

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

«Таблиця 1.3. Платіжна Матриця»