A* algorithm
A* algorithm
In this every node has 2 functions:
1. g(n) -cost till the current node
2. h(n) -cost to go to goal node form current node
This was proposed by Hart in 1972. It is a combination of branch and bound, best search along with dynamic. It uses a heuristic ON evaluation function denoted by f(s) to determine the order in which the search precedes the nodes in the tree.
The heuristic function for a node is defined as-
- The function g(n) is a measure of getting started from current node to the node ‘n’.
- The function h(n) is an estimate of the cost of going from current node to goal node.
Problems related to A * algorithm:-
8 puzzle problem-
3 7 6 goal: 5 3 6
5 1 2 7 _ 2
4 _ 8 4 1 8
left: 3 7 6 Right: 3 7 6 top: 3 7 6
5 1 2 5 1 2 5 _ 2
_ 4 8 4 8 _ 4 1 8
The 8 puzzle problem has a 3×3 grid with 8 random tiles arranged on it with an empty cell. At any point the empty cell can be moved either top, down, left or right. So the operation can be thought of as the direction in which the blank space is moved.
Using A* algorithm ,
f(n)= g(n) + h(n)
A* algorithm finds optimal solution if the heuristic function is carefully designed as the value is underestimated.
Underestimation—- if we can generate h(n) which will never overestimate the actual value from current to goal, then A* algorithm ensures to find an optimal path if one exists.
Overestimation of h(n), may or may not find the shortest path.
Admissibility of A* algorithm:-
A* algorithm is only admissible if for any graph it always terminates in an optimal path from start to goal if one exists.
visit www.oureducation.in and blog.oureducation.in for more information.
Tell us Your Queries, Suggestions and Feedback