(17teen-April-2020)
• A* search is a combination of lowest-cost-first and best-first searches that considers both path cost and heuristic information in its selection of which path to expand. For each path on the frontier, A* uses an estimate of the total path cost from a start node to a goal node constrained to start along that path. It uses cost(p), the cost of the path found, as well as the heuristic function h(p), the estimated path cost from the end of p to the goal.
• For any path p on the frontier, define f(p)=cost(p)+h(p). This is an estimate of the total path cost to follow path p then go to a goal node.
• If n is the node at the end of path p, this can be depicted as follows:
• actual estimate
• start ---------> n -----------> goal
• cost(p) h(p)
• ------------------------->
• f(p)
• If h(n) is an underestimate of the path costs from node n to a goal node, then f(p) is an underestimate of a path cost of going from a start node to a goal node via p.
• A* is implemented by treating the frontier as a priority queue ordered by f(p).
Comments