Prove that A* is admissible.

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.

F(n) never over estimates the true cost of solution through n.

Suppose a sub optimal goal node $G_2$ appears on the fringe, let the cost of the optimal solution be $C^*$ then because $G_2$ is sup optimal and because $h(G_2) = 0$, we know

$f(G_2) = g(h_2) + h(G_2) = g(G_2) \gt C^*$

Now consider a fringe node n i.e. on an optimal solution path – example P in the example. If h(n) does not over estimate the cost of completing the solution path, then we know that,

$f(n) = g(n) + h(n) \leq C^*$

Now, we have shown that.

$f(n) \leq c^* \lt f(G_2)$, so $G_2$ will not be expanded and A* must return an optimal solution.

$F[s] \leftarrow max(g(s) = h(s), f[node])$

repeat

best $\leftarrow$ the lowest f – value node in successors.

if f[best] > f – limit then return failure, f[best]

alternative $\leftarrow$ the second – lowest f-value among successors.

result, f[best] $\leftarrow$ RBFS (problem, best;

min (f-limit, alternative))

if result $\neq$ failure then return result.

Figure 4.5 The algo for RBFS.

RBFS is some what more efficient than IDA*, but still suffers from excessive mode regeneration.

Difference between A* and RBFS.

A* keeps in memory all of the already generated nodes.

RBFS only keeps the current search path and the sibling nodes along the path.

Like A* RBFS is an optimal algorithm. If the heuristic function h(n) is admissible. Its space complexity is O(bd). Bit its time complexity is rather difficult to characterize : it depends both on the accuracy of the heuristic function and on how often the best path changes as nodes are expanded.