Задача комівояжера

Кільцем називається мережева топологія, при якій кожний вузол мережі поєднан з двома іншими вузлами, тобто для будь-якої пари вузлів існує 2 різних маршрута. Таким чином, зв’язність кільця дорівнює 2. Для заданної матриці відстаней між вузлами може бути побудовано кілька кілець, серед яких одне або декілька мають мінімальну довжину, тобто є оптимальними.

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

Неважко помітити, що всього існує (n-1)! можливих маршрутів, серед яких один або декілька оптимальні. В більшості випадків можна вважати, що відстань між містами i та j є симетрична, тобто відстань від міста i до міста j рівна відстані від міста j до міста i. Однак для алгоритму, що подано нижче, дане припущення не обов’язкове.

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

Підмножини множини всіх маршрутів можна розглядати як вузли дерева, а процес розбивання - як розгалуження дерева. Тому даний засіб називається засобом пошуку по дереву рішень, або алгоритмом гілок і меж.