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

Abstract

Предметом исследований является решение задачи поиска гамильтонова цикла на графе, которая в дискретной математике относится к NP классу сложности и по-прежнему сохраняет к себе интерес. Целью работы является разработка нового алгоритма решения этой задачи, гарантирующего нахождение оптимального решения с полиномиальными затратами времени. В работе [1] был выполнен анализ современного состояния проблемы, отмечены недостатки существующих методов решения, изложены новые принципы и метод нахождения решения. Известные методы решения задачи основаны на реализации перебора возможных вариантов решений или на интуитивных эвристиках. Методы с перебором решений неприемлемы по затратам так как характеризуются неполиномиальными затратами времени. Эвристические методы удовлетворительны по времени, но не гарантируют нахождение оптимального решения. Популярность методов перебора объясняется простотой линейного поиска в заранее известном множестве допустимых решений задачи. Но факториальная зависимость мощности множества решений (n-1)! от числа вершин графа n делает невозможным применение таких методов для задач большого размера на практике. Желание существенно снизить временные затраты приводит к попыткам обоснованного редуцирования множества перебора либо к разработке различных эвристик, что фактически свидетельствует о невозможности сформулировать условия нахождения оптимального решения задачи в целом. В данной статье представлены описание условий, определяющих нахождение оптимального решения задачи и полиномиальный алгоритм решения задачи, воплощающий описанный метод. Поиск оптимального решения задачи сводится к поиску замкнутого пути в новом графе кратчайших путей. Граф кратчайших путей строится на основе исходного графа задачи, для чего используется алгоритм Дейкстры. Множество перебора для определения оптимального решения задачи состоит из решений, которые строятся из каждой вершины графа в графе кратчайших путей. Размер этого множества оценивается как n(n -1). Разработанный параллельный алгоритм гарантирует отыскание оптимального решения, значительно сокращает исходное пространство поиска, позволяет находить решение с полиномиальной сложностью. Тестирование программы показало работоспособность разработанного метода и алгоритма решения задачи.

The subject of research is the solution of the problem of finding a Hamiltonian cycle on a graph, which in discrete mathematics belongs to the NP complexity class and still retains interest. The aim of this work is to develop a new algorithm for solving this problem, which guarantees finding the optimal solution with polynomial time. In [1], an analysis of the current state of the problem was performed, the shortcomings of existing methods of solving were noted, and new principles and method of finding solution were presented. Known methods for solving the problem a re based on the implementation of a search of possible solutions or on intuitive heuristics. Enumeration methods of solutions are unacceptable in terms of costs, since they characterized by non-polynomial time. Heuristic methods are satisfactory in time, but they do not guarantee finding the optimal solution. The popularity of enumeration methods is explained by the linear simplicity of searching in a pre-known set of acceptable solutions to the problem. But the factorial dependence of the power of the set of solutions (n-1)! from the number of vertices of the graph n makes it impossible to use such methods for large-size problems in practice. The desire to significantly reduce time costs leads to attempts to reasonably reduce the enumeration set or to the development of various heuristics, which actually indicates that it is impossible to formulate conditions for finding the optimal solution to the problem as a whole. This article describes the conditions that determine the optimal solution of the problem and a polynomial algorithm for solving the problem that embodies the described method. Finding the optimal solution to the problem is reduced to finding a closed path in a new graph of shortest paths. The shortest paths graph built on the original graph of the problem by using Dijkstra's algorithm. The enumeration set for determining the optimal solution of the problem consists of solutions that are constructed from each vertex of the source graph in the shortest paths graph. The size of this set is estimated as n(n-1). The developed parallel algorithm guarantees finding the optimal solution, significantly reduces the initial search space, and allows you to find a solution with polynomial complexity. Testing of the program showed the efficiency of the developed method and algorithm for solving the problem.

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