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

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

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

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

Читати повністю