Знаходження ровз'язку задачі комівояжера методом найближчого сусіда

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

Особливий інтерес, з практичної точки зору, представляє процес знаходження ровз'язку задачі комівояжера для великої (близько тисячі) кількості пунктів призначення. В цьому випадку, точні методи рішення задач такого типу не дають бажаного результату, так як вимагають величезних обчислювальних витрат, і процес вирішення займає надто багато часу. Тому на практиці, зазвичай, використовуються евристичні методи, серед яких найбільш використовуваним та відомим являється метод найближчого сусіда.

Основна його суть при розв'язку задачі комівояжера полягає в тому, що пункти призначення послідовно включаються в маршрут, причому кожний наступний пункт, що включається, вибирається таким чином, щоб він був найближчим до останнього вже включеному серед усіх пунктів, ще не включених в маршрут. Основним недоліком даного методу є те, що деякі міста «пропускаються» в ході роботи алгоритму, і в результаті доводиться їх включати в кінці маршруту з більш високими тарифами, що в свою чергу негативно впливає на кінцевий результат (збільшенням довжини маршруту, а відповідно, і затрат на переміщення).

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

Ілюстрація роботи алгоритму методу найближчого сусіда

Далі, запишемо алгоритм даного методу більш детально, після чого перейдемо до практичної части, де використовуючи метод найближчого сусіда знайдемо розв'язок деякої задачі комівояжера.

Отже, рішення задачі комівояжера згідно з методом найближчого сусіда складається з наступних етапів:

  1. Вибраємо, в якості початкового, довільний пункт.
  2. На кожному кроці, виконуємо по одному переміщенні, і повторюємо дану операцію до тих пір, поки не будуть відвідані всі пункті. Відмітимо, що при цьому кожне таке переміщення повино здійснюватись у найближчий до відвіданого на попередньому кроці пункту.
  3. На останньому етапі, для того, щоб завершити маршрут, повертаємося у початковий пункт.

Розв'язок задачі комівояжера методом найближчого сусіда — приклад:

Нехай комівояжер повинен об'їхати п'ять міст, побувати в кожному по одному разу і повернутися у початкове. При цьому витрати на переміщення між містами повинні бути мінімальними. Тарифи на переміщення містяться в наступній таблиці.

zadacha_komivojagera_metod_najblugchoho_sysida1

Тарифи на переміщення між містами

Якщо почати маршрут з пункту під номером один, то скориставшись методом найближчого сусіда, отримаємо наступну послідовність обходу (маршрут комівояжера): . Відмітимо, що сумарна вартість даного маршруту (значення функції мети) становить  умовних одиниць.

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

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

Блок-схема алгоритму знаходження розв'язку задачі комівояжера методом найближчого сусіда

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар