Користувач:Atomchuk
Оптимальні розв’язки задачі комівояжера можуть бути отримані за допомогою методів лінійного програмування. Традиційно методи для розв’язання задачі комівояжера поділяються на[1]:
- Алгоритми для знаходження точних маршрутів (потребують значних часових затрат і підходять лише для задач малих розмірностей);
- Евристичні алгоритми, що забезпечують якість маршруту, близьку до оптимальної, але не вважаються оптимальними.
Точні алгоритми для розв’язування задачі комівояжера забезпечують одержання оптимального розв’язку. Розрізняють три основні типи точних алгоритмів для розв’язання задачі:
- Метод гілок та меж, що може бути використаний для розв’язання задач розмірністю 50-100 точок;
- Прогресивні методи покращання, що використовують методи лінійного програмування; використовуються для задач розмірністю 120–200 точок;
- Сучасні реалізації методів гілок та меж та відсікаючих площин, що ґрунтуються на лінійному програмуванні; забезпечують оптимальні та ефективні розв’язки для задач розмірностями до 5000 точок, також цей метод у поєднанні з алгоритмом Ліна–Кернігана–Гельсгауна був застосований для знаходження оптимального маршруту для задачі розмірністю 85900 точок – найбільшої задачі, що розв’язана сьогодні оптимально. Точний розв’язок для 15112 міст Німеччини був знайдений у 2001 роціза допомогою методу відсікаючих площин, запропонованого Данцігом, Фалкерсоном та Джонсоном у 1954 році, що ґрунтується на методах лінійного програмування[2]. Обчислення проводилися на мережі зі 110 процесорів, розміщених в університетах Princeton University та Rice University. Загальний час обчислень був еквівалентним 22,6 рокам роботи процесора Alpha 500 MHz.
Сьогодні існує багато наближених (евристичних) алгоритмів розв’язання задачі. Наближені алгоритми забезпечують одержання розв’язку задачі, близького до оптимального, але не гарантують його оптимальності. Сучасні реалізації можуть з великою ймовірністю знайти розв’язок для задач великих розмірностей (мільйонів точок) у припустимих часових межах, який може бути всього на 2–3% довший від оптимального. Евристичні алгоритми залежно від особливостей своєї роботи поділяються на такі основні типи:
- Конструктивні алгоритми. Це найшвидші за часом обчислень методи, що забезпечують найгіршу якість розв’язків. За кожен крок роботи алгоритму до існуючої частини знайденого маршруту додається нове ребро. Найкращі конструктивні алгоритми забезпечують якість, на 10– 15% гіршу від оптимального розв’язку;
- Алгоритми оптимізації маршруту. Методи, що поступово покращують початковий маршрут, отриманий за допомогою існуючого швидкого конструктивного алгоритму. Оптимізація відбувається завдяки зміні частин існуючого маршруту на коротші (локальній оптимізації). Забезпечують якість маршруту, на 3–10% гіршу від оптимального;
- Алгоритм Ліна–Кернігана та його модифікації. Це удосконалений алгоритм оптимізації маршруту, що забезпечує розв’язки, на 1–3% гірші від оптимального;
- Алгоритм Ліна–Кернігана–Гельсгауна. Модифікований алгоритм Ліна–Кернігана Келдом Гельсгауном, що забезпечує знаходження оптимальних розв’язків або дуже близьких до оптимальних (у межах до 1%);
- Генетичні алгоритми.
Конструктивні алгоритми належать до найпростіших методів знаходження розв’язків задачі комівояжера. За кожен крок виконання алгоритму до знайденої частини маршруту додається нове ребро. Алгоритм припиняє роботу, коли розв’язок знайдено і ніколи не намагається покращити його. До конструктивних алгоритмів належать:
- Алгоритм найближчого сусіда;
- Жадібний алгоритм;
- Алгоритм вставки.
Найприродніший евристичний алгоритм для розв’язання задачі комівояжера – алгоритм найближчого сусіда. Алгоритм починається в довільній точці та
поступово відвідує кожну найближчу точку, що ще не була відвідана. Алгоритм завершується, коли відвідано всі точки. Остання точка з’єднується з першою. Обчислювальна складність алгоритму – .
Жадібний алгоритм будує маршрут поступово, на кожному кроці додаючи найкоротше ребро, яке ще не належить маршруту. Ребро додається за умови, що воно не створить циклу всередині маршруту. Алгоритм завершується, коли додано N ребер або кожна точка має степінь 2. Кожне ребро може бути додане лише один раз. Обчислювальна складність алгоритму - .
Алгоритм вставки також є простим методом швидкого знаходження наближених розв’язків задачі. На початку роботи алгоритму визначається маршрут, що складається з трьох точок і формує трикутник. На кожному наступному кроці до маршруту додається найближча точка, що не належить йому. Обчислювальна складність алгоритму – .
Конструктивні алгоритми забезпечують найгіршу якість отриманих розв’язків задачі комівояжера при обчислювальній складності в середньому . Існують методи пришвидшення роботи описаних вище підходів. Зокрема завдяки методу, запропонованому Бентлі[3] – k-d-240 деревам, що ґрунтується на побудові ієрархічної декомпозиції вхідної області точок на частини, можна пришвидшити роботу алгоритмів до часу, еквівалентному O(nlog(n)). Алгоритми локальної оптимізації, що описані в наступних підрозділах, використовують розв’язки, отримані за допомогою методів побудови маршруту як початкові.
Після того, як за допомогою певного алгоритму побудови маршруту було одержано деякий розв’язок, є можливість його покращити. Найпоширенішими методами покращання маршруту є алгоритми локальної оптимізації 2-opt та 3-opt. У класичній реалізації алгоритм 2-opt вилучає 2 ребра, що входять до маршруту і додає два нові так, щоб новий маршрут став коротшим. Існує лише один варіант заміни двох ребер на нові два, при якому новий маршрут залишиться маршрутом, а не утворяться 2 цикли. Алгоритм 3-opt працює так само, як і 2-opt; відмінність полягає у тому, що замість заміни 2 ребер він замінює 3 ребра так, щоб маршрут став коротшим. Це означає, що існує 2 варіанти заміни 3 ребер.
Впродовж довгих років алгоритм Ліна–Кернігана залишається одним з найкращих евристичних методів розв’язування задачі комівояжера [33]. Алгоритм забезпечує знаходження маршруту, в середньому не довшого на 2% від оптимального. Основний підхід Ліна–Кернігана ґрунтується на техніці локальної оптимізації k-opt, де k – змінне число, яке змінюється на кожноаму кроці виконання алгоритму. Це забезпечує одержання значно кращих розв’язків порівняно з алгоритмами 2-opt та 3-opt, у яких число k є фіксованим. Проте алгоритм не є простим для реалізації, у сучасних версіях він має багато параметрів. Існує багато покращень алогритму для того, щоб збільшити його швидкодію. Обчислювальна складність алгоритму – . Алгоритм Ліна–Кернігана – алгоритм локальної оптимізації, що отримує початковий субоптимальний маршрут та оптимізовує його за допомогою замін ребер. Для задачі розмірністю N точок розв’язок не є довшим у 4 N разів від оптимального, а також ніколи не є гіршим за початковий маршрут. На практиці алгоритм виконується швидко. Проте час виконання алгоритму збільшується для задач із кластерним розподілом точок.
- ↑ Базилевич Р. Дослідження ефективності існуючих алгоритмів для розв’язання задачі комівояжера. / Р. Базилевич, Р. Кутельмах // Комп'ютерні науки та інформаційні технології [Текст] : [зб. наук. пр.] / відп. ред. Ю. М. Рашкевич. - Л.: Видавництво Національного університету "Львівська політехніка", 2009. - 279 c. : іл. - (Вісник / Національний університет "Львівська політехніка" ; № 650). - С. 235-244
- ↑ G. B. Dantzig, R. Fulkerson, and S. M. Johnson, Solution of a large–scale traveling salesman problem, Operations Research 2 (1954), pp. 393–410.
- ↑ J. L. Bentley, ‘‘Multidimensional binary search trees used for associative search,’’ Comm. ACM 18 (1975), 309–517
- використано матеріали зі статті у англійській Вікіпедії