A* & AO*

A* algorithm:-

This is the base of many AI system and it has been used since it was developed in 1968 by 3 scientists. 

Name is:-  Peter Hart, Nils nilsson, Bertram Raphael

In a*, the * is written for optimality purpose. It's a combination of two best algorithms. it is Dijkstra's algorithm and Best FIrst Search.

It can be used to solve many kinds of problems. This algorithm finds the shortest path using heuristic function through a search space technique to the goal state.

The A* algorithm also finds the lowest-cost path between the start to the state(desired state), Where changing state from one state to another requires some cost this requires the heuristic function to evaluate the essential cost/path 

it's use formula for defining the shortest path:-

f(n) = g(n) +h(n)

Where,
   n:-   This defines the next node on the path 
g(n):- The actual cost path from the start state to the current state

h(n):- This defines the heuristic function that finds the cheapest path from n to the goal state.

f(n):- the actual cost path from the start state to the goal state.
'

For use, A* algorithm  we will use two array name is OPEN and CLOSE

OPEN:-
           it contains the nodes that has been generated but has not been yet examined.

CLOSE:-
             This contains the nodes that have been examined.


Algorithm:-

 STEP 1:- Place the starting node into OPEN and Find it's f(n) value.

STEP 2:- Remove the node From OPEN, having the smallest f(n) value. if it is a goal node then stop                        and return 

Success.

STEP 3:- Else Remove the node from OPEN, find all its successors.

STEP 4:- Find the f(n) value of all successors; place them into OPEN and place the removed node                      into

CLOSE

STEP 5:- Go to Step-2

STEP 6:- Exit, 


Advantages:

  •  it is the best one from other techniques. 
  •  it is  used to solve a very complex problem
  •  it is optimally efficient 
Disadvantages:
  • It has complexity problems.
  • The execution speed highly dependant on the heuristic algorithm  

AO* Algorithm:-

AO* Algorithm is a mostly or efficient method to use it in AI. AO* Algorithm basically works on two phases 
AND or OR

This problem can be divided into a set of subproblems,  and each subproblem can be solved separately.
these type to solve a problem called  AO*