A* Search
• The most common informed search algorithm is A* search
(pronounced “A-star search”), a best-first search that uses the
evaluation function,
f(n) = g(n) +h(n)
where g(n) is the path cost from the initial state to node n, and
h(n) is the estimated cost of the cheapest path from n to a goal
state, so we have,
f(n) = estimated cost of the best path that continues from n to a goal.
A* search
A* search : Admissibility
The condition we require for optimality is that h(n) be an admissible heuristic.
An admissible heuristic is one that never overestimates the cost to reach the goal.
Admissible heuristics are by nature optimistic because they think the cost of solving the
problem is less than it actually is.
Straight-line distance is admissible because the shortest path between any two points is a
straight line, so the straight line cannot be an overestimate.
h(n) <= h*(n) ------------Underestimation
h(n) > h*(n) ------------Overestimation
A* search : Admissibility
A* search is complete.!!
• Whether A* is cost-optimal depends on certain properties of
the heuristic.
• A key property is admissibility an admissible heuristic is one
that never overestimates the cost to reach a goal. (An
admissible heuristic is therefore optimistic.)
• With an admissible heuristic, A* is cost-optimal.
• Suppose the optimal path has cost C*, but the algorithm
returns a path with cost C > C*. Then there must be some
node n which is on the optimal path and is unexpanded.
• The notation g*(n) denote the cost of the optimal path from the
start to n, and h*(n) denote the cost of the optimal path from n to
the nearest goal, we have:
• a suboptimal path must be wrong—it must be that A* returns only
cost-optimal paths.
• A heuristic h(n) is consistent if, for every node n and
every successor n’ of n generated by an action a, we
have:
• This is a form of the triangle inequality, which
stipulates that a side of a triangle cannot be longer
than the sum of the other two sides.
Search contours
• A useful way to visualize a search is to draw contours in the
state space, just like the contours in a topographic map.
• A problem with fewer restrictions on the actions is called
a relaxed problem.
• The state-space graph of the relaxed problem is a
supergraph of the original state space because the
removal of restrictions creates added edges in the graph.
• Hence, the cost of an optimal solution to a relaxed
problem is an admissible heuristic for the original
problem.
