Метод гілок та меж для рішення задач цілочисельного програмування
Вступ
У 1859 р. Сер Вільям Гамільтон, знаменитий математик, який дав світу теорію комплексного числа і кватерніони, запропонував дитячу головоломку, в якій пропонувалося здійснити «кругове подорож» по 20 містах, розташованих у різних частинах земної кулі. Кожне місто зєднувався дорогами з трьома сусідніми так, що дорожня мережа утворювала 30 ребер додекаедра, у вершинах якого знаходилися міста a, b,... t. Обовязковою умовою було вимога: кожне місто за винятком першого можна відвідати один раз.
Гамильтонова завдання про мандрівника нерідко перетворюється на задачу про комівояжера. Комівояжер - не вільно мандрівний турист, а ділова людина, обмежений тимчасовими, грошовими або будь-якими іншими ресурсами. Гамильтонова завдання може стати завданням про комівояжера, якщо кожне з ребер забезпечити числовою характеристикою. Це може бути кілометраж, час на дорогу, вартість квитка, витрата пального і т.д. Таким чином, умовні характеристики дадуть числовий ряд, елементи якого можуть бути розподілені між ребрами як завгодно.
Постановка завдання
Розглянемо задачу про комівояжера.
Є n міст, відстані (вартість проїзду, витрата пального на дорогу і т.д.) між якими відомі. Комівояжер повинен пройти всі n міст по одному разу, повернувшись в те місто, з якого почав. Потрібно знайти такий маршрут руху, при якому сумарний пройдене відстань (вартість проїзду і т.д.) буде мінімальним.
Очевидно, що завдання комівояжера - це проблема віднайдення найкоротшого гамильтонова циклу в повному графі.
Можна запропонувати наступну просту схему розвязання задачі комівояжера: згенерувати всі n! можливих перестановок вершин повного графа, підрахувати для кожної перестановки довжину маршруту і вибрати найкоротший. Однак, n! із зростанням n росте швидше, ніж будь-який поліном від n, і навіть швидше, ніж . Таким чином, рішення задачі комівояжера методом повного перебору виявляється практично нездійсненним, навіть при досить невеликих n.
Вирішити задачу комівояжера також можна за допомогою алгоритму Крускала і «деревяного» алгоритму. Ці методи прискорюють розробку алгоритму в порівнянні з методом повного перебору, проте не завжди дають оптимальне рішення.
Існує метод розвязання задачі комівояжера, який дає оптимальне рішення. Цей метод називається методом гілок і меж. Рішення задачі комівояжера методом гілок і меж по-іншому називають алгоритмом Літтла.
Якщо вважати міста вершинами графа, а комунікації (i, j) - його дугами, то вимога знаходження мінімального шляху, що проходить один і тільки один раз через кожне місто, і повернення назад, можна розглядати як знаходження на графі гамильтонова контуру мінімальної довжини.
Для практичної реалізації ідеї методу гілок і меж стосовно до задачі комівояжера потрібно знайти метод визначення нижніх меж підмножини і розбиття множини гамільтонових контурів на підмножини (розгалуження).
Визначення нижніх меж базується на тому твердженні, що якщо до всіх елементів i-го рядка або j-го стовпця матриці C додати або відняти число, то завдання залишиться еквівалентної колишньою, тобто оптимальність маршруту комівояжера не зміниться, а довжина будь-якого гамильтонова контуру зміниться на дану величину .
Опишемо алгоритм Літтла для знаходження мінімального гамильтонова контуру для графа з n вершинами. Граф представляють у вигляді матриці його дуг. Якщо між вершинами Xi і Xj немає дуги, то ставиться символ «?».
Алгоритм Літтла для розвязання задачі комівояжера можна сформулювати у вигляді наступних правил:
1. Знаходимо в кожному рядку матриці мінімальний елемент і віднімаємо його з усіх елементів відповідного рядка. Отримаємо матрицю, наведену по рядках, з елементами
.
2. Якщо в матриці , наведеної по рядках, виявляться стовпці, що не містять нуля, то наводимо її по стовпцях. Для цього в кожному стовпці матриці вибираємо мінімальний елемент, і віднімаємо його з усіх елементів відповідного стовпця. Отримаємо матрицю
,
кожен рядок і стовпець, якої містить хоча б один нуль. Така матриця називається наведеної по рядках і стовпцях.
3. Підсумовуємо елементи і , отримаємо константу приведення
,
яка буде нижньою межею множини всіх допустимих гамільтонових контурів, тобто
.
4. Знаходимо ступеня нулів для наведеної по рядках і стовпцях матриці. Для цього подумки нулі в Матіца замінюємо на знак «?» і знаходимо суму мінімальних елементів рядка і стовпця, відповідних цьому нулю. Записуємо її в правому верхньому кутку клітки:
.
5. Вибираємо дугу , для якої ступінь нульового елемента досягає максимального значення
.
6. Розбиваємо безліч всіх гамільтонових контурів на дві підмножини і . Підмножина гамільтонових контурів містить дугу , - її не містить. Для отримання матриці контурів , що включають дугу , викреслюємо в матриці рядок і стовпець . Щоб не допустити утворення негамільтонова контуру, замінимо симетричний елемент на знак «?».
7. Наводимо матрицю гамільтонових контурів . Нехай - константа її приведення. Тоді нижня межа множина визначиться так:
.
8. Знаходимо множину гамільтонових контурів, що не включають дугу. Виняток дуги досягається заміною елемента в матриці на ?.
9. Робимо приведення матриці гамільтонових контурів. Нехай - константа її приведення. Нижня межа множина визначається так:
.
10. Порівнюємо нижні множини, підмножини гамільтонових контурів і. Якщо , то подальшого розгалуження в першу чергу підлягає множина . Якщо ж , то розбиття підлягає множина .
Процес розбиття множин на підмножини супроводжується побудовою дерева розгалужень.
11. Якщо в результаті розгалужень отримуємо матрицю , то визначаємо отриманий розгалуженням гамільтонів контур і його довжину.
12. Порівнюємо довжину гамильтонова контуру з нижніми межами обірваних гілок. Якщо довжина контуру не перевищує їх нижніх меж, то завдання виконане. В іншому випадку розвиваємо гілки підмножин з нижньою межею, меншою отриманого контуру, до тих пір, поки не отримаємо маршрут з меншою довжиною або не переконаємося, що такого не існує.