Simple optimization method of Hamiltonian path

Abstract

The invention relates to the field of computer graphics and geographic information science, and particularly discloses a simple optimization method of a Hamiltonian path, which is characterized by comprising the following steps: S1, acquiring an initial solution of the Hamiltonian path of a node sample; S2, constructing a filtering factor, and filtering nodes on the Hamiltonian path initial solution through the filtering factor; and S3, repeating the filtering step in the step S2, calculating the length of the Hamiltonian path after each time of filtering, if the length of the Hamiltonian path after the next time of filtering is greater than the length of the Hamiltonian path after the previous time of filtering, taking the Hamiltonian path after the previous time of filtering as a final result, or when the positions of all nodes before and after filtering are not changed, taking the obtained result as a final result. According to the simple optimization method for the Hamiltonian path, the principle is simple, the optimization difficulty, cost and time can be effectively reduced, and the optimization efficiency of the Hamiltonian path is improved.

Description

technical field [0001] The invention relates to the fields of computer graphics and geographic information science, in particular to a simple optimization method for a Hamiltonian path. Background technique [0002] The TSP problem is the first of the seven century problems in the 21st century. It has been proved to be a complete NP problem. The main reasons for the complexity of the solution process are as follows: First, the distribution of target points exists in two The shortest path between points is also a two-dimensional distribution, which means that the problem is the entanglement of two two-dimensional problems. Traditional algorithms can solve the shortest path between two points, but it is difficult to solve the TSP problem of multi-dimensional entanglement. A simple analysis shows that no matter how the computational complexity of the shortest path between two points is optimized, it cannot be lower than two-dimensional, that is, the quadratic of the number of n...

AI Technical Summary

Problems solved by technology

[0002] The TSP problem is the first of the seven century problems in the 21st century. It has been proved to be a complete NP problem. The main reasons for the complexity of the solution process are as follows: First, the distribution of target points exists in two The shortest path between points is also a two-dimensional distribution, that is to say, the problem is the entanglement of two two-dimensional problems. The traditional algorithm can solve the shortest path between two points, but it is difficult to solve the multi-dimensional entangled TSP problem.

The initial solution of the Hamiltonian path obtained by the existing Hamiltonian path solving method is usually not the shortest Hamiltonian path. Therefore, it is urgent to provide a simple solution method to optimize the initial solution of the Hamiltonian path and obtain a shorter Hamiltonian path. Dayton path

Images