Minimizing the total estimated solution cost

The most widely known form of best-first search is called A∗A search (pronounced “A-star ∗SEARCH

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 algorithm is identical to UNIFORM-COST-SEARCH except

that A∗uses g + h instead of g.

Implementation:

A* does also use both OPEN and CLOSED LIST.

Algorithm:

1. Initialize the open list

2. Initilalize the closed list

   Put the starting node on the open

   list(you can leave it’s f at zero)

3. while the open list is not empty

a) find the node with the least f on the open list, call it “q”

b) pop q off the open list

c) generate q's 8 successors and set their parents to q

d) for each successor

i) if successor is the goal, stop search

successor.g = q.g + distance between

Successor and q

successor.h = distance from goal to

successor(This can be done using many

ways,we will discuss three heuristics- Manhattan, Euclidean and Diagonal Heuristics)

successor.f = successor.g + successor.h

ii) if a node with the same position as

successor is in the OPEN list which has a lower f than successor, skip this successor

iii) if a node with the same position as successor is in the CLOSED list which has lower f than successor, skip this successor otherwise, add the node to the open list end(for loop) e) push q on the closed list end.(while loop).

Properties:

Conditions for optimality: Admissibility and consistency

The first condition we require for optimality is that hbe an admissible heuristic. An HEURISTIC admissible heuristic is one that never overestimates the cost to reach the goal. Because g(n) is the actual cost to reach n along the current path, and f(n)=g(n) + h(n), we have as an immediate consequence that f(n) never overestimates the true cost of a solution along the current path through n.