Trending Technology Machine Learning, Artificial Intelligent, Block Chain, IoT, DevOps, Data Science

Recent Post

Codecademy Code Foundations

Search This Blog

Greedy Best-First Search

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!

No comments:

Post a Comment

Popular Articles