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

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

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

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

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

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

zadacha_komivojazhera_metod_podvijnoho_obhody122

Ілюстрація роботи алгоритму методу подвійного обходу мінімального кістяка

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

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

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

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

Метод подвійного обходу приклад

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

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

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

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

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

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

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

Метод подвійного обходу дерева блок-схема

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

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