Heuristic Search Methods Flashcards
What is the difference between an uninformed (blind) search and an informed (heuristic) search?
Uninformed - search algorithms only have the knowledge provided in the search problem. Chooses where to expand depending on path characteristics (depth and cost).
Informed - uses problem specific knowledge to pick which node to expand. Typically involves a heuristic function h(n) to estimate the cheapest path from n.STATE to a goal state.
Explain best-first search.
Use an evaluation function f to estimate the desirability of each node in the fringe (the smaller the value of f, the higher the desirability).
How does a greedy (best-first) search work?
Describe its properties in terms of completeness, time complexity, space complexity, and optimality.
f(n) = h(n): expand the node that appears to be closest to the goal, where f(n) is the estimate of cost from n to goal, e.g. straight line distance.
Completeness: no, susceptible to infinite loops
Time complexity: O(b^m)
Space complexity: O(b^m)
Optimality: no, not guaranteed to find shortest solution first
When discussing search algorithms, what do b, m, C, and h(n) mean?
b = branching factor
m = maximum tree depth
C* = cost of optimal solution
h*(n) = true cheapest cost from n to goal
How does the a-star (a*) search work?
Describe its properties in terms of completeness, time complexity, space complexity, and optimality.
Includes the cost of reaching a node. Evaluation function -> f(n) = g(n) + h(n), so expand the node that appears to be on the cheapest path to the goal.
g(n) = cost of reaching state n
h(n) = estimated cost of reaching goal from state n
f(n) = estimated cost of the cheapest path to a goal state that goes through the path of n
Completeness: yes, unless there are infinitely many loops with f(n) <= C*
Time complexity: exponential unless h is very accurate -
| h(n) - h(n) | <= O(log h(n))
Space complexity: keeps all nodes in memory
Optimality: yes, if h is admissible
What makes a heuristic h(n) admissible?
If for every node n, h(n) <= h(n), where h(n) is the minimum cost to reach the goal state from n.
Never overestimates the cost to reach the goal; it is optimistic (best case scenario).
