Let me show you a document:
Research on Map Shortest Path Search Algorithm
Student: Li Tutor: Dong Luan
Abstract: Up to now, a large number of experts and scholars at home and abroad have conducted in-depth research on the "shortest path problem". Through theoretical analysis and practical application, this paper systematically compares the advantages and disadvantages of breadth-first search algorithm (BFS), depth-first search algorithm (DFS) and A* algorithm from all aspects.
Keywords: shortest path algorithm; Breadth first search; Depth first algorithm; A* algorithm;
Map shortest path search algorithm
Abstract: Up to now, a large number of experts and scholars at home and abroad have conducted in-depth research on the "shortest path problem". Through theoretical analysis and practical application, this paper studies breadth-first search algorithm (BFS), depth-first search algorithm (DFS) and A * algorithm from any aspect of the system.
Keywords: shortest path algorithm; Breadth-first-search; Algorithm; A * algorithm;
Foreword:
The shortest path problem is one of the important contents in network analysis of geographic information system (GIS), and it is also of great significance in graph theory. Many problems in real life are related to the "shortest path problem", such as network routing, integrated circuit design, wiring problems, electronic navigation, transportation and tourism. In this paper, depth-first algorithm, breadth-first search algorithm and A* algorithm are used to discuss and analyze a specific problem, and the advantages and disadvantages of the three algorithms are compared.
In the study of the shortest path search algorithm for maps, the comparison principles of advantages and disadvantages of various algorithms mainly follow the following three points: [1]
Completeness of (1) algorithm: Put forward a question, which has an answer, and the algorithm can guarantee to find the corresponding answer. The completeness of the algorithm is one of the excellent indexes of the algorithm performance.
(2) Time complexity of the algorithm: Ask a question, how long does it take the algorithm to find the corresponding answer. The speed of the algorithm is an important embodiment of the advantages and disadvantages of the algorithm.
(3) Spatial complexity of the algorithm: How much storage space does the algorithm need when searching for answers to questions? The less resources the algorithm occupies, the better the performance of the algorithm.
Searching algorithm of shortest path in map;
1, breadth-first search
Breadth-first search, also known as width-first search or lateral-first search, is one of the simplest graph search algorithms, and it is also the prototype of many important graph algorithms. Dijkstra's single-source shortest path algorithm and Prim's minimum spanning tree algorithm both adopt the idea of width-first search. The alias of width-first-search is BFS, which belongs to a blind search method and aims to systematically expand and check all nodes in the graph to find the results. In other words, it searches the whole graph thoroughly, regardless of the possible address of the result, until it finds the result. BFS does not use the rule of thumb algorithm.
Pseudo-code of breadth-first search algorithm is as follows: [2-3]
BFS(v)// breadth first search g, starting from vertex v.
//All searched vertices I are marked as visited (i)= 1.
The initial component values of //Visited// are all 0.
Visited (v) =1;
q =[]； //Initialize Q as a queue with only one element v..
When q is not empty
u = del head(Q)；
For is adjacent to all vertices w do of u.
If (w)=0 has been visited, then
AddQ(w，Q)； //put w at the end of the queue Q.
Visited (w) =1;
endif
end
end time
End BFS
Two functions are called here: AddQ(w, q) puts w at the end of the queue q; DelHead(Q) takes the first vertex from the queue Q and deletes it from Q. Repeat the DelHead(Q) process until the queue q is empty.
Completeness: breadth-first search algorithm is complete. This means that no matter what kind of graphics, as long as the target exists, BFS will definitely find it. However, if the target does not exist and the graph is infinite, the BFS will not converge (will not end).
Time complexity: In the worst case, BFS must find all paths to possible nodes, so its time complexity is, where |V| is the number of nodes in the graph and |E| is the number of edges in the graph.
Spatial complexity: Because all nodes must be stored, the spatial complexity of BFS is, where |V| is the number of nodes in the graph and |E| is the number of edges in the graph. Another way of saying this is that the spatial complexity of BFS is O(B), where b is the maximum branching coefficient of the tree and m is the longest path length of the tree. Due to the huge demand for space, BFS is not suitable for solving very big problems. [4-5]
2. Depth first algorithm
Depth first search, abbreviated as DFS in English, belongs to backtracking algorithm. Just like the name of the algorithm, the search strategy followed by depth-first search is to search the graph as deeply as possible. [6] In short, the process is to search along the neighboring points of the vertex until there are no visited neighboring points of the currently searched vertex. At this point, the original path of the previously searched vertex returns to the previously searched visited vertex, and this vertex is regarded as the currently searched vertex. Continue this process until it can't be executed.
The pseudo code of the depth-first search algorithm is as follows: [7]
DFS(v) // Access all vertices reached by v..
Visited (v) =1;
For is adjacent to each vertex w do of v.
If (w)=0 has been visited, then
DFS(w)；
endif
end
End DFS
As a search algorithm, DFS plays an important role in finding solutions to NP (including NPC) problems. However, the time complexity of the search algorithm is O(n! ), its efficiency is relatively low, when the data scale becomes larger, this algorithm becomes inadequate. [8] There are many solutions to the efficiency problem of depth-first search. The most common is pruning, which means removing useless search branches. Feasible pruning and optimal pruning.
BFS: It is particularly effective for solving the shortest or least problem, and the search depth is small, but the disadvantage is that the memory consumption is large (a large number of array cells need to be opened to store the state).
DFS: It is effective for solving all traversal and searching problems, and it is fast when the depth of problem search is small and inefficient when the depth is large.
3.A* algorithm
1968, "P.E. Hart, N.J. Nelson and B. Raphael. Heuristic determination of formal basis of minimum cost path in graph. IEEE Trans。 System. Sci。 And cybernetics, SSC-4(2): 100- 107, 1968 .[9] Since then, an ingenious and efficient algorithm, A * algorithm, has come out and been widely used in related fields. A* algorithm actually introduces an evaluation function on the basis of width-first search. Instead of expanding all expandable nodes at once, it uses evaluation function to evaluate all unexpanded nodes, so as to find out the most expandable nodes and expand them until the target node is found.
The pseudo code of the main search process of A* algorithm is as follows: [10]
Create two tables, the open table saves all the nodes that have been generated but have not been investigated, and the closed table records the nodes that have been visited.
Calculating the estimated value of the starting point;
Put the starting point in the open table;
And (open! =NULL) // Take the node n with the smallest estimated value f from the open table;
If(n node = = target node) break
endif
For (each child node x of the current node n)
Calculate the estimated value of x;
If (x is on)
If (the estimated value of x is less than the estimated value of open table)
Set n as the father of x;
Update the estimated value in the open table; //Take the estimated value of the minimum path;
endif
endif
If (x is included)
If (the estimated value of x is less than the estimated value of the CLOSE table)
Set n as the father of x;
Update the estimated value in the settlement table;
Put the X node into OPEN // to get the estimated value of the minimum path.
endif
endif
If (x is not in the path)
Set n as the father of x;
Find the estimated value of x;
And insert x into the open table; //Not sorted yet
endif
finish up with
Insert n nodes in the closing table;
Sorting the nodes in the open table according to the estimated value; //In fact, it is to compare the size of node F in the open table, and proceed downward from the node with the shortest path.
End while (open! = empty)
Save the path, that is, from the end point, each node moves along the parent node until the start point, which is your path;
A * algorithm analysis:
Both DFS and BFS belong to blind search when expanding child nodes, that is, they will not choose which node is better in the next search, but jump to that node for the next search. In the case of bad luck, we need to explore the whole solution set space. Obviously, it can only be used to search small-scale problems. The biggest difference between A* algorithm and DFS, BFS and other blind search is that when the current search node selects the next node, it can select the node with the least cost as the next search node and jump on it. [11] A * algorithm uses the understanding of the problem and the understanding of the problem solving process to seek some heuristic information that is beneficial to the problem solving, so as to use these heuristic information to search for the optimal path. It does not need to traverse the whole map, but searches in a certain direction according to heuristic function at each step. When the map is large and complex, its computational complexity is much better than D ijks tr a algorithm. This is a very fast and efficient algorithm. However, the corresponding A* algorithm also has its shortcomings. Heuristic information is artificially added, which is subjective and directly depends on the experience of operators. Different situations use different heuristic information and heuristic functions, so it is difficult to choose them, and to a great extent, the optimal path cannot be found.
Summary:
This paper describes some steps of the shortest path algorithm, summarizes some advantages and disadvantages of each algorithm, and some relationships between algorithms. For BFS or DFS, although it is easy to use, it can only solve small-scale problems due to the limitation of time and space. BFS should be used for the shortest or least problems, while DFS should be used when traversing and solving all problems. As for the A* algorithm, it is a heuristic search algorithm and an optimal priority algorithm. It is suitable for small-scale, large-scale and super-large-scale problems, but the heuristic search algorithm is subjective, and its quality depends on the programmer's experience and the heuristic function chosen, so it is relatively difficult to write an excellent program with A* algorithm. Each algorithm has its own advantages and disadvantages. Choosing a reasonable algorithm for different problems is the best method.
References:
[1] Chen, Teng, Chen Qinghua. Case Analysis of Four Shortest Path Algorithms [J]. Computer Knowledge and Technology (Academic Exchange), 2007 (16):1030-1032
Yin, Yin. The shortest path algorithm of graph and its application in network [J]. Software Guide, 201(07): 51-53.
Liu Wenhai, Xu Rongcong. Algorithms and comparison of several shortest paths [J]. Fujian Computer, 2008(02):9- 12.
Deng Chunyan. Comparison of two shortest path algorithms [J]. Computer Knowledge and Technology, 2008 (12): 511-513.
Wang Sunan, Wei Songren, Jiang Wensheng people. Comparison of shortest path algorithms [J]. Systems Engineering and Electronics, 1994 (05): 43-49.
Xu and Li Tianzhi. Algorithms for finding all shortest paths [J]. Computer Engineering and Science, 2006 (12): 83-84
Li, Liu Runtao. A shortest path algorithm based on Dijkstra [J]. Journal of harbin university of science and technology, 2008 (03): 35-37.
Xu Dao. A New Algorithm for Finding the Shortest Path [J]. Computer Engineering and Science, 2006(02).
[9] Yan Chunshen. An Improved Police Patrol Program Based on Graph Depth Priority Algorithm and Dijkstra Algorithm [J].20 10 International Conference on Electrical Engineering and Automatic Control, 20 10(3): 73-77
[10] Bussonya VC++ realizes the shortest path based on Dijkstra algorithm [J]. Science and Technology Information (Science Teaching and Research), 2008 (18): 36-37
Yang, Wang, Ma. Realization of an optimization algorithm for shortest path analysis [J]. Journal of Jilin University (Information Science Edition), 2002 (02): 70-74