Розв’язання задачі комівояжера різними програмними методами
1.1 Загальний опис
Завдання комівояжера (надалі скорочено - ЗК) є одним із знаменитих завдань теорії комбінаторики. Вона була поставлена в 1934 році, і про неї, як про Велику теорему Ферма обламували зуби найкращі математики. У своїй галузі (оптимізації дискретних завдань) ЗК є своєрідним полігоном, на якому випробовуються нові методи.
Постановка завдання така.
Комівояжер (бродячий торговець) повинен вийти з першого міста, відвідати по разу у невідомому порядку міста 2,1,3.n і повернутися до першого міста. Відстань між містами відома. У якому порядку слід обходити міста, щоб замкнутий шлях (тур) комівояжера був найкоротшим?
Щоб привести завдання до наукового вигляду, запровадимо деякі терміни. Отже, міста перенумеровані числами j Т = (1,2,3. n). Тур комівояжера може бути описаний циклічною перестановкою t =( j 1 , j 2 . j n , j 1 ), причому всі j 1 .. j n різні номери; повторюється на початку і наприкінці j 1 показує, що перестановка зациклена. Відстань між парами вершин С ij утворюють матрицю С. Завдання полягає в тому, щоб знайти такий тур t, щоб мінімізувати функціонал
Щодо математизованого формулювання ЗК доречно зробити два зауваження.
По-перше, у постановці З ij означали відстані, тому вони мають бути неотрицательными, тобто. для всіх j Т:
(останнє рівність означає заборона петлі в турі), симетричними, тобто. для всіх i, j:
і задовольняти нерівність трикутника, тобто. для всіх:
C ij + C jk C ik
У математичній постановці йдеться про довільну матрицю. Зроблено це оскільки є багато прикладних завдань, які описуються основний моделлю, але всім умовам (2)-(4) не задовольняють.Особливо часто порушується умова (3) (наприклад, якщо С ij не відстань, а плата за проїзд: часто туди квиток коштує одну ціну, а назад іншу). Тому ми розрізнятимемо два варіанти ЗК: симетричну задачу, коли умова (3) виконано, і несиметричну - в іншому випадку. Умови (2)-(4) за умовчанням вважатимемо виконаними.
Друге зауваження стосується всіх можливих турів. У несиметричній ЗК всі тури t = ( j 1 , j 2 . j n , j 1 ) і t ? = ( j 1 , j n . j 2 , j 1 ) мають різну довжину і повинні враховуватися обидва. Різних турів очевидно (n-1)!.
Зафіксуємо на першому і останньому місці в циклічній перестановці номер j 1 , а n -1 номерів, що залишилися, переставимо всіма ( n -1)! можливими способами. В результаті отримаємо усі несиметричні тури. Симетричних турів є вдвічі менше, т.к. кожен зарахований двічі: як t і як t?.
Можна уявити, що складається тільки з одиниць і нулів. Тоді можна інтерпретувати, як граф, де ребро ( i , j ) проведено, якщо С ij =0 і не проведено, якщо С ij =1. Тоді, якщо існує тур довжини 0, він пройде по циклу, що включає всі вершини по одному разу. Такий цикл називається гамільтоновим циклом. Незамкнений гамільтонів цикл називається гамільтоновим ланцюгом (гамільтоновим шляхом).
У термінах теорії графів симетричну ЗК можна сформулювати так:
Дана повна мережа з n вершинами, довжина ребра (i, j) = З ij. Знайти гамільтонів цикл мінімальної довжини.
У несиметричній ЗК замість "цикл" треба говорити "контур", а замість "ребра" - "дуги" чи "стрілки".
Деякі прикладні завдання формулюються як ЗК, але в них потрібно мінімізувати довжину не циклу гамільтона, а гамільтонового ланцюга. Такі завдання називаються незамкненими. Деякі моделі зводяться до завдання прокількох комівояжерах, але ми тут їх розглядати не будемо.
1.2. Методи вирішення ЗК
1.2.1. Метод гілок та кордонів
Загальна ідея тривіальна: потрібно розділити величезну кількість варіантів, що перебираються на класи і отримати оцінки (знизу в задачі мінімізації, зверху в задачі максимізації) для цих класів, щоб мати можливість відкидати варіанти не по одному, а цілими класами. Складність полягає в тому, щоб знайти такий поділ на класи (гілки) та такі оцінки (кордони), щоб процедура була ефективною.
Викладемо алгоритм Літтла на прикладі 1 попереднього розділу. Повторно запишемо матрицю:
Нам буде зручніше трактувати С ij як вартість проїзду з міста i до міста j. Припустимо, що добрий мер міста j видав указ виплачувати кожному комівояжеру, що в'їхав у місто, 5 доларів. Це означає, що будь-який тур подешевшає на 5 доларів, оскільки у будь-якому турі потрібно в'їхати до міста j . Але оскільки всі тури поступово подешевшали, то колишній мінімальний тур і тепер коштуватиме найменше. Добрий вчинок мера можна представити як зменшення всіх чисел j-го стовпця матриці С на 5. Якби мер хотів спровадити комівояжерів з j-го міста і встановив нагороду за виїзд у розмірі 10 доларів, це можна було б висловити відніманням 10 з усіх елементів j-й того рядка. Це знову змінило б вартість кожного туру, але мінімальний тур залишився б мінімальним. Отже, доведено наступну лему.
Віднімаючи будь-яку константу з усіх елементів будь-якого рядка або стовпця матриці С, ми залишаємо мінімальний тур мінімальним.
Для алгоритму нам буде зручно отримати більше нулів у матриці С, не отримуючи там, однак, негативних чисел. Для цього ми віднімемо з кожного рядка її мінімальний елемент (це називається приведенням по рядках, див.табл. 3), а потім віднімемо з кожного стовпця матриці, наведеної по рядках, його мінімальний елемент, отримавши матрицю, наведену по стовпцях, див. 4).
Прочерки по діагоналі означають, що з міста в місто і ходити не можна. Зауважимо, що сума констант приведення по рядках дорівнює 27, сума по шпальтах 7, сума сум дорівнює 34.
Тур можна задати системою з шести підкреслених (виділених іншим кольором) елементів матриці, наприклад, такий, як показано на табл. 2. Підкреслення елемента означає, що в турі з i-го елемента йдуть саме в j-тий. Для туру із шести міст підкреслених елементів має бути шість, тому що в турі із шести міст є шість ребер. Кожен стовпець повинен містити рівно один підкреслений елемент (у кожне місто комівояжер в'їхав один раз), у кожному рядку повинен бути рівно один підкреслений елемент (з кожного міста комівояжер виїхав один раз); крім того, підкреслені елементи повинні описувати один тур, а не менші цикли. Сума чисел підкреслених елементів становить вартість туру. На табл. 2 вартість дорівнює 36, це мінімальний тур, який отриманий лексикографічним перебором.
Тепер розмірковуватимемо від наведеної матриці на табл. 2. Якщо ній вдасться побудувати правильну систему підкреслених елементів, тобто. систему, яка б задовольняла трьом вищеописаним вимогам, і цими підкресленими елементами будуть лише нулі, то ясно, що з цієї матриці ми отримаємо мінімальний тур. Але він же буде мінімальним і для вихідної матриці С, тільки для того, щоб отримати правильну вартість туру, потрібно буде додати всі константи приведення, і вартість туру зміниться з 0 до 34. Таким чином, мінімальний тур не може бути менше 34. Ми отримали оцінку знизу всім турів.
Тепер приступимо дорозгалуження. Для цього зробимо крок оцінки нулів. Розглянемо нуль у клітині (1,2) наведеної матриці. Він означає, що ціна переходу з міста 1 до міста 2 дорівнює 0. А якщо ми не підемо з міста 1 до міста 2? Тоді все одно потрібно в'їхати до міста 2 за ціни, вказані у другому стовпці; найдешевше за 1 (з міста 6). Далі все одно треба буде виїхати з міста 1 за ціну, вказану в першому рядку; найдешевше в місто 3 за 0. Підсумовуючи ці два мінімуми, маємо 1+0=1: якщо не їхати "по нулю" з міста 1 до міста 2, то треба заплатити не менше 1. Це і є оцінка нуля. Оцінки всіх нулів поставлено на табл. 5 правіше і вище за нуль (оцінки нуля, рівні нулю, не ставилися).
Виберемо максимальну з цих оцінок (у прикладі є кілька оцінок, рівних одиниці, виберемо першу з них у клітині (1,2)).
Отже, вибрано нульове ребро (1,2). Розіб'ємо всі тури на два класи, що включають ребро (1,2) і не включають ребро (1,2). Про другий клас можна сказати, що доведеться доплатити ще 1, так що тури цього класу коштують 35 або більше.
Що ж до першого класу, то ньому треба розглянути матрицю на табл. 6 з викресленим першим рядком та другим стовпцем.