Загальний опис методу гілок і меж організації повного перебору можливостей.
Рішення задачі про комівояжера методом гілок і меж: основна схема.
Нехай - кінцеве безліч і - матеріально-значна функція на ньому; потрібно
знайти мінімум цієї функції і елемент множини, на якому цей мінімум
досягається.
Коли є та чи інша додаткова інформація про безліч, вирішення цієї
завдання іноді вдається здійснити без повного перебору елементів всієї безлічі
M. Але частіше
всього повний перебір виробляти доводиться. У цьому випадку обов'язково виникає
завдання, як краще організувати перебір.
Метод гілок і меж - це один з методів організації повного перебору. Він
застосуємо не завжди, а тільки тоді, коли виконуються специфічні
додаткові умови на безліч M і мінімізіруемую на ньому функцію. А саме,
-
припустимо, що є матеріально-значна функція j на безлічі підмножин
безлічі M з наступними двома властивостями:
для (тут - безліч, що складається з єдиного елемента);
2) якщо і, то.
У цих умовах можна організувати перебір елементів множини M з метою
мінімізації функції на цій безлічі так:
розіб'ємо безліч M на частини (будь-яким способом) і виберемо ту з його частин W1, на
якій функція j мінімальна; потім розіб'ємо на кілька частин безліч W1 і
виберемо ту з його частин W2, на якій мінімальна функція j; потім розіб'ємо W2
на кілька частин і виберемо ту з них, де мінімальна j, і так далі, поки не
прийдемо до якого-небудь одноелементні безлічі.
Це одноелементні безліч називається рекордом.
Функція j, якої ми при цьому виборі користуємося, називається оціночної.
Очевидно, що рекорд не зобов'язаний доставляти мінімум функції f, а проте, ось яка
виникає можливість скоротити перебір за сприятливих обставин.
Описаний вище процес побудови рекорду складався з послідовних етапів, на
кожному з яких фіксувалося декілька множин і вибиралося потім одне з
них. Нехай - підмножини множини M, що виникли на передостанньому етапі
побудови рекорду, і нехай безліч виявилося обраним за допомогою оціночної
функції. Саме при розбивання і виник рекорд, який зараз для
визначеності позначимо через. Відповідно до сказаного вище,,; крім того, за
визначення оціночної функції,.
Припустимо, що, тоді для будь-якого елемента m множини M, що належить
численности, будуть вірні нерівності, це значить, що при повному переборі
елементів з M елементи з вже взагалі не треба розглядати. Якщо ж
нерівність не буде виконано, то всі елементи з треба послідовно
порівняти зі знайденим рекордом і як тільки знайдеться елемент, який дає меншу
значення оптимізується функції, треба їм замінити рекорд і продовжити перебір.
Остання дія називається поліпшенням рекорду.
Слова метод гілок і меж пов'язані з природною графічною інтерпретацією
усього викладеного: будується багаторівневе дерево, на нижньому поверсі якого
розташовуються елементи множини M, на якому гілки ведуть до рекорду і його
поліпшенням і на якому частина гілок залишаються "обірваними", тому що їх
розвиток виявилося недоцільним.
Ми розглянемо зараз перший з двох запланованих у цьому курсі прикладів
застосування методу гілок і меж - рішення задачі про комівояжера. Ось її
формулювання.
Є декілька міст, з'єднаних певним чином дорогами з відомою
завдовжки; потрібно встановити, чи є шлях, рухаючись по якому можна
побувати в кожному місті тільки один раз і при цьому повернутися до міста, звідки
шлях був початий ( "обхід комівояжера"), і, якщо такий шлях є, встановити
найкоротший з таких шляхів.
Формалізуємо умова в термінах теорії графів. Міста будуть вершинами графа, а
дороги між містами - орієнтованими (спрямованими) ребрами графа, на
кожному з яких задана вагова функція: вага ребра - це довжина відповідної
дороги. Шлях, який потрібно знайти, це - орієнтований остовне простий
цикл мінімальну вагу в Орграф (нагадаємо: цикл називається остовне, якщо він
проходить по всіх вершин графа; цикл називається простим, якщо він проходить по
кожній своїй вершині тільки один раз; цикл називається орієнтованим, якщо
початок кожного наступного ребра збігається з кінцем попереднього; вага циклу -
це сума ваг його ребер; нарешті, Орграф називається повним, якщо в ньому є
всі можливі ребра); такі цикли називаються також Гамільтона.
Очевидно, у повному Орграф цикли зазначеного вище типу є. Зауважимо, що питання
про наявність в Орграф Гамільтона циклу досить розглянути як окремий випадок
задачі про комівояжера для повних Орграф. Дійсно, якщо даний Орграф не
є повним, то його можна доповнити до повного відсутніми ребрами і
кожному з доданих ребер приписати вага