Полиномиальный алгоритм поиска гамильтонова цикла на графе

Abstract

Предметом досліджень є вирішення задачі пошуку гамільтонова циклу на графі, яка в дискретній математиці відноситься до NP класу складності та як і раніше зберігає до себе інтерес. Метою роботи є розробка нового алгоритму вирішення цієї задачі, що гарантує знаходження оптимального рішення з поліноміальними витратами часу. У роботі [1] був виконаний аналіз сучасного стану проблеми, відзначені недоліки існуючих методів вирішення, викладені нові принципи і метод знаходження рішення. Відомі методи вирішення задачі засновані на реалізації перебору можливих варіантів рішень або на інтуїтивних евристиках. Методи з перебором рішень неприйнятні за витратами бо характеризуються неполіноміальними витратами часу. Евристичні методи задовільні за часом, але не гарантують знаходження оптимального рішення. Популярність методів перебору пояснюється простотою лінійногопошуку в заздалегідь відомій безлічі допустимих рішень задачі. Але факторіальна залежність потужності множини рішень (n-1)! від числа вершин графа n унеможливлює застосування таких методів для задач великого розміру на практиці. Бажання істотно знизити часові витрати призводить до спроб обґрунтованого скорочення множини перебору або до розробки різних евристик, що фактично свідчить про неможливість сформулювати умови знаходження оптимального рішення задачі в цілому. У даній статті представлені опис умов, що визначають знаходження оптимального рішення задачі та поліноміальний алгоритм рішення задачі, що втілює описаний метод. Пошук оптимального рішення задачі зводиться до пошуку замкнутого шляху в новому графі найкоротших шляхів. Граф найкоротших шляхів будується на основі вихідного графа задачі, для чого використовується алгоритм Дейкстри. Множина перебору для визначення оптимального розв'язку задачі складається з розв'язків, які будуються з кожної вершини графа в графі найкоротших шляхів. Розмір цієї множини оцінюється як n(n-1). Розроблений паралельний алгоритм гарантує відшукання оптимального рішення, значно скорочує вихідний простір пошуку, дозволяє знаходити рішення з поліноміальною складністю. Тестування програми показало працездатність розробленого методу і алгоритму вирішення завдання.