Алгоритм найближчого сусіда

Алгоритм найближчого сусіда (Nearest neighbor algorithm) для розв’язання задачі комівояжера належить до алгоритмів побудови маршруту, що є найпростішими методами знаходження розв’язків задачі комівояжера.

Алгоритм найближчого сусіда є найприроднішим евристичним алгоритмом для розв’язання задачі комівояжера. Алгоритм починається в довільній точці та поступово відвідує кожну найближчу точку, що ще не була відвідана. Алгоритм завершується, коли відвідано всі точки. Остання точка з’єднується з першою. Обчислювальна складність алгоритму – O(N²).

АЛГОРИТМ НАЙБЛИЖЧОГО СУСІДА.

ВХІДНІ ДАНІ: множина точок V розмірністю N.

ВИХІДНІ ДАНІ: маршрут T, що складається з послідовності відвідування точок множини V.

1) Вибрати довільну точку v₁;

2) T₁ = v₁;

3) ДЛЯ i =2 ДО i= N ВИКОНАТИ

a. ВИБРАТИ точку v_i, найближчу до точки T_i-1;

b. T_i = v_i;

4) T_N+1 = v₁;

5) КІНЕЦЬ АЛГОРИТМУ.

Результатом виконання алгоритму найближчого сусіда є маршрут, приблизно на 15-25% довший від оптимального.

 

Алгоритм 2-opt

Алгоритм 2-opt (2-opt algorithm) належить до алгоритмів покращення маршруту (route improvement). Це методи, що поступово покращують початковий маршрут, отриманий за допомогою існуючого швидкого алгоритму побудови маршруту. Покращення відбувається завдяки зміні частин існуючого маршруту на коротші (локальна оптимізація). Алгоритми покращення маршруту забезпечують якість маршруту, на 3-10% гіршу від оптимального.

У класичній реалізації алгоритм 2-opt вилучає 2 ребра, що входять до маршруту і додає два нові таким чином, щоб новий маршрут став коротшим. Існує лише один варіант заміни двох ребер на нові два, при якому новий маршрут залишиться маршрутом, а не утворяться 2 цикли.

Алгоритм триває доти, поки не залишиться можливих замін, що оптимізують маршрут. Одержаний маршрут називають 2-оптимальним.

АЛГОРИТМ 2-OPT.

ВХІДНІ ДАНІ: множина точок V розмірністю N.

ВИХІДНІ ДАНІ: маршрут T_2-opt, що складається з послідовності відвідування точок множини V.

1) СТВОРИТИ початковий маршрут T за допомогою деякого алгоритму побудови маршруту;

2) ДЛЯ i =1 ДО i = N ВИКОНАТИ

a. ДЛЯ j =1 ДО j = N ВИКОНАТИ

Алгоритм Ліна-Кернігана

Впродовж довгих років алгоритм Ліна-Кернігана (Lin-Kernighan algorithm) залишається одним з найкращих евристичних методів розв’язування задачі комівояжера. Алгоритм забезпечує знаходження маршруту, в середньому не довшого на 2-3% від оптимального. Основний підхід Ліна-Кернігана базується на техніці локальної оптимізації k-opt, де k – змінне число, яке змінюється на кожному кроці виконання алгоритму. Це забезпечує одержання значно кращих розв’язків у порівнянні з алгоритмами 2-opt та 3-opt, у яких число k є фіксованим. Алгоритм не є простим щодо реалізації, у сучасних версіях має багато параметрів. Існує багато покращень алгоритму для того, щоб збільшити його швидкодію. Обчислювальна складність алгоритму - O(N^2,2). Лін-Керніган отримує початковий суб-оптимальний маршрут та оптимізує його за допомогою замін ребер. Для задачі розмірністю N точок розв’язок не є довшим у 4 разів від оптимального, а також ніколи не є гіршим за початковий маршрут. На практиці алгоритм виконується швидко. Час виконання алгоритму збільшується для задач з кластерним розподілом точок.

Алгоритм Ліна-Кернігана передбачає зміни ребер, що послідовно перетворює початковий маршрут в інший. Зміни тривають доти, поки не буде можливих замін ребер, що забезпечать одержання коротшого маршруту. Дано початковий маршрут T. На кожному кроці виконання алгоритм намагається знайти дві множини ребер X ={ x₁, x₂,…, x_k } та Y ={ y₁, y₂,…, y_k } такі, що якщо ребра з множини X вилучити з маршруту, а натомість додати ребра з множини Y, то в результаті отримаємо кращий маршрут. Ця взаємна заміна ребер називається заміною k-opt. Множини X та Y створюються послідовно, елемент за елементом. Спочатку вони порожні. На кожному кроці i пара елементів x_i, y_i додається до відповідних множин.

 

Алгоритм Дейкстри

Знаходить найкоротший шлях від однієї вершини графа до всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для графів без циклів від'ємної довжини.

Алгоритм:

Кожній вершині V зіставимо мітку - мінімальну відому відстань від цієї вершини до вершини а. Алгоритм працює покроково - на кожному кроці він «відвідує» одну вершину і намагається зменшувати мітки. Робота алгоритму завершується, коли всі вершини відвідані.

Ініціалізація. Мітка самої вершини a покладається рівною 0, мітки інших вершин - нескінченності. Це відображає те, що відстані від a до інших вершин поки невідомі. Всі вершини графа позначаються як невідвідані.

Крок алгоритму. Якщо всі вершини відвідані, алгоритм завершується. В іншому випадку, із ще не відвіданих вершин вибирається вершина u, що має мінімальну позначку. Ми розглядаємо всілякі маршрути, в яких u є передостаннім пунктом. Вершини, в які ведуть ребра з u, назвемо сусідами цієї вершини. Для кожного сусіда вершини u, крім позначених як "відвідані", розглянемо нову довжину шляху, що дорівнює сумі значень поточної мітки u і довжини ребра, що з'єднує u з цим сусідом. Якщо отримане значення довжини менше значення мітки сусіда, замінимо значення мітки отриманим значенням довжини. Розглянувши всіх сусідів, помітимо вершину u як відвідану і повторимо крок алгоритму.

Обчислювальна складність алгоритму: O(n²).

Ємнісна складність: залежить від структури представлення даних, мінімально може бути O(n*log n + m).

 

Хвильовий алгоритм

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

Алгоритм:

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

Обчислювальна складність: O(n²).

Ємнісна складність: залежить від розміру матриці заповнення, можливо – O(m*n).