А Ю Левченко - Декомпозиція загальної задачі комівояжера та наближений метод її розв'язку - страница 1

Страницы:
1  2  3 

ВІСНИК ЖДТУ № 3 (58)

Технічні науки

ІНФОРМАТИКА

УДК 681.3

А.Ю. Левченко, асист.

Житомирський державний технологічний університет

ДЕКОМПОЗИЦІЯ ЗАГАЛЬНОЇ ЗАДАЧІ КОМІВОЯЖЕРА ТА НАБЛИЖЕНИЙ МЕТОД ЇЇ РОЗВ'ЯЗКУ

(Представлено д.т.н., проф. Панішевим А.В.)

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

Вступ. Загальна задача комівояжера (ЗЗК) формулюється таким чином. Заданий неорієнтований граф

H = (V, U) з n вершинами та функція ваг його ребер d : U    Z0 , Z0 - множина цілих невід'ємних

чисел. Потрібно знайти найкоротший замкнений маршрут, який пов'язує всі вершини V . Очевидно, у будь-якому зв'язному графі ЗЗК завжди має розв'язок [1].

Єдиний відомий на даний час автору алгоритм точного розв'язку ЗЗК розглядається в [2]. Він виконується в дві стадії. Перша стадія базується на поліноміальному зведенні ЗЗК до симетричної задачі комівояжера (СЗК) за допомогою алгоритму пошуку найкоротшого багатополюсного шляху, наприклад, за допомогою алгоритму Флойда-Уоршала. На другій стадії виконується класичний метод Літла, який характеризується великою трудомісткістю і є непридатним для графів із цікавою з точки зору практики розмірністю.

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

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

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

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

Вершина, видалення якої перетворює зв'язний граф у незв'язний, називається точкою зчленування, а ребро з такою ж властивістю - мостом. Зв'язний, непустий, підграф графа H, який не має точок зчленування, зветься блоком. Точка зчленування є загальною вершиною двох та більше блоків [3].

Всі точки зчленування та мости в графі Н можна встановити за час O (V + U ) процедурою, яка

запропонована в [4].

Непуста підмножина висячих вершин графа H створює підграф H' у вигляді лісу. Кожному дереву лісу відповідає коренева вершина, що зв'язує його з тією частиною графа H , яка не включає ребра та решту вершин дерева. Очевидно, коренева вершина кожного дерева є точкою зчленування, отже, кожне дерево лісу є компонентою зв'язності графа H , де всі вершини, крім висячих - точки зчленування.

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

Твердження 1. Будь-яке рішення ЗЗК для дерева має вартість, рівну подвоєній сумі ваг ребер.

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

134 © А.Ю. Левченко, 2011виділимо в графі H всі мости та відмітимо точки зчленування кожного моста. Очевидно, вартість замкненого маршруту по мосту дорівнює подвоєній вазі ребра, яке представляє міст. Сума вартостей маршрутів, які побудовані для виділених об'єктів, є постійною складовою вартості будь-якого розв'язку ЗЗК в графі H .

Для виділення дерев лісу H' застосуємо варіант алгоритму, запропонованого в [4]. Позначимо V' і U' множини вершин і ребер лісу H', K - множина кореневих вершин, K с V'.

Наступний алгоритм будує всі дерева лісу H' в графі H і визначає множину кореневих вершин K .

50. H = (V,U) - зв'язний граф, де V - множина вершин, U - множина ребер u = \vi, vj J , |V| = n ; вершини графа H впорядковані за зростанням їх ступенів: deg v1 < deg v2 <... < deg vn; K = 0, V' = 0, U' = 0.

51. Якщо deg v1 > 1, то кінець: граф H не містить лісу H , інакше i = 1.

52. Для ребра u = |vi, vj j положити deg vi = 1, deg vj = deg vj -1, V = V -\yi J , V' = V' u |vi, vj j , U = Uu{uJ ; i = i +1.

53. Якщо i = n -1, то V' = V, U' = U , кінець: граф H - дерево.

54. Якщо deg vt = 1, то перейти до кроку S2.

55. K = V'cV , побудувати для кожної кореневої вершини з K дерево лісу H .

Час роботи алгоритму, очевидно, порівняний з часом упорядкування ступенів графа H, який оцінюється, як відомо, величиною O (n log n).

Кожне ребро {v, wJ дерева H[, k = 1, |K|, взагалі кажучи, є мостом, видалення якого призводить до остовного незв'язного підграфу графа H , який не містить {v, wj .

Розглянемо підграф (S) графа H , який породжений підмножиною вершин S = (V - V')u K . Для знаходження і виділення всіх мостів у підграфі (S^ скористаємося алгоритмом пошуку в глибину, який визначає на множині вершин S всі точки зчленування за час O (S| + |V| - |V '|) [4]. Якщо пара точок зчленування з'єднана ребром, видалення якого збільшує число компонент зв'язності підграфа S , то вона створює міст Mm. Множина з s мостів породжує s +1 компонент зв'язності H" підграфа (SS).

Замкнений маршрут, який проходить по всім вершинам компоненти H", І = 1, s +1, є частиною

шуканого маршруту комівояжера у графі H .

Звернемося до підграфа, який отримано в результаті видалення всіх мостів. Компоненти зв'язності підграфа в сукупності містять всі відмічені вершини. Компонента може бути точкою зчленування, блоком або підграфом, який розділяється, тобто підграфом, який містить точки зчленування, відмінні від відмічених [5]. Побудуємо для кожної компоненти маршрут комівояжера, який починається та закінчується у відміченій вершині, інцидентної до моста. Розв'язок ЗЗК для графа H є результатом об'єднання всіх послідовних маршрутів у відмічених вершинах.

Покажемо, як об'єднуються у розв'язок ЗЗК т маршрути т'к, em, т", що побудовані відповідно для

дерев H'k лісу H , к = 1, |K|, мостів Mm , m = 1, s , і компонент зв'язності H" підграфа (S), І = 1, s +1. Зазначимо, що серед всіх компонент H" завжди існує така, що містить в точності одну вершину V1

одного моста. Визначимо її як першу в сукупності компонент H", І = 1, s +1. Вершину V1 приймемо за початкову та кінцеву точку шуканого маршруту комівояжера.

Якщо s > 2, то частина компонент H", І = 2, s +1, пов'язана між собою декількома мостами. У таких компонентах лежить одна вершина кожного моста.

Нехай т" = (w,a,b,- маршрут, побудований для H", І = 1, s +1, де w - вершина моста; w = v1 при І = 1. Припустимо, що в ньому містяться вершини з множини кореневих вершин K . Тоді виконаємо в т" заміну кожної вершини a є K на маршрут (a,..., a) для дерева H'k з кореневою вершиною a . В кожному маршруті т" відмічені всі вершини, інцидентні мостам.

Побудуємо граф (L, M), в якому вершині І є L , І = 1, s +1, поставлений у відповідність маршрут т", а ребру {i, M - міст Mm , m = 1, s . В графе (L, M) пара вершин i та j створює ребро {i, jJ, якщо вершини p єт" и q є     з'єднані мостом {p, qJ, i Ф j .

Граф (L, M) - дерево, оскільки за будовою він зв'язний, і Щ = |M| -1.

Вершину дерева (L, M), яка відповідає т", будемо вважати кореневою. Розв'язком ЗЗК є будь-який обхід всіх вершин дерева, який починається та закінчується у вершині v1 єт" і двічі проходить по кожному ребру множини M .

Всі деталі з'єднання в шуканий маршрут комівояжера множини маршрутів {т"'| l = 1, s +1|, з'єднаних

мостами Mm , m = 1, s , можна викласти, виходячи з рисунка 1.

Спочатку розв'язок ЗЗК містить маршрут т" = (v1,v1) і міст {v, w} , який з'єднує т" з маршрутом т" = (w,. ., x,. ., У,. ., w) . Оскільки x і y - відмічені вершини, тобто вершини мостів {x, a} і {y, b} , то т проходить по частині (w,x) маршруту т"", ребру {x, a}, маршруту T3" = {a,a} і ребру {a, x} . Далі він включає частину (x,y) маршруту т"", ребро {y, b}, маршрут т'[ = (b,b), ребро {b, y}, ще одну частину (y,w) маршруту т"" та ребро {w, v1}. Таким чином, побудований маршрут т = (v1,..., v1, w,x, a,..., a, x,y, b,b, y,w, v1). Очевидно, час об'єднання всіх виділених підграфів графа H обмежений величиною O ( \L\ +|M|) .

a

x

©v--

Рис. 1. Дерево (L, M) з зазначеними вершинами

Вартість маршруту комівояжера т дорівнює:

C(ж) = §C(т[) + 2£C(Mm) + ^C(т"') ,

Страницы:
1  2  3 


Похожие статьи

А Ю Левченко - Декомпозиція загальної задачі комівояжера та наближений метод її розв'язку

А Ю Левченко - Точний алгоритм розв'язку загальної задачі комівояжера