A* Algorithm in Artificial Intelligence
Basic Principle of A* Algorithm:
Sum the cost and the evaluation function values for a state to get its “goodness” worth and use this as a yardstick instead of the evaluation function value in best-first search. The sum of the evaluation function value and the cost along the path leading to that state is called a fitness number.
A fitness number f'(n) is a heuristic function that estimates the merits of each node that we generate. So, this algorithm can search for more promising paths first. Dash (‘) in the function indicates that it is an approximation to a function f(n) that gives the actual or true evaluation of the node. It is given as follows:
where f'(n) – It is estimated cost of the cheapest solution through n.
h'(n) – It is an estimate of the additional cost of getting from the current node to a goal node.
g'(n) – It is an estimate of getting from the initial node to the current node.
A* Algorithm is given as follow:
1. Put the initial node in a list OPEN.
2. If (OPEN is empty) or (OPEN=GOAL) then terminate search
3. Removes the first node from OPEN. Call this node a.
4. If (a=GOAL) then terminate with SUCCESS.
5. Else if node a has successors, generate all of them. Estimate the fitness number of the successors by totalling the evaluation function value and the cost function value. Sort the list by fitness number.
6. Name the new list as CLOSED.
7. Replace OPEN with CLOSED.
8. Go to step 2.