Метод гілок та меж у гальмітоновій задачі про сільського листоношу
Cформульовано гамільтонову задачу про сільського листоношу, яка є узагальненням гамільтонової задачі комівояжера. Запропоновано модифікацію класичного методу гілок та меж (методу Літтла), яка дозволяє знаходити точний розв’язок гамільтонової задачі про сільського листоношу або коректно встановити йо...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2012
|
| Назва видання: | Системні дослідження та інформаційні технології |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/50164 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод гілок та меж у гальмітоновій задачі про сільського листоношу / А.В. Морозов, А.В. Панішев // Систем. дослідж. та інформ. технології. — 2012. — № 2. — С. 57-66. — Бібліогр.: 6 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-50164 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-501642013-10-07T03:04:21Z Метод гілок та меж у гальмітоновій задачі про сільського листоношу Морозов, А.В. Панішев, А.В. Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Cформульовано гамільтонову задачу про сільського листоношу, яка є узагальненням гамільтонової задачі комівояжера. Запропоновано модифікацію класичного методу гілок та меж (методу Літтла), яка дозволяє знаходити точний розв’язок гамільтонової задачі про сільського листоношу або коректно встановити його відсутність. Сформулирована гамильтоновая задача о сельском почтальоне, которая является обобщением гамильтоновой задачи коммивояжера. Предложена модификация классического метода ветвей и границ (метода Литтла), позволяющая находить точное решение гамильтоновой задачи о сельском почтальоне или корректно установить его отсутствие. The Hamiltonian Rural Postman Problem, which is generalization of the Hamiltonian Travelling Salesman Problem, is formulated. Modification of the classical branch-and-bound algorithm (Little’s method) which allows to find exact solution of the Hamiltonian Rural Postman Problem or correctly determine lack of solution is offered. 2012 Article Метод гілок та меж у гальмітоновій задачі про сільського листоношу / А.В. Морозов, А.В. Панішев // Систем. дослідж. та інформ. технології. — 2012. — № 2. — С. 57-66. — Бібліогр.: 6 назв. — укр. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/50164 519. 161 uk Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах |
| spellingShingle |
Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Морозов, А.В. Панішев, А.В. Метод гілок та меж у гальмітоновій задачі про сільського листоношу Системні дослідження та інформаційні технології |
| description |
Cформульовано гамільтонову задачу про сільського листоношу, яка є узагальненням гамільтонової задачі комівояжера. Запропоновано модифікацію класичного методу гілок та меж (методу Літтла), яка дозволяє знаходити точний розв’язок гамільтонової задачі про сільського листоношу або коректно встановити його відсутність. |
| format |
Article |
| author |
Морозов, А.В. Панішев, А.В. |
| author_facet |
Морозов, А.В. Панішев, А.В. |
| author_sort |
Морозов, А.В. |
| title |
Метод гілок та меж у гальмітоновій задачі про сільського листоношу |
| title_short |
Метод гілок та меж у гальмітоновій задачі про сільського листоношу |
| title_full |
Метод гілок та меж у гальмітоновій задачі про сільського листоношу |
| title_fullStr |
Метод гілок та меж у гальмітоновій задачі про сільського листоношу |
| title_full_unstemmed |
Метод гілок та меж у гальмітоновій задачі про сільського листоношу |
| title_sort |
метод гілок та меж у гальмітоновій задачі про сільського листоношу |
| publisher |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| publishDate |
2012 |
| topic_facet |
Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/50164 |
| citation_txt |
Метод гілок та меж у гальмітоновій задачі про сільського листоношу / А.В. Морозов, А.В. Панішев // Систем. дослідж. та інформ. технології. — 2012. — № 2. — С. 57-66. — Бібліогр.: 6 назв. — укр. |
| series |
Системні дослідження та інформаційні технології |
| work_keys_str_mv |
AT morozovav metodgíloktamežugalʹmítonovíjzadačíprosílʹsʹkogolistonošu AT paníševav metodgíloktamežugalʹmítonovíjzadačíprosílʹsʹkogolistonošu |
| first_indexed |
2025-07-04T11:43:13Z |
| last_indexed |
2025-07-04T11:43:13Z |
| _version_ |
1836716545765539840 |
| fulltext |
© А.В. Морозов, А.В. Панішев, 2012
Системні дослідження та інформаційні технології, 2012, № 2 57
TIДC
ПРОБЛЕМИ ПРИЙНЯТТЯ РІШЕНЬ І
УПРАВЛІННЯ В ЕКОНОМІЧНИХ, ТЕХНІЧНИХ,
ЕКОЛОГІЧНИХ І СОЦІАЛЬНИХ СИСТЕМАХ
УДК 519. 161
МЕТОД ГІЛОК ТА МЕЖ У ГАМІЛЬТОНОВІЙ ЗАДАЧІ
ПРО СІЛЬСЬКОГО ЛИСТОНОШУ
А.В. МОРОЗОВ, А.В. ПАНІШЕВ
Cформульовано гамільтонову задачу про сільського листоношу, яка є узагаль-
ненням гамільтонової задачі комівояжера. Запропоновано модифікацію класич-
ного методу гілок та меж (методу Літтла), яка дозволяє знаходити точний
розв’язок гамільтонової задачі про сільського листоношу або коректно встано-
вити його відсутність.
ВСТУП
Задача комівояжера та методи її розв’язання нині є широко відомими. Менш
відомою є гамільтонова задача комівояжера, яка описана в роботах [1–2].
У цій роботі описується узагальнення гамільтонової задачі комівояжера для
випадку, коли додатково задано множину ребер, через які обов’язково має
пройти гамільтонів цикл. Це узагальнення називатимемо гамільтоновою за-
дачею про сільського листоношу (ГЗСЛ) [3, 4]. Відомі на сьогодні методи
розв’язання гамільтонової задачі комівояжера не можуть бути безпосе-
редньо застосовані для такої задачі.
ПОСТАНОВКА ЗАДАЧІ
Сформулюємо задачу про сільського листоношу в термінах теорії графів.
Задано зв’язний зважений граф ),( UVH = з множиною вершин ,V
nV = та множиною ребер .U Кожному ребру Uji ∈},{ приписано вагу
+∈ 0Zdij , ji ≠ , nji ,1, = , +
0Z — множина невід’ємних цілих чисел. Граф H
повністю визначається симетричною матрицею ваг nijd ][ , де +∈ 0Zdij , якщо
Uji ∈},{ та ∞=ijd інакше, ji ≠ , nji ,1, = , ∞=iid , nji ,1, = . На множині
U задано непорожню підмножину ребер R . Необхідно знайти в графі H цикл,
який містить кожне ребро з R та має мінімальну сумарну вагу всіх ребер.
Позначимо )(Rz гамільтонів цикл графу ,H який проходить по всім
ребрам множини R . Назвемо ГЗСЛ задачу, що полягає в знаходженні гаміль-
тонового циклу )(* Rz , який мінімізує функціонал:
А.В. Морозов, А.В. Панішев
ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 58
∑
∈
=
)(},{
))((
Rzlk
kldRzC . (1)
Зацікавленість у розв’язанні ГЗСЛ виникає у тому випадку, коли потріб-
но знайти кільцевий маршрут на транспортній мережі міста або району, що
моделюється графом ),( UVH = . Кожному пункту відправлення (прибуття)
мережі відповідає вершина ,Vi ∈ nV = , а кожному ребру Uji ∈},{ — від-
різок дорожнього полотна між парою сусідніх пунктів i та j. Ребро },{ ji ха-
рактеризується вагою (вартістю) ijd , яка дорівнює затратам на переміщення
транспортного засобу з i в j або з j в i .
На практиці пасажирські автоперевезення виконуються за маршрутами,
для яких завчасно визначено порядок проходження деякої частини пунктів.
Основою для вибору таких ділянок можуть бути пріоритети одних пунктів
над іншими: масиву багатоповерхових будівель над котеджним селищем,
заводського району над курортною зоною тощо. Наприклад, середній час
поїздки пасажирів за кільцевим міським маршрутом, що охоплює сусідні,
прилеглі, щільнонаселені квартали — менший, ніж у будь-якого іншого
кільцевого маршруту, якщо показники якості дорожнього покриття мережі
відповідають встановленим параметрам. Ділянки доріг, які апріорі включено
в планований кільцевий маршрут у графі ),,( UVH = подані множиною ре-
бер R , що утворюють сукупність ланцюгів. Якщо в графі H міститься га-
мільтонів цикл ),(Rz то у відповідній транспортній мережі він визначає
найпростіший кільцевий маршрут.
ГЗСЛ є NP-повною, оскільки у випадку ∅=R вона є NP-повною гаміль-
тоновою задачею комівояжера (ГЗК) [4]. У [2] запропоновано алгоритм,
який коректно знаходить розв’язок ГЗК, якщо граф H гамільтонів,
і встановлює її нерозв’язність у протилежному випадку. В основі запропо-
нованого алгоритму лежить схема гілок та меж, яка виконується після пере-
вірки достатніх умов нерозв’язності ГЗСЛ. Очевидно, що складність такої
перевірки має бути обмежена поліномом від розміру задачі.
Безпосереднє застосування алгоритму гілок та меж з [1, 2] не дозволяє
розв’язати ГЗСЛ. Включення в шуканий гамільтонів цикл заданої підмно-
жини ребер ∅≠R виявляється настільки сильним обмеженням, що вимагає
іншого підходу до організації розгалуження та обчислення нижніх оцінок
для ))(( * RzC .
АЛГОРИТМ
За допомогою вершинно-реберного перетворення, який описаний у [5] ГЗСЛ
зводиться до цієї ж задачі на графі ,),( UVH = в якому степені всіх вершин
більші, ніж 2 і множина ребер R , яка міститься в шуканому гамільтоновому
циклі, утворює паросполучення R . Очевидно, ,
2⎥⎦
⎥
⎢⎣
⎢≤
nR .Vn = Відмітимо,
що величина R обмежує простір розв’язків настільки, що він може вияви-
тися порожнім. Назвемо допустимий розв’язок ГЗСЛ )(Rz обходом.
Пошук розв’язку задачі починається з перетворення матриці вартостей
графу H у приведену матрицю [6]. Він полягає в тому, що в рядку i шука-
Метод гілок та меж у гамільтоновій задачі про сільського листоношу
Системні дослідження та інформаційні технології, 2012, № 2 59
ється мінімальний елемент ijji dmin=α , ni ,1= , який віднімається від кож-
ного елемента цього рядка. Потім у стовпці j шукається мінімальний еле-
мент ,min ijj d=β nj ,1= , який віднімається від кожного елемента цього
стовпця. Елементи iα та jβ називаються коефіцієнтами приведення. З при-
веденої матриці nijd ][ знаходиться нижня границя вартості шуканого
розв’язку
∑
∈
+=
Rji
jiij ddR
},{
},{min)( γφ , (2)
де
∑∑
==
+=
n
j
i
n
i
i
11
βαγ .
Приведена матриця, яка визначає множину всіх розв’язків ГЗСЛ, у за-
гальному випадку не симетрична. Їй взаємно однозначно відповідає зваже-
ний орієнтований мультиграф ),( UVH ′=′ , в якому вершини i та j зв’язані
парою дуг ),( ji та ),( ij , якщо в графі ),( UVH = вони зв’язані ребром
.},{ ji Таким чином, кожне ребро Rji ∈},{ графу H подане в мультиграфі
H ′ двома дугами Rji ′∈),( , Rij ′∈),( , UU 2=′ , RR 2=′ .
У приведеній матриці виберемо ті елементи ),( ji та ,),( Rij ′∈ для яких
0},{min >=∆ jiijij dd і покладемо
ijijjiijijij ddddd ∆−=−= },{min , ijjijiijjjiji ddddd ∆−=−= },{min .
Назвемо отриману матрицю nijd ][ повністю приведеною. Подальші дії
будуть виконуватися за допомогою цієї матриці.
Перетворення матриці вартостей графу H у повністю приведену мат-
рицю nijd ][ має аргументоване обґрунтування. ГЗСЛ для повністю приве-
деної матриці полягає в побудові гамільтонового контуру або обходу міні-
мальної вартості, який включає в точності одну дугу з кожної пари ),,( ji
,),( Rij ′∈ що містить хоча б одну дугу з нульовою вагою. Таким чином, за
матрицею nijd ][ визначається список дуг нульової ваги, які є претендентами
на включення в оптимальний розв’язок.
Викладені міркування відкривають можливість адаптувати класичний
алгоритм гілок та меж, який описаний у [6], для пошуку розв’язку ГЗСЛ.
Покажемо, що спосіб розгалуження допустимих розв’язків )(Rz вкладаєть-
ся у відому схему побудови бінарного дерева перебору [6].
Кореню дерева перебору )}({ Rz поставимо у відповідність повністю
приведену матрицю nijd ][ з оцінкою )(Rφ і визначимо дугу мультиграфу
,H ′ яка ініціює розгалуження. Для цього, як і в [6], кожний елемент ),( qp
в nijd ][ такий, що 0=pqd , оцінимо величиною
jqpjpiqi
ddqp
≠≠
+= minmin),(γ (3)
і знайдемо елемент ),( qp з найбільшим значенням
А.В. Морозов, А.В. Панішев
ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 60
}0|),({max),( ==Γ pqdqplk γ . (4)
Елементу ),( qp у мультиграфі H ′ відповідає дуга ),,( qp яка ініціює
розбиття множини всіх обходів на дві підмножини та породжує в умовах
ГЗСЛ два випадки: Rlk ∉},{ та Rlk ∈},{ .
У випадку Rlk ∉},{ множина всіх розв’язків задачі розбивається на
підмножини }},{{ Rlk ∉ та )},{( lk . Перша підмножина включає всі обходи,
які містять дугу ),( lk , а друга — усі обходи, які не містять цієї дуги.
Матриця, за якою обчислюється нижня границя )),(( Rlk ′∈φ вартості
всіх обходів множини { }RRlk ′∉∉},{ і визначає цю множину, знаходиться
так само, як і в [6], за умови, що виконується таке правило.
Якщо множина R містить ребро },{ kx , то в шуканий обхід разом із ду-
гою ),( lk включається дуга ),( kx . Аналогічно, якщо множина R містить
ребро },{ ly , то до дуги ),( lk приєднується дуга ),( yl . Включення дуги
),( kx або ),( yl у підмножину розв’язків }),{( Rlk ′∉ означає, що матриця,
яка її визначає, не містить не тільки рядок k та стовпець l, але і той рядок
і стовпець, номери яких є початком і кінцем дуги, що приєднується. У випад-
ку },{ kx , Rly ∈},{ до дуги ),( lk приєднуються дуги ),( kx і ),( yl , а у мат-
риці, яка визначає множину }),{( Rlk ′∉ , виключаються рядки lkx ,, та
стовпці .,, ylk
Позначимо нижню границю вершини розгалуження .φ Для дуги
Rlk ′∉),( , яка ініціює розгалуження, покладемо
⎩
⎨
⎧ ∈
=
інакше; ,0
,}{якщо , Rx,kd xk
kµ
⎩
⎨
⎧ ∈
= інакше, ,0
, }{якщо , Rl,ydly
lµ
де lyxk dd , — елементи матриці, яка відповідає границі .φ У випадку
)(Rφφ = вони є елементами повністю приведеної матриці nijd ][ . Тоді вар-
тість усіх обходів множини }),{( Rlk ′∉ обмежена знизу величиною
∑∑ ′+′+++=∉ jilkRlk βαµµφφ )),(( , (5)
де iα′ та jβ ′ — коефіцієнти приведення, отримані в результаті перетворення
матриці, якій відповідає границя ,φ у матрицю, яка визначає множину
}.),{( Rlk ∉
Матриця, яка визначає множину ),( lk , і границя ),( lkφ знаходиться
так, як і в [6]:
),(),( lkГlk += φφ . (6)
Розглянемо випадок, коли Rlk ∈),( . Простір розв’язків ГЗСЛ )}({ Rz
розбивається на дві підмножини )},{( lk та .)},{( kl У першу підмножину
включаються всі обходи, які містять дугу ),( lk , а в другу — дугу ),( kl .
Нехай вершині розгалуження відповідає границя ϕ та матриця D, яка
породжує дугу ),( lk або ),( kl , Rlk ∈},{ із максимальною оцінкою. Матри-
ця, яка визначає підмножину ,)},{( lk знаходиться в результаті виключення
Метод гілок та меж у гамільтоновій задачі про сільського листоношу
Системні дослідження та інформаційні технології, 2012, № 2 61
з D рядка k та стовпця ,l присвоєння елементу lkd значення ∞ та приве-
дення отриманої скороченої матриці. Аналогічно, для знаходження матриці,
яка визначає підмножину )},{( kl , необхідно в D покласти ,∞=kld вида-
лити рядок l та стовпець k та виконати приведення отриманої скороченої
матриці. Нижні границі вартості обходів для підмножини )},{( lk та )},{( kl
обчислюються таким чином:
∑∑
≠≠
′+′++=
lj
j
ki
ikldlk βαφφ ),( , (7)
∑∑
≠≠
′+′++=
lj
j
ki
ilkdkl βαφφ ),( , (8)
де ji βα ′′, — коефіцієнти приведення, отримані в результаті перетворення
матриці D .
Можливим є випадок, коли в D або ∞=kld , або ∞=lkd . З (7) і (8) ви-
пливає, що якщо ∞=kld , то ∅=)},{( lk , якщо lkd = ∞ , то ∅=)},{( kl .
Модифікація базового алгоритму гілок та меж для розв’язання ГЗСЛ,
яку отримано в результаті вершинно-реберного перетворення (ВРП), має
такий вигляд.
0. ),( UVH = — неорієнтований зважений граф із степенями вершин
більшими 2, поданий матрицею вартостей порядку Vn = ; R — паросполу-
чення графу ,H яке міститься в шуканому гамільтоновому циклі )(Rz∗ мі-
німальної вартості. Покладаємо C∗ = ∞ .
1. Матриця вартостей графу H перетворюється в приведену матрицю,
за якою обчислюється нижня границя )(Rφ вартостей для всіх розв’язків
задачі. З приведеної матриці визначається повністю приведена матриця
nijdD ][= , яка відповідає орієнтованому зваженому мультиграфу
),( UVH ′=′ , UU 2=′ , RR 2=′ . У H ′ потрібно знайти гамільтонів кон-
тур (обхід), який містить рівно по одній дузі з кожної пари дуг ),( ji ,
Rij ′∈),( , і має мінімальну вартість.
2. У матриці D за формулами (3) і (4) знаходиться елемент ),( lk , пода-
ний у мультиграфі дугою ),( lk , яка породжує в дереві перебору вершину
розгалуження.
3. Якщо Rlk ∉},{ , то перехід до п. 7.
4. Якщо ∞=lkd , то підмножина обходів Rlkkl ∈},{)},,{( , яка містить
дугу ),( kl порожня; перехід до п. 6.
5. Для визначення підмножини обходів Rlkkl ∈},{)},,{( , які містять
дугу ),( kl , розглядається скорочена матриця, де ∞=kld і виключено рядок
l та стовпець .k Після її приведення за формулою (8) обчислюється нижня
границя ),( klφ вартості дуг усіх обходів підмножини )},{( kl , яка породжує
в дереві перебору поточну активну вершину )},{( kl . Якщо ),( klC φ>∗ , то вер-
шина )},{( kl з приведеною матрицею D та границею ),( klφ приєднується
до вершини розгалуження, інакше вона далі не розглядається. Перехід до п. 9.
А.В. Морозов, А.В. Панішев
ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 62
6. Для визначення підмножини обходів Rlklk ∈},{)},,{( , які містять
дугу ),,( lk розглядається скорочена матриця, в якій ∞=lkd і виключені
рядок k та стовпець l . Після її приведення за формулою (7) обчислюється
нижня границя ),( lkφ вартості всіх обходів підмножини )},{( lk , яка викли-
кає в дереві перебору поточну активну вершину .)},{( lk Якщо ),( lkC ϕ>∗ ,
вершина )},{( lk з приведеною матрицею D та границею ),( lkϕ приєднуєть-
ся до вершини розгалуження, в іншому випадку вершина виключається
з подальшого розгляду. Перехід до п. 9.
7. Під час визначення підмножини обходів Rlklk ∉},{)},,{( , які не міс-
тять дуги ),( lk , матриця у вершині розгалуження зводиться до матриці D
після заміни kld ≠ ∞ на kld = ∞ . Якщо ),( lkC φ>∗ , то в дереві перебору
вершина )},{( lk додається до вершини розгалуження разом із приведеною
матрицею D та нижньою границею ),( lkφ вартості обходів )},{( lk , в ін-
шому випадку вершина більше не розглядається. Величина ),( lkφ дорівнює
нижній границі вершини розгалуження, збільшеній на оцінку ),(~ lkA .
8. Для визначення підмножини обходів }'),{( Rlk ∉ , які містять дугу
),( lk , у матриці при вершині розгалуження виключаються: рядок k та стов-
пець l ; рядки ks, та стовпці lk, , якщо Rks ∈},{ ; рядки lk, та стовпці ,, lp
якщо Rpl ∈},{ ; рядки lks ,, та стовпці plk ,, , якщо Rplks ∈},{},,{ . Шля-
хом приведення отриманої матриці шукається матриця .D Після обчислен-
ня нижньої границі )),(( Rlk ′∉φ вартостей обходів ,}),{( Rlk ′∉ яка визна-
чається за формулою (5), вершина }),{( Rlk ′∉ з матрицею D та оцінкою
)),(( Rlk ′∉φ приєднується до вершини розгалуження, якщо виконується
умова )),((* RlkC ′∉> φ , інакше вершину більше не розглядаємо.
9. Якщо розмірність матриці D дорівнює одиниці, то отримано допус-
тимий розв’язок )(Rz ГЗСЛ. Виключаємо з подальшого розгляду вершини,
оцінки яких більші або рівні .*C Якщо після виключення не залишилося
жодної вершини, то перехід до п. 10. Інакше, знаходимо вершину дерева
з найменшою оцінкою. Якщо таких вершин кілька, то вибираємо ту, якій
відповідає матриця меншої розмірності. Перехід до п. 2.
10. Якщо під час розв’язання не було знайдено жодного припустимого
розв’язку, то ГЗСЛ є нерозв’язною. Інакше )(Rz∗ — шуканий гамільтонів
контур, а ∗C — його вага.
ПРИКЛАД
Для матриці вартостей графу ),( UVH =
1 2 3 4 5 6
1 ∞ 10 ∞ 5 7 18
2 10 ∞ 23 15 ∞ 8
3 ∞ 23 ∞ 25 24 ∞
4 5 15 25 ∞ ∞ 23
5 7 ∞ 24 ∞ ∞ 11
6 18 8 ∞ 23 11 ∞
Метод гілок та меж у гамільтоновій задачі про сільського листоношу
Системні дослідження та інформаційні технології, 2012, № 2 63
і підмножини його ребер }}6,2{},5,1{},4,3{{=R необхідно знайти розв’язок
ГЗСЛ або коректно встановити, що задача не має розв’язку.
1. Після віднімання із кожного рядка вихідної матриці вектора
)8,7,5,23,8,5(=α і віднімання з кожного стовпця отриманої матриці векто-
ра )0,1,0,15,0,0(=β знайдемо приведену матрицю
1 2 3 4 5 6
1 ∞ 5 ∞ 0 1 13
2 2 ∞ 0 7 ∞ 0
3 ∞ 0 ∞ 2 0 ∞
4 0 10 5 ∞ ∞ 18
5 0 ∞ 2 ∞ ∞ 4
6 10 0 ∞ 15 2 ∞
і визначимо нижню границю вартості всіх розв’язків ГЗСЛ:
=++++= ∑∑
==
6
1
6
1
622651154334 },{},{min},{min)(
j
j
i
iddddddR βαφ
.741656)0,0(min}0,1{min}5,2{min =++++=
Оскільки ,02},{min 34433434 >===∆ ddd то поклавши 034 =d ,
343 =d , отримаємо повністю приведену матрицю
1 2 3 4 5 6
1 ∞ 5 ∞ 0 1 13
2 2 ∞ 0 7 ∞ 0
3 ∞ 0 ∞ 0 0 ∞
4 0 10 3 ∞ ∞ 18
5 0 ∞ 2 ∞ ∞ 4
6 10 0 ∞ 15 2 ∞
.
2. Обчислимо оцінки для всіх нульових елементів повністю приведеної
матриці:
,0)2,3(,4)6,2(,2)3,2(,1)4,1( ==== γγγγ
,2)1,5(,3)1,4(,1)5,3(,0)4,3( ==== γγγγ 2)2,6( =γ .
Дуга )6,2( мультиграфу H ′ ініціює розгалуження.
3. R∈}6,2{ .
4. ∞≠26d . Множина всіх розв’язків задачі розбивається на підмножи-
ну обходів )},2,6{( які містять дугу )2,6( і підмножину обходів )},6,2{( які
містять дугу )6,2( .
5. Знаходимо матрицю, яка визначає підмножину обходів )}2,6{( . Для цього
виключаємо дугу )6,2( , поклавши ∞=26d , виключаємо рядок 6 і стовпець 2
і приводимо отриману скорочену матрицю. Приведена матриця має вигляд
1 3 4 5 6
1 ∞ ∞ 0 1 9
2 2 0 7 ∞ ∞
3 ∞ ∞ 0 0 ∞
4 0 3 ∞ ∞ 14
5 0 2 ∞ ∞ 0
А.В. Морозов, А.В. Панішев
ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 64
і дає оцінку ∑∑
≠≠
=++=′+′++=
26
62 784074)()2,6(
j
j
i
idR βαφφ .
6. Матриця, яка визначає підмножину обходів )}6,2{( , знаходиться
шляхом присвоєння дузі )2,6( ваги ∞=62d , виключенням рядка 2, стовпця
6 і приведенням отриманої матриці:
1 2 3 4 5
1 ∞ 5 ∞ 0 1
3 ∞ 0 ∞ 0 0
4 0 10 1 ∞ ∞
5 0 ∞ 0 ∞ ∞
6 8 ∞ ∞ 13 0
.
Звідси випливає оцінка
∑∑
≠≠
=+++=′+′++=
62
26 7822074)()6,2(
j
j
i
idR βαφφ .
7. Розмірність приведеної матриці більша за одиницю. Будь-яка з вер-
шин )}6,2{( , )}2,6{( дерева розгалуження може бути обрана в якості актив-
ної. Виберемо вершину )}6,2{( .
8. Обчислимо оцінки для всіх нульових елементів матриці, яка визначає
підмножину обходів )}6,2{( :
,1)1,4(,0)5,3(,0)4,3(,5)2,3(,1)4,1( ===== γγγγγ
,0)1,5( =γ .8)5,6(,1)3,5( == γγ
Дуга )5,6( ініціює розгалуження.
9. R∉}5,6{ ; множина обходів )}6,2{( розбивається на підмножину об-
ходів })5,6{( R′∉ , які включають дугу )5,6( , і підмножину обходів )}5,6{( ,
які не містять цю дугу.
10. У матриці, якій відповідає границя )6,2(φ , покладаємо 65d = ∞
і приводимо отриману матрицю. Результатом таких дій є матриця
1 2 3 4 5
1 ∞ 5 ∞ 0 1
3 ∞ 0 ∞ 0 0
4 0 10 1 ∞ ∞
5 0 ∞ 0 ∞ ∞
6 0 ∞ ∞ 5 ∞
і оцінка 86878)5,6(~)6,2()5,6( =+=+= Aφφ , яка обмежує знизу вартості всіх
обходів )}5,6{( , що включають дугу )6,2( і не містять дуги )5,6( .
11. У матриці, яка відповідає нижній границі ),6,2(φ виключаємо рядок
6 і стовпець 5. Оскільки ребра R∉}5,6{ і R∈}1,5{ суміжні, то виключаємо
рядок 5 і стовпець 1 та забороняємо дугу )2,1( , покладаючи ∞=12d задля
уникнення виникнення підциклів. У результаті приведення отриманої мат-
риці переходимо до матриці
Метод гілок та меж у гамільтоновій задачі про сільського листоношу
Системні дослідження та інформаційні технології, 2012, № 2 65
2 3 4
1 ∞ ∞ 0
3 0 ∞ 0
4 9 0 ∞
і оцінки ∑∑ =++=′+′++=′∉ 791078)6,2())5,6(( 51 jidR βαφφ , яка об-
межує вартості всіх обходів })5,6{( R′∉ . Розмірність таблиці більша за оди-
ницю, тому вибираємо вершину розгалуження з найменшою нижньою гра-
ницею )2,6(φ .
12. Знаходимо у відповідній матриці оцінки для всіх її нульових елементів:
.9)6,5(,0)1,5(,5)1,4(,1)5,3(,0)4,3(,4)3,2(,1)4,1( ======= γγγγγγγ
Подальше розгалуження виконується за допомогою дуги )6,5( .
13. Так як R∉}6,5{ , множина обходів )}2,6{( подана розбиттям на під-
множину })6,5{( R′∉ і підмножину )}6,5{( .
14. Вершині )}6,5{( відповідає матриця
1 3 4 5 6
1 ∞ ∞ 0 1 0
2 2 0 7 ∞ ∞
3 ∞ ∞ 0 0 ∞
4 0 3 ∞ ∞ 14
5 0 2 ∞ ∞ ∞
і оцінка 87978)6,5()2,6()6,5( =+=+= Гφφ .
15. У матриці, яка визначає множину обходів })6,5{( R′∉ , покладаємо
∞=21d для усунення підциклів:
1 3 4
2 ∞ 0 7
3 ∞ ∞ 0
4 0 3 ∞
.
Оцінка, яка їй відповідає: 79178)2,6())6,5(( 15 =+=+=′∉ dR φφ . Для
розгалуження вибираємо вершину })5,6{( R′∉ з найменшою нижньою гра-
ницею.
16. Знаходимо оцінки для всіх нульових елементів матриці, які відпові-
дають цій вершині: .9)3,4(,0)4,3(,9)2,3(,0)4,1( ==== γγγγ Розгалуження
продовжує дуга .)2,3( R′∉
17. Матриця
2 3 4
1 ∞ ∞ 0
3 ∞ ∞ 0
4 0 0 ∞
визначає множину обходів )}2,3{( з нижньою границею += )5,6()2,3( φφ
88979)2,3(~
=+=+ A .
18. У матриці, яка відповідає вершині })5,6{( R′∉ , покладаємо ∞=32d ,
виключаємо рядки 3, 4 і стовпці 2, 3.
А.В. Морозов, А.В. Панішев
ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 66
19. У результаті отримаємо матрицю з єдиного елемента (1, 4) і, відпо-
відно, обхід (2, 6), (6, 5), (5, 1), (1, 4), (4, 3), (3, 2) вартістю =′∉ ))2,3(( Rφ
.79079))5,6(( 43 =+=+′∉= dRφ
20. Допустимий розв’язок задачі ),3,4(),4,1(),1,5(),5,6(),6,2{()( =Rz
)}2,3( з вартістю 79))(( =RzC є оптимальним. Дерево розв’язків задачі
зображено на рисунку.
ВИСНОВКИ
Сформульовано ГЗСЛ. На основі класичного методу Літтла побудовано мо-
дифікацію методу, яка дозволяє знаходити розв’язок задачі або встановлю-
вати його відсутність. Перед застосуванням алгоритму пропонується викорис-
тати процедуру вершинно-реберного перетворення [5], яке дає можливість
перевірити необхідні умови існування розв’язку задачі, і, можливо, зменши-
ти розмірність задачі. Проілюстровано роботу цього алгоритму на прикладі.
ЛІТЕРАТУРА
1. Garashchenko I., Panishev A. Method of finding hamilton routes in transport net-
work // Artificial Intelligence and Decision Making.: ITHEA, Sofia. — 2008. —
№ 7. — P. 43–48.
2. Гаращенко И.В., Морозов А.В., Панишев А.В. Метод решения гамильтоновой
задачи коммивояжера // Искусственный интеллект. — 2008. — № 3. —
С. 630–637.
3. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. —
М.: Мир, 1982. — 416 c.
4. Теория расписаний и вычислительные машины: пер. с англ. / Под. ред.
Э.Г. Коффмана. — М.: Наука, 1984. — 335 с.
5. Морозов А.В., Панишев А.В. Вершинно-реберное преобразование в гамиль-
тоновой задаче о сельском почтальоне // Искусственный интеллект. —
2009. — № 3. — С. 138–143
6. Яблонский А.А. Минимизация кольцевых маршрутов доставки продукции потреби-
телям // Экономика и математические методы. — 2009. — № 3. — C. 124–131.
Надійшла 21.01.2010
Рисунок. Дерево розв’язків
)}6,2{( )}2,6{(
})6,5{( R′∉ )}6,5{(
78)6,2( =φ 78)2,6( =φ
79))6,5(( =′∉ Rφ
)}5,6{(})5,6{( R′∉
86)5,6( =φ79))5,6(( =′∉ Rφ
)}2,3{(})2,3{( R′∉
88)2,3( =φ
74)( =Rφ
87)6,5( =φ
79))2,3(( =′∉ Rφ
)}({ Rz
|