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

Abstract

В дискретной математике существует много задач, которые относятся к NP классу сложности. Решение этих задач имеет как теоретическую, так и практическую ценность. Одной из них является задача поиска гамильтонова цикла на графе. Целью работы является разработка нового метода и алгоритма решения этой задачи предпочтительного имеющимся по затратам времени и качеству получаемого решения. В работе выполнен анализ проблемы и существующих методов её решения, определены недостатки этих методов. Показано, что все известные методы решения этой задачи строятся на реализации перебора вариантов решений либо на интуитивных эвристиках. Первые из них характеризуются неполиномиальными затратами времени, а вторые – не обеспечивают получение оптимального решения. Причиной такого состояния является невозможность сформулировать условия, определяющие оптимальное решение задачи. В таком случае единственно возможным способом решения задачи по-прежнему остаётся перебор вариантов, а для снижения затрат нахождения решения необходимо прибегать к сокращению пространства перебора вариантов. В работе изложены новые принципы нахождения решения и предложен новый метод решения задачи. На основе нового метода разработан полиномиальный алгоритм решения задачи. Поиск гамильтонова цикла в графе сводится к поиску замкнутого пути в новом графе кратчайших путей. Для построения графа кратчайших путей используется алгоритм Дейкстры. Пространство перебора вариантов решения задачи состоит из решений, которые строятся из каждой вершины графа в графе кратчайших путей. Тестирование разработанной программы показало работоспособность разработанного метода и алгоритма решения задачи. Предложенный метод решения существенно сокращает пространство перебора и позволяет находить оптимальное решение с полиномиальной сложностью, как в полном, так и неполном графах. Рассмотренный метод пригоден для параллельной реализации, что даёт дополнительный выигрыш во времени и позволяет на всю мощь использовать параллельные возможности современных многоядерных процессоров.In discrete mathematics, there are many problems that belong to the NP class of complexity. The solution of these problems has both theoretical and practical value. One of them is the problem of finding a Hamiltonian cycle on a graph. The aim of the work is to develop a new method and algorithm for solving this problem, which are preferable to the existing methods by time and quality of the solution. The paper analyzes the problem and existing methods of solving it, and identifies the disadvantages of these methods. It is shown that all known methods for solving this problem are based on the implementation of enumeration of solutions or on intuitive heuristics. The first of them are characterized by a non-polynomial amount of time for solving, and the second does not provide the optimal solution. The reason for this state is the inability to formulate conditions that determine the optimal solution of the problem. In this case, the only possible way to solve the problem is still to enumerate over the options, and to reduce the cost of finding a solution, you must resort to reducing the space for iterating over the options. The paper presents new principles for finding a solution and offers a new method for solving the problem. On the basis of the new method, a polynomial algorithm for solving the problem is developed. The search for a Hamiltonian cycle in a graph is reduced to the search for a closed path in a new graph of shortest paths. Dijkstra's algorithm is used to construct the shortest paths graph. The space of enumeration of solutions to the problem consists of solutions that are constructed from each vertex of the graph in the shortest paths graph. Testing of the developed program showed the efficiency of the developed method and algorithm for solving the problem. The proposed solution method significantly reduces the search space and allows us to find the optimal solution with polynomial complexity, both in full and incomplete graphs. The considered method is suitable for parallel implementation, which gives an additional gain in time and allows you to fully use the parallel capabilities of modern multi-core processors.