Обчислювальна математика

Спеціальність ПЗ

5-й семестр

Конспект лекцій

Лекція 1

Загальний опис методу гілок і меж організації пів-ного переборуможливостей. Рішення задачі про комівояжера методом гілок і меж:основна схема.

Хай - кінцеве безліч і - ве-громадської-значнафункція на ньому; потрібно знайти мінімумцієї функції і елемент множини, на якому цей мінімумдосягається.

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

Метод гілок і меж - це один з методів організації повногоперебору. Він застосовується не завжди, а тільки тоді, коливиконуються специфічні додаткові умови на множ -ство M і мінімізіруемую на ньому функцію. А саме, - припустимо, що є матеріально-значна функція (на безлічіпідмножин множини M з наступними двома властивостями:

1) для (тут - безліч, що складаєтьсяз єдиного елементу);

2) якщо і, то.

У цих умовах можна організувати перебір елементів множини M зметою мінімізації функції на цій безлічі так: розіб'ємо безліч M на частини (будь-яким способом) і вибе -рем ту з його частин (1, на якій функція (мінімальна; за-тим розіб'ємона кілька частин безліч (1 і виберемо ту з його частин (2, на якіймінімальна функція (; потім разо-б'ємо (2 на кілька частин і виберемо туз них, де мінімальна-ну (, і так далі, поки не прийдемо до якого-небудьодноелементні-му безлічі.

Це одноелементні безліч називається рекордом.
Функція (, якої ми при цьому виборі користуємося, називаєтьсяоціночної. Очевидно, що рекорд не зобов'язаний доставляти мінімумфункції f, а проте, ось яка виникає можливість скоротитиперебір за сприятливих обставин.

Описаний вище процес побудови рекорду складався з послідовнихетапів, на кожному з яких фіксувалосядекілька множин і вибиралося потім одне з них. Нехай
 - Підмножини множини M, що виникли на предпослед-ньому етапіпобудови рекорду, і нехай безліч виявилосявибраним за допомогою оціночної функції. Саме при розбив-ванні і виникрекорд, який зараз для визначеності позначимо через.
Відповідно до сказаного вище,,
; Крім того, з визначення оціночної функції,.

Припустимо, що, тоді для будь-якого елемента m безлічі M,належить множині, будуть вірні не -рівності, це значить, що при повному пере -бору елементів з M елементи з вже взагалі не треба рас -сматрівать. Якщо ж нерівність не буде виконан -але, то всі елементи з треба послідовно порівняти з най -денним рекордом і як тільки знайдеться елемент, що дає мен -шиї значення оптимізується функції, треба їм замінити ре-корд і продовжитиперебір. Остання дія називаєтьсяполіпшенням рекорду.

Слова метод гілок і меж пов'язані з природною гра -фіческой інтерпретацією усього викладеного: будується багато -рівневе дерево, на нижньому поверсі якого розташовуютьсяелементи множини M, на якому гілки ведуть до рекорду і йогополіпшенням і на якому частина гілок залишаються «обірваними»,тому що їх розвиток виявилося недоцільним.

Ми розглянемо зараз перший з двох запланованих уцьому курсі прикладів застосування методу гілок і меж - ре-шеніе задачі прокомівояжера. Ось її формулювання.

Є декілька міст, з'єднання деяких обра-зом з дорогамипевною довжиною; потрібно встановити, має -ся чи шлях, рухаючись по якому можна побувати в кожному горо -де тільки один раз і при цьому повернутися до міста, звідки шлях був початий
( «Обхід комівояжера»), і, якщо такий шлях має -ся, встановити найкоротший з таких шляхів.

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

Очевидно, у повному Орграф цикли зазначеного вище типу є. Зауважимо,що питання про наявність в Орграф Гамільтона циклу досить розглянутияк окремий випадок задачі про кого-мівояжере для повних Орграф.
Дійсно, якщо даний Орграф не є повним, то його можнадоповнити до повного відсутніми ребрами і кожному з доданих реберпри-писати вага (, вважаючи, що (- це «комп'ютерна нескінченність», тобтомаксимальне з усіх можливих у розглядах чисел. Якщо у зновупобудованому повному Орграф знайти тепер ліг-чайшій Гамільтоном цикл, то принаявність у нього ребер з вагою (можна буде говорити, що в даному, початковомуграфі «циклу комівояжера» немає. Якщо ж у повному Орграф найлегший га -мільтон цикл виявиться кінцевим за вагою, то він і буде іско-мим циклом ввихідному графі.

Отсюла випливає, що завдання про комівояжера досить ре-шити дляповних Орграф з ваговою функцією. Сформулюємотепер це в остаточному вигляді: Нехай - повний орієнтований граф і --вагова функція; знайти простий остовне орієнтований цикл ( «циклкомівояжера ») мінімальної ваги.

Нехай конкретний склад безлічі вершин і
 - Вагова матриця даного Орграф, тобто

,причому для будь-кого.

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

Введемо деякі терміни. Нехай є деяка чис -ловая матриця. Привести рядок цієї матриці означає виокрем-лити в рядкумінімальний елемент (його називають константою приведення) і відняти його звсіх елементів цього рядка. Очерет-видно, в результаті в цьому рядку на місцімінімального еле-мента виявиться нуль, а всі інші елементи будутьнеотріца-них. Аналогічний сенс мають слова привести стовпець матриці.

Слова привести матрицю по рядках означають, що всі рядки матрицінаводяться. Аналогічний сенс мають словапривести матрицю по стовпцях.

Нарешті, слова привести матрицю означають, що матрицяспочатку наводиться по рядках, а потім наводиться за стовп-ЦАМ.

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

Приступимо тепер до опису методу гілок і меж длярішення задачі про комівояжера.

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

Другий крок. Виберемо в матриці M1 найважчий нуль, і нехай він стоїть вклітині; фіксуємо ребро графа і раз -ділимо безліч (на дві частини: на частину, що складається зобходів, які проходять через ребро, і на частину,що складається з обходів, які не проходять через ребро.
Зіставимо безлічі наступну матрицю M1, 1: уматриці M1 замінимо на (число в клітці. Потім отриманий-ної матрицівикреслимо рядок номер i і стовпець номер j, причому в решти рядків істовпців збережемо їх вихідні номери. Нарешті, наведемо цю останнюматрицю і запам'ятаємо суму констант приведення. Отримана наведенаматриця і буде матрицею M1, 1; щойно запомненную суму константприведення додамо до ((() і результат, що позначається в по-дальшої через
((), Можна порівняти безлічі.

Тепер безлічі теж можна порівняти якусь матрицю
M1, 2. Для цього в матриці M1 замінимо на (число в клітціі отриману в результаті матрицю наведемо. Суму константприведення запам'ятаємо, а отриману матрицю позначимо через M1, 2. Додамозапомненную суму констант приведення дочисла ((() і отримане число, що позначається надалі че -рез ((), можна порівняти безлічі.

Тепер виберемо між множинами і те, наякому мінімальна функція ((тобто те з множин, якомувідповідає менше з чисел (() і (().

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

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

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