Hamiltonian path quick search method based on adjacent rectangles

Abstract

The invention relates to the field of computer graphics and geographic information science, and particularly discloses a Hamiltonian path quick search method based on adjacent rectangles. The method comprises the following steps of S1, acquiring the node sample data; S2, constructing a minimum bounding rectangle of the node samples; S3, measuring the average adjacent distance of the nodes; S4, dividing the minimum bounding rectangle into a plurality of equal adjacent rectangles along a transverse axis or a longitudinal axis by taking an integral multiple of the average adjacent distance as a reference; S5, connecting the nodes in each adjacent rectangle sequentially along the transverse axis direction or the longitudinal axis direction to form a connecting line; and S6, connecting the connecting lines of adjacent rectangles in sequence, so that all the connecting lines are combined into one connecting line, and a result is a search result of an Hamiltonian path. According to the Hamiltonian path rapid search method based on the adjacent rectangles, the principle is simple, the processing difficulty, cost and time can be effectively reduced, and the search 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 fast search method for Hamiltonian paths based on adjacent rectangles. Background technique [0002] The Hamiltonian path was proposed by the astronomer William Rowan Hamilton to find a path that passes through all other cities exactly once from a given start point to a given end point in a map network with multiple cities. [0003] The traveling salesman problem, namely the TSP problem (Traveling Salesman Problem) is also translated as the traveling salesman problem and the salesman problem. It is one of the famous problems in the field of mathematics. Assuming that a traveling merchant wants to visit N cities, he must choose the path he wants to take. The limit of the path is that each city can only be visited once, and in the end he must return to the original starting city. The goal of path selection is that the required path distance is...

AI Technical Summary

Problems solved by technology

[0008] Although the research on the Hamiltonian path problem has made some progress in the era of parallel computing, in view of the fact that the traditional algorithm only optimizes the combination of nodes sequentially, without in-depth consideration of the problem space relationship, so few scholars in the current research have discovered this problem Hidden space constraints are used for path search to prevent the amount of computation from spreading exponentially, so as to reduce the difficulty, cost and time of processing

Images