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

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

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

1. Метод редукції рядків та колонок.
2. Метод осереднених коефіцієнтів.
3. Метод Монте-Карло.
4. Метод найближчого сусіда.

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

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