Ans:- A* algorithm:-
A* uses a best-first search and finds the least-cost path from a given initial node to one goal node (out of one or more possible goals).
It uses a distance-plus-cost heuristic function (usually denoted f(x)) to determine the order in which the search visits nodes in the tree. The distance-plus-cost heuristic is a sum of two functions:
o the path-cost function, which is the cost from the starting node to the current node (usually denoted g(x))
o an admissible "heuristic estimate" of the distance to the goal (usually denoted h(x)).
o The h(x) part of the f(x) function must be an admissible heuristic; that is, it must not overestimate the distance to the goal.
o Thus, for an application like routing, h(x) might represent the straight-line distance to the goal, since that is physically the smallest possible distance between any two points or nodes.
o If the heuristic h satisfies the additional condition for every edge x, y of the graph (where d denotes the length of that edge), then h is called monotone, or consistent.
o In such a case, A* can be implemented more efficiently—roughly speaking, no node needs to be processed more than once (see closed set below)—and A* is equivalent to running Dijkstra's algorithm with the reduced cost d'(x,y): = d(x,y) − h(x) + h(y).
AO* algorithm:-
Initialize the graph to start node.
Traverse the graph following the current path accumulating nodes that have not yet been expanded or solved.
Pick any of these nodes and expand it and if it has no successors call this value FUTILITY otherwise calculate only f’ for each of the successors.
If f’ is 0 then mark the node as SOLVED.
Change the value of f’ for the newly created node to reflect its successors by back propagation.
Wherever possible use the most promising routes and if a node is marked as SOLVED then mark the parent node as SOLVED.
If starting node is SOLVED or value greater than FUTILITY, stop, else repeat from 2.