DEFERRED SOLUTIONS METHOD DEVELOPMENT FOR CONSTRUCTING A HAMILTONIAN CYCLE SEARCH ALGORITHM ON A GRAPH

Abstract

The subject of research is the solution of the problem of finding a Hamiltonian cycle on a graph, which belongs to the NP complexity class. The aim of the work is to develop an effective polynomial algorithm for its optimal solution. The paper analyzes the problem and the existing methods of its solution, identifies the shortcomings of these methods. It is showing that the main obstacle remains the inability to formulate the conditions for finding the optimal solution. As a result, the methods for solving this problem based on enumeration over acceptable solutions or on intuitive heuristics. Heuristic methods do not guarantee finding the optimal solution. Enumeration methods are popular because of a simple linear search scheme in a pre-known set of valid solutions to the problem. They allow you to find the optimal solution, but require a lot of time. In enumeration algorithms, valid solutions can be obtain by using graph traversal algorithms, but the factorial cost of enumeration requires reducing the enumeration space, for example, using the branch-and-bound method. This method is based on an ordered search of acceptable solutions, considering only the most promising ones, and discarding at once the whole sets of solutions that are not such. For the method to work, it is important to determine the cost function of a partial solution that depends on certain parameters, which is difficult, and perhaps impossible for the problem under consideration. If the function generates a probabilistic estimate, there is a risk of losing the optimal solution to the problem when it is discarding. The only reliable estimate for a valid solution is the length of the cycle, which, unfortunately, becoming known after its formation. As an alternative, the article proposes a new method of deferred solutions, according to which all possible partial solutions are constructed and stored simultaneously. Each partial solution is characterizing by its own evaluation. At each step, a partial solution is completing by adding a vertex to it, to which you can go from its last vertex – as many new partial solutions are building, as there are options for going from its last vertex. The generated partial solutions are saving, and the current worked-out solution is deleting. To perform the next step, the partial solution that has the smallest length estimate is selecting. Execution continues until the optimal solution is not build. The proposed method solves the problem under consideration, but its application for large graphs requires the selection of a correct estimate of partial solutions.