Greedy Best-First Search [H]
- This algorithm tries to bite off as big a chunk of the solution as it can without worrying about the consequences.
- It expands the node that appears to be closest to the goal.
- The BestFS 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. BestFS 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.
- Performance Measure
- Complete: No, can get stuck in a loop (A >> B, B >> A, A >> B, ...)
- Can be made complete in a finite-space and repeat-state checking
- Time Complexity: O(bm)
- Space Complexity: O(bm) - Keeps all nodes in memory
- Optimality: No (or Yes if there are no obstacles)
- Complete: No, can get stuck in a loop (A >> B, B >> A, A >> B, ...)
Related ☣ Search
