Monday, September 14, 2015

A* algorithm VS Dikjastra algorithm

Both algorithm are efficient algorithm to find shortest path between start point and end point, the difference is the measurement of the next most possible node in the graph.
Dikjastra algorithm : measurement is distance from start node to current node
A* algorithm: measurement is distance from start node to current node + current node to the end node
A* algorithm and dikjastra are both heuristic searching algorithm, unlike DFS or BFS, which is blind searching algorithm. 
G: distance from start node to current node, we can know the exactly distance by traveling the node.
H: heuristic distance from current node to end node, we has to predict the distance.
F:  G + H

This is the biggest difference between these two algorithm. Thus, the implementation of these two algorithm would be a little bit different.
close list:  like the unordered_set in BFS, which marks the visited nodes.
open list: like the queue in BFS, which mark the current exploring node, but in these two algorithm, we use priority_queue to select the most possible node
For Dikjastra algorithm:
when exploring the neighbors, 3 cases could happend:
case1: neighbor is in close list.  we can skip that node
case2: neighbor is not in close list and not in open list, then we should caculate G , then push the node into open list
case3: neighbor is not in close list but in open list, this means we explore the same node twice, we get to the same node in two different path, in this case, the distance of two path may different. We have to compare the new G and the old G in open list, if new G < old G, we update the G value of the node in openlist
For A* algorithm:
 MOST THINGS ARE THE SAME
case1: neighbor is in close list.  we can skip that node
case2: neighbor is not in close list and not in open list, then we should caculate F = G+H , then push the node into open list
case3: neighbor is not in close list but in open list, this means we explore the same node twice, we get to the same node in two different path, in this case, the distance of two path may different. We have to compare the new G and the old G in open list, if new G < old G, we update the G value of the node in open list.( We don't need to take F value to be considered, because, F  = H+G, in this scenario, H is the same, we only need to compare G. )

 Ads & disads:

A* use heuristic function to optimize the search, but may not be more efficient than dijkstra, because it requires more operations on one single node, and you have to find a efficient heuristic function to get the distance.



No comments:

Post a Comment