Transcript quick_review_heuristic

Review of heuristic searches
• Heuristic searches encode the notion of the
“merit” of a state into a heuristic function, h(n).
Euclidean distance as h(s)
Say we want to plan a path from Arad to Bucharest, and we know the straight line
distance from each city to our goal. This lets us plan our trip by picking cities at each
time point that minimize the distance to our goal (or maximize our heuristic).
Greedy best first search
In this case, greedy best first search does not find the optimal solution.
greedy best first search ignores the cost of getting to a city, so it can be tricked into
exploring nodes that cost a lot to get to but seem to be close to the goal.
The A* Algorithm
Remember that g(n) is the cost of getting TO a node and h(n) is the estimated cost FROM it
to the goal. f(n) is g(n) + h(n).
•
The Priority Queue (list of nodes to expand) starts off empty (we call this queue PQ).
•
The list of previously visited (state, f value, backpointer) triples starts of empty (we call
this list V).
•
Put the Start state (S) into PQ and V with priority f(S) =g(S) + h(S) (= h(S). Why?)
•
Attempt to POP the element with the lowest f value from PQ.
-- Case 1: PQ is empty. Then there is no solution!
-- Case 2: We popped the Goal. Then we are done!
-- Case 3: We expand the node and generate its children! For each successor node (which
we call n):
Define f(n) = g(n) + h(n).
If n is a NEW node we place it in PQ with priority f(n), OR
If n is ALREADY in PQ or if it was already expanded, and f(n) is a LOWER
value than what we produced previously, place n in PQ with priority f(n) and
update V accordingly.
Otherwise, IGNORE the node and move on.
A star will find a good solution only if the heuristic
function is ADMISSIBLE.
Do you remember what that means?
Admissible heuristics
Which heuristics are admissible for the 8 puzzle?
•
h(n) = number of misplaced tiles
•
h(n) = total Manhattan distance between tile locations in S and goal locations in
G
•
h(n) = min (2, h*[n])
•
h(n) = h*(n)
•
h(n) = max (2, h*[n])
•
h(n) = 0