Dijkstra’s algorithm works by visiting vertices in the graph starting with the object’s starting point. It then repeatedly examines the closest not-yet-examined vertex, adding its vertices to the set of vertices to be examined. it expands outwards from the starting point until it reaches the goal. Dijkstra’s algorithm is guaranteed to find a shortest path from the starting point to the goal, as long as none of the edges have a negative cost. (I write “a shortest path” because there are often multiple equivalently-short paths.) In the following diagram, the pink square is the starting point, the blue square is the goal, and the teal areas show what areas Dijkstra’s algorithm scanned. The lightest teal areas are those farthest from the starting point, and thus form the “frontier” of exploration:
The Best-First-Search (BFS) algorithm works in a similar way, except that it has some estimate (called a heuristic) of how far from the goal any vertex is. Instead of selecting the vertex closest to the starting point, it selects the vertex closest to the goal. BFS is not guaranteed to find a shortest path. However, it runs much quicker than Dijkstra’s algorithm because it uses the heuristic function to guide its way towards the goal very quickly. For example, if the goal is to the south of the starting position, BFS will tend to focus on paths that lead southwards. In the following diagram, yellow represents those nodes with a high heuristic value (high cost to get to the goal) and black represents nodes with a low heuristic value (low cost to get to the goal). It shows that BFS can find paths very quickly compared to Dijkstra’s algoritm:
However, both of these examples illustrate the simplest case―when the map has no obstacles, and the shortest path really is a straight line. Let’s consider the concave obstacle as described in the previous section. Dijkstra’s algorithm works harder but is guaranteed to find a shortest path:
BFS on the other hand does less work but its path is clearly not as good:
The trouble is that BFS is greedy and tries to move towards the goal even if it’s not the right path. Since it only considers the cost to get to the goal and ignores the cost of the path so far, it keeps going even if the path it’s on has become really long.
Wouldn’t it be nice to combine the best of both? A* was developed in 1968 to combine heuristic approaches like BFS and formal approaches like Dijsktra’s algorithm. It’s a little unusual in that heuristic approaches like BFS usually give you an approximate way to solve problems without guaranteeing that you get the best answer. However, A* is built on top of the heuristic, and although the heuristic itself does not give you a guarantee, A* can guarantee a shortest path.
No comments:
Post a Comment