Метод найближчого сусіда

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

Пояснення алгоритму

Формулюється таким чином: Алгоритм найближчого сусіда починається в довільній точці та поступово відвідує кожну найближчу точку, яка ще не була відвідана. Пункти обходу плану послідовно включаються до маршруту, причому, кожен черговий пункт, що включається до маршруту, повинен бути найближчим до останнього вибраного пункту серед усіх інших, ще не включених до складу маршруту. Алгоритм завершується, коли відвідано всі точки. Остання точка з'єднується з першою.

Вхідні дані: множина точок V розмірністю N Вихідні дані: маршрут Т, що складається з послідовності відвідування точок множини V

Кроки алгоритму (варіант 1)
  1. Вибрати довільну точку V1
  2. Т1 = V1
  3. Для і=2 до і=N виконати:
  4. Вибрати точку Vi, найближчу до точки Ті-1
  5. Ti = Vi
  6. Т N +1 = V1
  7. Кінець алгоритму[1]

Кроки алгоритму (варіант 2)
  1. Довільно обрати поточну точку
  2. Знайти найкоротше ребро, що сполучає поточну точку з досі ще не відвіданою точкою V
  3. Зробити точку V поточною
  4. Позначити точку V, як відвідану
  5. Коли всі точки розмірності N відвідані, припинити пошук маршруту
  6. Перейти до другого кроку

Алгоритм простий у реалізації, швидко виконується, але, як і інші «жадібні» алгоритми, може видавати неоптимальні рішення. Обчислювальна складність алгоритму — O(n2). Результатом виконання алгоритму найближчого сусіда є маршрут, приблизно на 25% довший від оптимального. Одним з евристичних критеріїв оцінки рішення є правило: якщо шлях, пройдений на останніх кроках алгоритму, зіставний зі шляхом, пройденим на початкових кроках, то можна умовно вважати знайдений маршрут прийнятним, інакше, імовірно, існують кращі рішення. Інший варіант оцінки рішення полягає у використанні алгоритму нижньої граничної оцінки. Другий критерій оцінки рішення полягає в застосуванні алгоритму нижньої граничної оцінки.[2]

Для будь-якої кількості міст більшій за три в задачі комівояжера можна підібрати таке розташування міст (значення відстаней між вершинами графу і вказівка ​​початкової вершини), що алгоритм найближчого сусіда буде видавати найгірше рішення.

Посилання
  • Алгоритм найближчого сусіда на Mathcad Calculation Server
  • Gutin, A. Yeo and A. Zverovich, Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP. Discrete Applied Mathematics 117 (2002), 81-86.
  • J. Bang-Jensen, G. Gutin and A. Yeo, When the greedy algorithm fails. Discrete Optimization 1 (2004), 121–127.
  • G. Bendall and F. Margot, Greedy Type Resistance of Combinatorial Problems, Discrete Optimization 3 (2006), 288–298.

Примітки
  1. Базилевич Р., Кутельмах Р. «Дослідження ефективності існуючих алгоритмів для розв'язання задачі комівояжера», 2009
  2. G. Gutin, A. Yeo and A. Zverovich, 2002
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.