Greedy Best-First search tries to expand the node that is closest to the goal assuming it will lead to a solution quickly
- f(n) = h(n)
- "Greedy Search"
Greedy best first search to refer specifically to search with heuristic that attempts to predict how close the end of a path is to a solution, so that paths which are judged to be closer to a solution are extended first. This specific type of search is called greedy best-first search.
Implementation
- expand the "most desirable" node into the fringe queue
- sort the queue in decreasing order of desirability
Example: consider the straight-line distance heuristic h
- Expand the node that appears to be closest to the goal
hSLD (In(Arid)) = 366
Notice that the values of hSLD cannot be computed from the problem itself
It takes some experience to know that hSLD is correlated with actual road distances
- Therefore a useful heuristic
Complete
- No, GBFS can get stuck in loops (e.g. bouncing back and forth between cities)
Time
- O(bm) but a good heuristic can have dramatic improvement
Space
- O(bm)- keeps all the nodes in memory
Optimal
- No!
- f(n) = h(n)
- "Greedy Search"
Greedy best first search to refer specifically to search with heuristic that attempts to predict how close the end of a path is to a solution, so that paths which are judged to be closer to a solution are extended first. This specific type of search is called greedy best-first search.
Implementation
- expand the "most desirable" node into the fringe queue
- sort the queue in decreasing order of desirability
Example: consider the straight-line distance heuristic h
- Expand the node that appears to be closest to the goal
hSLD (In(Arid)) = 366
Notice that the values of hSLD cannot be computed from the problem itself
It takes some experience to know that hSLD is correlated with actual road distances
- Therefore a useful heuristic
Complete
- No, GBFS can get stuck in loops (e.g. bouncing back and forth between cities)
Time
- O(bm) but a good heuristic can have dramatic improvement
Space
- O(bm)- keeps all the nodes in memory
Optimal
- No!
No comments:
Post a Comment