0
4.5kviews
Explain A* Search.
1 Answer
1
172views

Minimizing the total estimated solution cost. The most widely known form of best first search is called $A^*$ search. It evaluates nodes by combining g(n), the cost to reach the node, and h(n), the cost to get from the node to the goal:

F(n) = g(n) + h(n)

Since g(n) gives the path cost from the start node to node n, and h(n) is the estimated cost of the cheapest path from n to the goal, we have,

F(n) = Estimated cost of the cheapest solution through n.

Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of g(n) + h(n). It turns out that this strategy is more than just reasonable : Provided that the heuristic function h(n) satisfies certain conditions, $A^*$ search is both complete and optimal.

The optimality of $A^*$ is straight forward to analyze if it is used with TREE – SEARCH. In this case. $A^*$ is optimal if h(n) is an admissible.

Heuristic – i.e. provided that h(n) never over estimates the cost to reach the goal. Admissible heuristic are by nature optimistic, because they think the cost of solving the problem is less than it actually is since g(n) is the exact cost to reach n, we have as immediate consequences that f(n). never over estimates the tree cost of an obvious through n.

An obvious example of an admissible heuristic is the straight – line distance $h_{SLD}$ that we used in getting to Bucharest. Straight – line distance is admissible because the shortest path between any two points is a straight line, so the straight line cannot be an over estimate. In figure (3), we show the progress of an $A^*$ tree search for Bucharest. The values of g are computed from the step costs in figure (2) and the values of $h_{LSD}$are given in figure (1).

Notice in particular that Bucharest first appears on the fringe at step, but it is not selected for expansion because its 4 – cost (450) is higher than that of Pltesti (417).

Another way to say this is that there might be a solution through Pltesti whose cost is as low as 417, so the algorithm will not settle for a solution that costs 450. From this example, we can extract a general proof that $A^*$ using TREE – SEARCH is optimal if h(n) is admissible.

enter image description here

Please log in to add an answer.