Застосування методу поступового покращення для розв’язання задачі комівояжера

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

Для і=1, 2,..., n-1 і j=i+1,...,n визначити, чи зменшується довжина гамільтонового контуру під час переставляння в заданій вище послідовності обходу вершин пари вершин х_і і х_j. Якщо це призводить до зменшення довжини гамільтонового контура, то здійснити таке переставляння в порядок обходу вершин графу G. Повторювати цей процес доти, доки за допомогою попарних переставлянь досягається зменшення довжини гамільтонового контура.

Переставляння вершин "і" і "j" означає заміну дуг

(х_i_-1, x_i), (x_і, x_i₊₁), (x_j_-1, x_j), (x_j, x_j₊₁)

дугами

(х_i_-1, x_j), (x_j, x_i₊₁), (x_j_-1, x_i), (x_i, x_j₊₁)

Процес попарних переставлянь повинен бути скінченним, оскільки

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

- кожного разу формується нова послідовність обходу, відмінна від попередніх.

При цьому можна отримати новий гамільтоновий контур, який має строго меншу довжину, ніж попередній.

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

Задачі і алгоритми

Пошук в ширину

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

Шляхи мінімальної сумарної ваги в зваженому графі

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

Класичним алгоритмом рішення даної задачі є алгоритм Дейкстри.

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

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

Алгоритм Дейкстри

Дано: непустий зважений граф G=(V,E) з ненегативними вагами ребер (дуг). Вимагається знайти найкоротший шлях від s до t (s ¹ t).

Ініціалізація:

1. всім вершинам v_i приписується мітка - дійсне число: d(s)=0, d(v_i)=+_ для всіх v_i¹s;

2. мітки всіх вершин, окрім s, вважаються тимчасовими, влучна s - постійної;

3. вершина s оголошується поточною (c:=s);

4. всі ребра (дуги) вважаються непоміченими.

Основна частина:

1. для всіх вершин u_j, інцидентних поточній вершині с, мітки яких є тимчасовими, перераховуємо ці мітки по формулі: d(u_j):=min{d(u_j)_,d(c)+Weight(с,u_j)} (*), де (с,u_j) - ребро (дуга), сполучаюча вершини с і u_j, а Weight(с,u_j) - її вага; за наявності кратних ребер вибирається ребро з мінімальною вагою;

2. якщо мітки всіх вершин є постійними або рівні +_, то шлях не існує; ВИХІД("немає рішення");

3. інакше знаходимо серед вершин з тимчасовими мітками (серед всіх таких вершин, а не тільки тих, чиї мітки змінилися в результаті останнього виконання кроку (1)!) вершину x з мінімальною міткою, оголошуємо її мітку постійної, позначаємо ребро (дугу) (c',x), таке, що d(x)= d(з')+Weight(c',x), де c'=с або с' - вершина, що була поточною на одному з попередніх кроків (c'=с, якщо на кроці (1) при u_j=x реалізувалася друга частина формули (*)), і робимо цю вершину поточної (c:=x);

4. якщо c=t, то знайдений шлях довжини d(t), який можна відновити таким чином: це той шлях між s і t, який складається тільки з помічених на кроці (3) ребер (дуг) (можна довести, що він існує і єдиний); ВИХІД("рішення знайдене");

5. інакше переходимо на крок (1).

Алгоритм Дейкстри не завжди знаходить правильне рішення у разі довільних вагів ребер (дуг) графа. Наприклад, для орграфа, зображеного на малюнку, алгоритм Дейкстри знайде маршрут s(s,t) t довжини 1 між вершинами s і t, а не мінімальний маршрут довжини 2+(-2)=0, проходить через третю вершину графа.

Приклад орграфа, для якого непридатний алгоритм Дейкстри.

Найкоротше остовне дерево

Задача: знайти найкоротше остовне дерево зваженого графа.

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

Алгоритм Краскала

Алгоритм побудови остових дерев широко використовують у задачах пошуку оптимальних рішень.

Розглянемо неорієнтований граф G(X, Y), в якому напрямки дуг не задаються. Нехай кожному ребру (x, y) цього графа відповідає вага a(x,y).

Побудова остовного дерева здійснюється при розгляді ребер вхідного графу в довільному порядку. Під час кожного перегляду стосовно вихідного ребра вирішується буде чи не буде воно включене в остовне дерево. Алгоритм можна представити як процес розфарбування ребер. При цьому один колір (блакитний) використовується для розфарбування ребер, які включені в остовне дерево, а інший (зелений) – для розфарбування ребер, яких не включають в це дерево. В алгоритмі під час перегляду ребра здійснюється лише перевірка того, чи не створює дане ребро в сукупності з ребрами, вже включеними в дерево, цикл. Якщо результат перевірки підтверджується (тобто ребро утворює цикл), то розглянуте ребро не включається в дерево (фарбується в зелений колір). Інакше це ребро включається в дерево (фарбується в блакитний колір).

Перевірка чи розглянуте ребро утворює цикл з ребрами, що вже включені в остовне дерево, здійснюється так:

- ребра, включені в дерево складають граф, що мають одну або більше компонентів зв’язності;

- вершини, що належать окремій компоненті зв’язності, об’єднуються в сукупність, яка в даному алгоритмі називатиметься «букетом»;

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

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