The Depth first search and Breadth first search given earlier for OR trees or graphs can be easily adopted by AND$-$OR graph.

$$ The main difference lies in the way termination conditions are determined, since all goals following an AND nodes must be realized; whereas a single goal node following an OR node will do$.$

$$ So for this purpose we are using AO$*$ algorithm.

$$ Like A$*$ algorithm here we will use two arrays and one heuristic function.

$$ OPEN:

$$ It contains the nodes that has been traversed but yet not been marked solvable or unsolvable.

$$ CLOSE:

$$ It contains the nodes that have already been processed.

An algorithm to find a solution in an AND $-$ OR graph must handle AND area appropriately

$$ A$*$ algorithm can not search AND $-$ OR graphs efficiently

$$ the top node A has been expanded producing two area one leading to B and leading to C$-$D $.$

$$ the numbers at each node represent the value of f $\text{'}$ at that node $($cost of getting to the goal state from current state$).$

$$ For simplicity, it is assumed that every operation$($i$.$e$.$ applying a rule$)$ has unit cost, i$.$e$.,$ each are with single successor will have a cost of $1$ and each of its components.

$$ With the available information till now $,$ it appears that C is the most promising node to expand since its f $\text{'}=3,$ the lowest but going through B would be better since to use C we must also use D$\text{'}$ and the cost would be $9(3+4+1+1).$ Through B it would be $6(5+1)$

$.$ Thus the choice of the next node to expand depends not only n a value but also on whether that node is part of the current best path form the initial mode

$$ the node G appears to be the most promising node, with the least f $\text{'}$ value. But G is not on the current best path, since to use G we must use GH with a cost of $9$ and again this demands that arcs be used $($with a cost of $27).$

$$ The path from A through B$,$ E$-$F is better with a total cost of $(17+1=18).$ Thus we can see that to search an AND$-$OR graph, the following three things must be done

$1.$ traverse the graph starting at the initial node and following the current best path, accumulate the set of nodes that are on the path and have not yet been expanded

$.2.$ Pick one of these unexpanded nodes and expand it$.$ Add its successors to the graph and compute f $\text{'}($cost of the remaining distance$)$ for each of them

$3.$ Change the f $\text{'}$ estimate of the newly expanded node to reflect the new information produced by its successors. Propagate this change backward through the graph. Decide which of the current best path.