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

курсовая работа

Вступ

У 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. Порівнюємо довжину гамильтонова контуру з нижніми межами обірваних гілок. Якщо довжина контуру не перевищує їх нижніх меж, то завдання виконане. В іншому випадку розвиваємо гілки підмножин з нижньою межею, меншою отриманого контуру, до тих пір, поки не отримаємо маршрут з меншою довжиною або не переконаємося, що такого не існує.

Делись добром ;)