шуканий цикл; вилучити рядок і стовпець, на перетині яких знаходиться зазначене ребро; перейти до п. 2.
8.Розглянути випадок, коли ребро з максимальною вартіс тю ризику виключається із подальшого перегляду: збільшити поточне значення вартості шуканого гамільтонового циклу на значення вартості ризику ребра, що вилучається; заблокувати це ребро у таблиці суміжності; перейти до п. 2.
9.Дописати ребро, що відповідає елементуAjд, до списку ребер, які утворюють шуканий гамільтонів цикл з мінімальною вартістю.
10.Завершити алгоритм.
Пропонується такий варіант реалізації описаного алгоритму у вигляді програми. Для покращення читабельності програми наведені фрагменти містять «заглушки» у вигляді коментарів щодо обчислення тих або інших величин. Аналіз наведеного вище алгоритму наводить на думку щодо раціональності вико ристання рекурсії для його реалізації.
{Процедура, що виконує приведення поточної таблиці суміжності.} procedure reduce(a:mas; n:byte; var way:word; var way_rib: mas_w;
var item:byte); |
|
|
|
var i, j, x, y, rib_x, rib_y: byte; |
|
|
|
max, sumjnin: word; |
|
|
|
begin |
|
|
|
if П > 1 |
{Якщо розмірність таблиці більша за 1, то} |
||
then |
|
|
|
begin |
|
|
|
min_const(a, n, sum_min); {визначається сумарна константа приведення;} |
|||
|
|
{визначається нульове ребро} |
|
max_risk(a, n, max, х, у, rib_x, rib_y); |
{з максимальним ризиком;} |
||
|
|
{збільшується поточне значення} |
|
inc(way, sum_min); |
|
{вартості циклу, що будується.} |
|
if way < m i n w a y {Якщо це значення менше від визначеного мінімального, то} |
|||
t h e n b e g i n |
|
{(ліва гілка дерева розв'язку)} |
|
|
{збільшується лічильник включених} |
||
inc(item); |
|
|
{до шуканого циклу ребер;} |
way_rib[item].x := r i b x ; |
{дописується визначене ребро} |
||
way_rib[item].y := rib_y; |
|
{до списку ребер.} |
|
{Визначення ребра, що зациклює послідовність знайдених ребер і] |
|||
{присвоєння елементу таблиці, що йому відповідає значення -1.} |
|||
f o r І := 0 to П do |
{Виключається рядок, що відповідає} |
||
f o r j := у to n - 1 |
do |
|
{визначеному ребру.} |
a [ i , j ] : = a [ i , j + |
1]; |
|
|
f o r j := 0 to П do |
{Виключається стовпець, що відповідає} |
||
f o r і := х to n - 1 |
do |
|
{визначеному ребру;} |
a[i,j] :=a[i + 1,j]; |
|
|
|
reduce(a, n - 1, way, way_rib, item); |
{перехід до розгляду} |
||
e n d ; |
|
{таблиці зменшеної розмірності.} |
|
{Збільшення поточного значення вартості циклу} |
|||
inc(way, max); |
{на значення максимального ризику.} |
||
if way < m i n w a y {Якщо це значення менше від визначеного мінімального, то}
175
t h en begin |
{{права гілка дерева розв 'язку)} |
|
a[rib_x, rib_y] := - 1 ; |
{блокування ребра;} |
|
reduce(a, n, way, w a y r i b , item); {перехіддо розгляду таблиці} |
||
end; |
{з виключеним ребром.} |
|
end |
|
|
else begin |
{У разі зменшення таблиці до одного елемента:} |
|
if way < тігпл/ау{якщо значення отриманого циклу менше за мінімальне, то} |
||
then begin |
|
|
|
m i n w a y := way; |
{запам'ятати це значення;} |
|
inc(item); {збільшити лічильник кількості ребер у шуканому циклі;} |
|
|
|
{дописати ребро до списку ребер,} |
|
way_nbptem]j<:=а[1,0]; |
{що утворюють гамільтонів цикл} |
|
way_rib[item].y :=а[0,1]; |
{з мінімальним значенням.} |
|
end; |
|
end; |
|
|
end; |
|
|
Основна частина програми: |
|
|
for І := 1 to n do |
{Введення таблиці суміжності, що описує заданий граф.} |
|
for j := 1 to n do read(f_in, c[i, j]);
for і := 1 to n do c[i, 0] := і;{Введення додаткового стовпця з нумерацією вершин.} for j := 1 to n do C[0, j] := j; {Введення додаткового рядка з нумерацією вершин.}
for і := 1 to n do с[і, і] := - 1 ; |
{Блокування ребер (/', /').} |
min_way := 65535; way := 0; item := 0; |
{Ініціалізація початку розв'язку задачі.} |
|
{Звернення до процедури,} |
reduce(c, n, way, way_rib, item); |
{що визначає розв'язок задачі.} |
for І := 1 to n do |
{Виведення визначеного гамільтонового} |
write(f_out, '(', way_rib[i].x, '", way_rib[i].y, ') ');{циклу мінімальної довжини.} writeln(f_OUt); {Виведення значення довжини} writeln(f_out, 'Minimum way=', m i n w a y ) ; {мінімального гамільтонового циклу.}
Метод гілок і границь є досить ефективним евристичним підходом до розв'язання задачі про комівояжера. Проаналізує мо факти, що свідчать на користь цього твердження.
Перш за все треба зазначити, у чому полягає евристика розв'язання повноперебірної задачі. У цьому зв'язку була вису нута ідея щодо зміни значень таблиці суміжності за рахунок її приведення по рядках і стовпцях, а також покрокового визна чення подальшого включення ребер до шуканого гамільтоново го циклу або їх виключення із розгляду.
По-друге, слід визначити, у чому саме полягає ефективність застосування цього методу. Під час виконання алгоритму на конкретному прикладі покроково проводився розрахунок по точного значення нижньої границі вартості гамільтонового циклу й аналіз доцільності переходу до розгляду того чи іншо го ребра заданого графа. Це дало привід для відсікання тих гілок дерева розв'язку, де розташовані неперспективні ходи. Якщо протягом виконання дій і побудови дерева розв'язку буде
176
знайдено менше значення вартості гамільтонового циклу, ніж попередньо визначене, то воно стає еталонним і з ним надалі порівнюватимуться поточні значення нижніх границь вар тості. Це є приводом для відсікання всіх гілок дерева, які ма ють значення більші, ніж еталонне.
Уперше метод гілок і границь був запропонований Лендом і Дойгом у 1960 р. для розв'язування загальної задачі цілочисло вого лінійного програмування. У 1963 р. Літтл, Мурті, Суїні і Керел у своїй роботі запропонували застосування цього методу для розв'язання задачі про комівояжера у наведеній інтерпретації.
Однак це не єдиний спосіб застосування методу гілок і гра ниць для розв'язування задачі про комівояжера.
Нагадаємо алгоритм повного перебору, розглянутий у розді лі «NP-повні задачі». У його основі лежить алгоритм пере становки номерів вершин заданого графа у лексикографічному порядку. Для кожної такої перестановки визначалася сума довжин ребер, які відповідають утвореній послідовності вер шин. У розглянутому алгоритмі були застосовані деякі відсі кання зайвих дій, пов'язані з припиненням сумування у разі, якщо поточна сума перевищувала визначене на даний момент мінімальне значення довжини циклу. Користуючись новою термінологією, відсікання зайвих дій відповідає відсіканню гілок дерева розв'язку, а контроль за неперевищенням поточ ного мінімуму - встановлення нижньої границі вартості циклу.
А чи не можна використати ще якусь евристику, тобто збіль шити кількість відсікань наперед неперспективних гілок? Пропонується такий хід міркувань. Розглянемо їх на прикладі наведеного раніше алгоритму, де курсивом виділено коментарі, які стосуються змін у тексті основної частини програми:
b := a; flag := true; |
|
{Ініціалізація початку перебору варіантів.} |
|
while flag do |
|
|
{Повторення перебору варіантів,} |
begin |
|
{поки не буде досягнуто останнього варіанта.} |
|
permutation; |
|
|
{Одержання поточної перестановки.} |
sum := 0; І := 1; |
{Ініціалізація одержання довжини поточного маршруту.} |
||
while (sum < min) and (І <= П - 1) do |
{Поки поточна сума менша) |
||
begin |
|
|
{за поточний мінімум,} |
sum := sum + d[a[i], а[і + 1]]; {обчислення довжини поточного маршруту.} |
|||
іпс(і) |
|
|
|
end; |
|
|
|
if І > П - 1 {Якщо знайдена сума всіх ребер перестановки, крім останньої, то} |
|||
then begin |
|
|
|
sum := sum + d [ a [ n ] , a [ 1 ] ] ; {додавання останньої ланки маршруту;} |
|||
if sum < min then |
{перевірка оптимальності поточного маршруту;} |
||
begin |
|
|
|
min := sum; |
{визначення оптимального поточного маршруту;} |
||
Ь := а |
|
|
{збереження послідовності об'їзду} |
end; |
|
|
{міст оптимального маршруту.} |
end |
|
|
|
177
else SOrt( І); {(УВАГА! ІДЕЯ МЕТОДУ!) інакше сортування залишку вершин]
|
{поточної перестановки за зростанням} |
|
{для відсікання всіх неперспективних перестановок.} |
count := 0; |
{Ініціалізація визначення завершення перестановок.) |
for І := 2 to П - 1 do {Починаючи з другого елемента поточної перестановки,}
if а[І] > а[І + 1 ] |
{підрахунок пар сусідніх елементів,} |
then inc(COunt); |
{що утворюють спадну послідовність.} |
if count = n - 2 then flag := false; |
{Якщо всі елементи перестановок,} |
end; {крім першої, утворюють спадну послідовність, то завершити алгоритм.)
На відміну від попередньої послідовності пояснення після наведення тексту програми, що реалізує алгоритм, перейдемо до детальніших коментарів щодо ідеї алгоритму.
Нехай для деякої перестановки av а2 , ..., at, ai + 1,..., an ви значено мінімальне значення суми довжин усіх ребер. Спочат ку розглянемо випадок, коли наступна перестановка дасть су му, більшу за визначене мінімальне значення. Така ситуація
може статися для деякого елемента послідовності at, тобто до |
|
давання довжини ребра (at, ai + х) перевищить знайдений поточ |
|
ний мінімум: d[av а2 ] + d[a2, а3 ] + ... + d[at, al + J > min. Оскіль |
|
ки це сталося після додавання d[ap ai + |
J, то можна стверджува |
ти, що d[av a2 ] + d[a2, a3 ] + ... + d[at_v |
at] sSi min. Таким чином, |
логічним є висновок, що додавання довжин ребер, починаючи з ребра (аг, at + j), тільки погіршить ситуацію.
Розглянемо дві частини поточної послідовності: av a2 , ..., at і al + j, ..., an. Перша представляє вершини графа, що утворю ють ребра, сума довжин яких не перевищує поточного мініму му, а додавання другої - перевищує його. Значить, якою не бу ла б послідовність елементів ai + l,..., an, додавання довжин цих ребер все одно буде перевищувати мінімум. Тому логічно буде пропустити всі перестановки цих елементів, які, як відомо, відбуваються якраз справа наліво. Остаточним варіантом пе рестановки значень елементів ai + v ..., an буде такий, для яко го виконується умова ai + 1> аі + 2> •••> ап- Тому, для того щоб не розглядати зайві перестановки елементів аі + 1, ..., ап, штуч но упорядкуємо їх за спаданням і продовжимо алгоритм далі.
У разі, коли при деякій перестановці буде знайдено міні мальне значення, а на наступному воно буде покращене, то це не суперечить логіці міркувань, оскільки все одно далі може знайтись такий елемент аь, для якого додавання довжини ребра (at, at + г) перевищить знайдений мінімум. Якщо ні і на кожній наступній перестановці буде покращуватися значення мініму му, то кількість опрацьованих перестановок буде такою, як і в алгоритмі з повним перебором усіх варіантів.
Оскільки у даному алгоритмі на відміну від повного перебо ру наперед невідома кількість відкинутих перестановок, то за вершення роботи алгоритму визначається за умови, що на де-
178
якому кроці виконання алгоритму всі елементи послідовності а2 , ..., at, аі + 1, ..., ап упорядкуються за зростанням. Нагадаємо, що першим елементом послідовності є номер вершини, з якої починається об'їзд комівояжера.
А тепер підіб'ємо підсумок і остаточно визначимо, де у роз глянутому алгоритмі є ознаки методу гілок і границь. По-перше, це можливість відкидання наперед неперспективних пере становок елементів (гілок), що є номерами вершин графа. Подруге, критерієм оцінювання ситуації щодо відкидання пере становок елементів at + j>, ..., ап є значення поточного мінімуму (нижня границя). Евристичні підходи до розробки такого алго ритму базуються на ідеї скасування всіх перестановок елементів, що належать фрагменту аі + 1, ..., ап, як ті, що не дадуть покра щання результату при врахуванні довжин відповідних їм ребер.
Точних оцінок ефективності роботи методу гілок і границь на разі не існує. Однак слід зазначити, що на сучасних комп'ю терах більшість задач про комівояжера із застосуванням цього методу можна розв'язати і для кількості вершин, що сягає зна чення 100.
Щодо тестування цих алгоритмів, то порада буде такою: корисно перевірити їх роботу на тих самих тестах, на яких пе ревірялися інші методи, рекомендовані для розв'язання задачі про комівояжера.
Завдання
1.Розробити та реалізувати у вигляді програми алгоритм ви значення наближеного розв'язку задачі про комівояжера, використавши алгоритм Ейлера.
2.Виконати завдання 1 для повного зваженого графа з кіль кістю вершин N ^5. Результат виконання програми вивести у файл.
3.Виконати завдання 1 для повного зваженого графа з кіль кістю вершин N < 12. Результат виконання програми вивес ти у файл.
4.Розробити та реалізувати у вигляді програми алгоритм ви значення розв'язку задачі про комівояжера, використавши метод гілок і границь, що базується на ідеї приведення таб лиці суміжності.
5.Виконати завдання 4 для повного зваженого графа з кількістю вершин N^5. Результат виконання програми вивести у файл.
6.Виконати завдання 4 для повного навантаженого графа з кількістю вершин N ^ 12. Результат виконання програми вивести у файл.
7.Розробити та реалізувати у вигляді програми алгоритм визна чення розв'язку задачі про комівояжера, використавши метод гілок і границь, що базується на ідеї повного перебору варіантів.
179