CN111612257A - A Shortest Path Solving Method Based on Spatial Reduction - Google Patents

Abstract

The present invention aims to provide a method for solving the shortest path based on spatial naturalization, which includes the following steps: naturalizing a road network into a vector geographic space to obtain a starting point and a destination; taking the center of the line connecting the starting point and the destination as a dot , take the length of the connection between the origin and the destination as the diameter, construct the first circle including the origin and destination; find all the paths in the first circle, and perform topology faceting on these paths; The origin and destination connection line and topological facet are filtered to obtain several polygons connecting the origin and destination, and these polygons are merged; the merged polygons are divided into different parts according to the origin and destination. Path, the shorter path is selected, which is the obtained first initial path. The invention will make up for the difficult problem of selecting the evaluation function of the traditional A* algorithm, and solve the problem that the ant colony algorithm, the genetic algorithm, and the neural network algorithm can only solve the approximate solution and cannot obtain the mathematical optimal solution.

Description

A Shortest Path Solving Method Based on Spatial Reduction

technical field

The invention relates to the fields of computer graphics, geographic information science and logic, in particular to a method for solving the shortest path of base space reduction.

Background technique

The shortest path problem has always been a classic problem in computer science and geographic information science. Traditional similar problems are solved by classical computer algorithms such as ant colony algorithm, A* algorithm, Dijkstra algorithm, etc. Dijkstra algorithm can solve the mathematical optimal solution, but Low efficiency; other algorithms are highly efficient, but they cannot solve the mathematical optimal solution. The solution thinking of various algorithms is different, so it is difficult to take into account the problems of excellence and accuracy. The research directions are also divided into two mainstream directions: The search efficiency optimization of Dijkstra's algorithm and the accuracy improvement of other algorithms - so far no scholar has been able to unify the two, combining the high efficiency of other algorithms with the mathematically rigorous solution of Dijkstra's algorithm.

The solution of the shortest path problem has plagued many disciplines such as computer graphics, mathematics, logic, and geographic information science for decades. The direction of its research and solution has become alienated. Research in this field has reached a dead end and so far has not been able to resolve this contradiction. It can be seen from simple mathematical analysis that the shortest path must exist. Its characteristic is that the distance between any two points on the path is also the shortest, and the local solution and the overall solution are organically unified. Therefore, the research is naturally divided into two directions: ensuring the local and ensuring the whole.

It can be seen from the existence and geometric characteristics of the shortest shortest length that the problem is ultimately the comparison of lengths. The comparison of lengths is essentially the solution of the line problem, and the line is the boundary of the surface. Therefore, the problem solved by other algorithms can be reduced to the geometric space, and the geometric The method completes the reduction and optimization of the sample space, and then uses the Dijkstra algorithm to solve the optimal solution, and finally realizes the unification of all the shortest path algorithms in the space field, and achieves the unification of "fast" and "quasi" shortest path search.

SUMMARY OF THE INVENTION

In view of the above-mentioned defects of the prior art, in order to achieve the above-mentioned purpose, the present invention provides a method for solving the shortest path based on space reduction, to solve the divergence problem of the solution space when the shortest path is solved, including the following steps:

S1. Naturalize the road network to a vector geographic space to obtain the origin and destination;

S2. Taking the center of the line connecting the origin and the destination as the dot, and taking the length of the line connecting the origin and the destination as the diameter, construct the first circle including the origin and the destination;

S3. Find all the paths in the first circle, and perform topological facets on these paths;

S4, filter through the connection line between the origin and the destination and the topology facet obtained in step S3 again to obtain several polygons connecting the origin and the destination, and merge these polygons;

S5. Divide the polygons merged in step S4 into different paths according to the origin and destination, and select the shorter path, which is the obtained first initial path.

As an optional improved technical solution: step S3 also includes: as long as the path is within the circle or intersects with the circle, all are screened out for topology faceting.

As an optional improved technical solution: it also includes step S6, taking the length of the first initial path as the benchmark, constructing a second circle with the center of the line connecting the origin and the destination as the center of the circle, and filtering out the path within the range of the second circle. Perform topology profiling, obtain a second initial path, compare the second initial path with the first initial path, and check the accuracy of the first initial path.

As an optional improved technical solution: step S6 also includes the following steps:

S61, taking the connecting line between the starting point and the ending point, that is, the length of the first initial path as the diameter, and taking the center of the connecting line between the starting point and the ending point as the circle point to construct a second circle;

S62, find out all the paths in the second circle, and perform topological facets on these paths;

S63, filter through the topological facet obtained in step S62 by connecting the starting point and the ending point again to obtain several polygons connecting the starting point and the ending point, and merge these polygons;

S64, the polygon merged in step S63 is divided into different paths according to the starting point and the ending point, and the shorter path is selected, which is the second initial path obtained;

S65. Compare the second initial path with the first initial path to check the accuracy of the first initial path.

As an optional improved technical solution: Step E2 further includes: as long as the path is within the circle or intersects with the second circle, all are screened out for topology faceting.

In particular, the reason for the construction process of the circle in the described step B is analyzed as follows:

In step S2, by constructing a first circle whose diameter is the length of the line connecting the origin and the destination, the problem is extended from a one-dimensional space of distance length to a two-dimensional space, and the space of possible solutions is constrained by the range concept of the two-dimensional space. , and then obtain the initial solution, that is, the first initial path.

The realization function of step S3 is:

The solution space of the problem is expanded to the field of two-dimensional surfaces through facets, and the purpose of merging polygons is to quickly find the surface that can contain the origin and destination, and then find possible solutions to the problem, and also optimize the loop for subsequent computers. Provide theoretical explanations and initial values.

Steps S4 and S5 implement functions as follows:

Using the concept that a two-dimensional surface is a closed line, the origin, destination, surface, and line are combined by merging polygons, and the initial solution is found through the closed line, which provides convenience for the subsequent compression of the solution space and the solution of the true value.

The realization function of step S6 is:

The initial solution obtained through step S5 is an approximate solution, and the length of the true value must be within the range of the line connecting the two points and the approximate solution. The range circle is constructed again through the approximate solution. From the geometric analysis, it can be known that the range circle must contain the true value, and then the true value is constrained again to ensure the effective, fast and accurate solution of the true solution.

In the invention, the shortest path solution in traditional computer graphics and logic is unified into the category of geographic space, and the paths involved in the solution are limited to a small range through geometry, space science and other related technologies. The range is linearly related to the line connecting the target points and has nothing to do with the number of global samples, so it also solves the sample space optimization problem of the Dijkstra algorithm. With the help of dimension-raising and dimensional-reduction thinking, the length problem is a one-dimensional logic problem, and the space analysis technology is the logic judgment technology of the two-dimensional space object. Therefore, using the space analysis technology, the overall problem solution is transformed into a local problem solution and then the final solution is obtained. It also solves the problem that other algorithms, such as biological algorithms and intelligent algorithms, can only obtain local optimal solutions, but it is difficult to solve the overall optimal solution.

The shortest path is a one-dimensional problem in a two-dimensional environment, so its solution complexity is not less than the quadratic of the number of samples. For a one-dimensional problem in a two-dimensional environment, there must be a one-dimensional and two-dimensional association, and this association is the implicit topological relationship of objects in a two-dimensional environment. The present invention constructs a range circle, and its essence is the process of expanding the solution space of distance from one-dimensional to two-dimensional constrained. The two-dimensional problem is one-dimensional, and then the one-dimensional problem solution is quickly solved.

The invention will make up for the difficult problem of the traditional A* algorithm evaluation function selection, and solve the problem that the ant colony algorithm, the genetic algorithm, the neural network algorithm can only solve the approximate solution and cannot complete the mathematical optimal solution. Compared with the patent ZL201510790636.5, the present invention is the preposition of the patent, which is to transform the global two-dimensionalization process in the two-dimensionalization process of one-dimensional problems into a local two-dimensionalization process. The topology facet saves a lot of storage space and computing resources, and provides technical support for the realization of real-time shortest path analysis.

Description of drawings

FIG. 1 is a flow chart of the present invention.

FIG. 2 is a schematic diagram of the original route in the embodiment.

FIG. 3 is a schematic diagram of constructing a filter range circle by direct connection in an embodiment.

FIG. 4 is a schematic diagram of all path facets obtained by filtering in the embodiment.

FIG. 5 is a schematic diagram of connecting starting point polygons by line filtering in an embodiment.

FIG. 6 is a vectorized diagram after the polygons after the facets are found in the embodiment are merged and imported into the space coordinate system.

FIG. 7 is a schematic diagram of a circle constructed with the start and end points as the circle focus and the initial solution length as the benchmark in the embodiment.

FIG. 8 is a schematic diagram of a road area of the circular range gland of FIG. 5 in an embodiment.

FIG. 9 is a schematic diagram of the optimal solution in the embodiment.

10 to 12 are schematic diagrams of constraining the search range by ellipses.

FIG. 13 is a schematic diagram of constraining the search range by a circle.

Detailed ways

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention.

Example 1

Referring to Fig. 1, the shortest path solution method of the present embodiment, its operating platform is the Windows 7 operating system on the PC, and the geographic information system platform is Beijing SuperMap geographic information platform software 5.3.3 version, comprising the following steps:

S1. Naturalize the road network into a vector geographic space to obtain the origin and destination, as shown in Figure 2.

S2. Taking the center of the line connecting the origin and the destination as a dot, and taking the length of the line connecting the origin and the destination as the diameter, construct a first circle including the origin and destination; as shown in Figure 3.

S3. Find all the paths in the first circle, and perform topological facets on these paths, as shown in Figure 4; as long as the paths are within the circle or intersect with the first circle, they are screened out for topological facets.

S4, filter through the connection line between the origin and the destination and the topology facet obtained in step S3 again to obtain several polygons connecting the origin and the destination, and merge these polygons, as shown in Figure 5;

S5. Divide the polygons merged in step S4 into different paths according to the origin and destination, and select the shorter path, which is the obtained first initial path, as shown in FIG. 6 . Since the polygon is a closed line, two points on any polygon can be connected by two paths, and the shorter one is the initial value.

The shortest path selected above can be obtained by using the prior art to complete the final shortest path.

Through the solution of this embodiment, a better path can be solved quickly. The whole process includes first vectorizing the geographic space, taking advantage of the easy construction of a circle, and taking advantage of the advantages of a two-dimensional plane of a circle to filter out one-dimensional The one-dimensional path is then topologically faceted and dimensioned to form a two-dimensional closed path block, and then the one-dimensional connection between the origin and destination is used to overlap and filter the two-dimensional closed path block. It can find the shortest path and realize the solution of the initial path; such a solution process does not depend on the update and change of the map, and only needs to filter out the path; and the process of screening the path is also more convenient, which improves the efficiency of the solution.

Embodiment 2

This embodiment is a preferred solution of Embodiment 1; the solution provided in Embodiment 1 is a necessary technical solution, and this embodiment is a preferred solution to provide a sufficient technical solution on the basis of the necessary technical solution.

S61. In the first embodiment, the starting point and the ending point of the first initial path have been obtained by solving, and the line connecting the starting point and the ending point is the diameter, and the center of the connecting line between the starting point and the ending point is the circle point, and a second circle is constructed, as shown in the figure 7.

S62, find out all the paths in the second circle, and perform topological faceting on these paths, as shown in Figure 7; as long as the paths are within the circle or intersect with the second circle, they are all screened out for topological faceting.

S63, filter through the topological facet obtained in step S62 by connecting the starting point and the ending point again to obtain several polygons connecting the starting point and the ending point, and merge these polygons, as shown in Figure 8;

S64. Divide the polygons merged in step S63 into different paths according to the starting point and the ending point, and select the shorter path, which is the obtained second initial path. Since the polygon is a closed line, two points on any polygon can be connected by two paths, and the shorter one is the initial value.

S65. Compare the second initial path with the first initial path to check the accuracy of the first initial path.

The result obtained in the first embodiment can be verified by recalculation in this embodiment, and it can be confirmed that the calculation result of the first embodiment is correct, so this embodiment is a sufficient verification process.

When performing the calculation in this embodiment, the calculation is performed using the starting point and the end point obtained by the calculation in the first embodiment. Therefore, the second circle formed may be larger than the first circle, or may be smaller than the first circle, no matter what the case is, it is A full verification for Example 1.

At the same time, there will be a certain overlapping path between the second circle and the first circle, so the calculation result of the first circle can be stored and used when the second circle is calculated.

In the calculation of the shortest path in the first and second embodiments, the existing technology can be used to complete the final shortest path acquisition, as shown in FIG. 8, the dotted line in FIG. 8 is the straight path between the origin and the destination, and the thick solid line is the shortest path calculated. The existing technology used may be the patent number ZL201510790636.5, which is of course not limited to this technical solution, as long as the technology for obtaining the shortest path can be completed.

Referring to FIG. 9 to FIG. 13 , directly according to the first initial path length, the search range may be constrained by an ellipse, or may be constrained by a peripheral circle of the ellipse, where the circle includes the ellipse range. The present invention adopts circle to constrain, and the main reasons are as follows:

1. The model is simple: it only needs to correlate the initial path length with the starting point and the end point, and the center of the circle is the center of the line connecting the starting point and the ending point, and the radius is half of the initial path length, which satisfies the goal constrained by distance and starting point;

2. Easy to solve mathematically: ellipse not only needs to solve the major and minor axes and focus, but also when converting between coordinate systems, especially when rotating, the solution is more complicated, while the circle only needs to drop the center of the circle, and there is no influence of graphic rotation. .

3. Accurate search: The original and simplest graphics can be converted non-destructively on any platform, while for ellipses, precision loss will inevitably occur when converting between different platforms, as shown in Figure 9 below.

It has a great impact on the accuracy of spatial search, and it is easy to miss the possibility of retrieval. As shown in Figure 11-Figure 12 below, the line on the left will be missed when searching on a new platform. For the method of establishing an ellipse to find the shortest path, please refer to the Chinese invention patent application with the application number CN201910314226.1.

Referring to Figure 12, AOB is the diameter, O is the center of the circle, and the diameter-length multi-dimensional initial path:

AB<CA+CB

CA<AO+CO

CB<BO+CO

AO+CO<AO+CO=L1

BO+CO<EO+CO=L1

So CA+CB<2*L1

According to the properties of the circle, CA+CB=CA+AF>L1;

That is to say, the distance from any point on the circle to the starting and ending points is not more than twice the initial distance 2*L1 and not less than L1, that is, the distance from any point on the circle to the starting and ending points is [L1, 2*L1), and the solution space The lower limit of is L1, that is to say, the distance outside the circle must exceed this value, which means that the optimal solution must be within the range of the circle. Through the initial solution and the circle, the original solution space is reduced from [L0, +∞) to [L0, 2*L1), including the interval [L0, L1], that is, the connection between the two points and the initial value. In the later stage, the path solution only needs to be carried out in this range, and the optimal solution must be included.

The parts that are not described in detail in the present invention are known techniques of those skilled in the art.

The preferred embodiments of the present invention have been described in detail above. It should be understood that those skilled in the art can make many modifications and changes according to the concept of the present invention without creative efforts. Therefore, all technical solutions that can be obtained by those skilled in the art through logical analysis, reasoning or limited experiments on the basis of the prior art according to the concept of the present invention shall fall within the protection scope determined by the claims.

Claims (5)

1. The shortest path solving method based on the space normalization is characterized by comprising the following steps of:

s1, the road network is normalized to a vector geographic space, and a starting place and a destination are obtained;

s2, constructing a first circle containing the starting place and the destination by taking the center of a connecting line of the starting place and the destination as a circular point and taking the length of the connecting line of the starting place and the destination as a diameter;

s3, finding out all paths in the first circle, and carrying out topological construction on the paths;

s4, filtering the topological structural surface obtained in the step S3 again through connecting the starting place and the destination, obtaining a plurality of polygons connecting the starting place and the destination, and merging the polygons;

and S5, dividing the combined polygon in the step S4 into different paths according to the starting place and the destination, and selecting the path with the shorter path, namely the first initial path.

2. The shortest path solving method according to claim 1, wherein the step S3 further includes: if the path is in the circle or has a cross with the circle, the topological structure surface is screened out.

3. The shortest path solving method according to claim 1 or 2, further comprising the steps of:

s6, taking the length of the first initial path as a diameter, constructing a second circle by taking the connecting line center of the starting place and the destination as the center of the circle, carrying out topology construction on the path filtered in the range of the second circle, obtaining a second initial path, comparing the second initial path with the first initial path, and checking the accuracy of the first initial path.

4. The shortest path solving method according to claim 3, wherein the step S6 further comprises the steps of:

s61, constructing a second circle by taking the connecting line of the starting point and the end point, namely the first initial path length, as a diameter and taking the center of the connecting line of the starting point and the end point as a circular point;

s62, finding out all paths in the second circle, and carrying out topological construction on the paths;

s63, filtering the topological structural surface obtained in the step S62 through the connecting line of the starting point and the end point again to obtain a plurality of polygons connecting the starting point and the end point, and merging the polygons;

s64, dividing the combined polygon in the step S63 into different paths according to the starting point and the end point, and selecting the path with the shorter path, namely the second initial path;

and S65, comparing the second initial path with the first initial path to check the accuracy of the first initial path.

5. The shortest path solving method according to claim 4, wherein the step S62 further comprises: if the path is in the circle or crossed with the second circle, the topological structure surface is screened out.

Images