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

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

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

    Теорема 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 р.) Нехай для упорядкованої за зростанням послідовності степенів вершин

                                 

              (1.1)

    графа 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	C	D	E	F
A	∞	26	42	15	29	25
B	7	∞	16	1	30	25
C	20	13	∞	35	5	0
D	21	16	25	∞	18	18
E	12	46	27	48	∞	5
F	23	5	5	9	5	∞

 

     Розв’язок

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

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

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

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

	1	2	3	4	5	6
1	∞	11	27	0	14	10
2	6	∞	15	0	29	24
3	20	13	∞	35	5	0
4	5	0	9	∞	2	2
5	7	41	22	43	∞	0
6	18	0	0	4	0	∞

 

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

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

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

	1	2	3	4	5	6
1	∞	11	27	0	14	10
2	1	∞	15	0	29	24
3	15	13	∞	35	5	0
4	0	0	9	∞	2	2
5	2	41	22	43	∞	0
6	13	0	0	4	0	∞