A* Search Algorithm
As we know, Human is a wanderer.He uses many routes to get from one place to another.
Since ancient times, humans used to apply a lot of calculation to choose a optimal path for destination. Like time, cost, long and short paths.
- Actually A* is a part of informed search techniques(Algorithms) in Artificial Intelligence.
- Before moving on Informed search algorithm let's understand search technique first.
- In the olden times it was very difficult to find the right path. today, we have algorithms that can help us find the shortest paths virtually. We just need to add costs (time, money etc.) to the graphs or maps and the algorithm finds us the path that we need to take to reach our destination as quick as possible.This is what a search algorithm do.
- Search Algorithm divided into two parts informed search and uninformed search or blind.
- Here we are discussing Informed Search Algorithm.
- Informed search algorithm contains an array of knowledge such as how far we are from the destination, path cost, how to reach to destination node, etc.
- A* algorithm is a type of Informed Search Algorithm.
- A* mostly known for its completeness, optimality, and optimal efficiency.Meaning it's sure that A* will find all route from source to destination , with least cost.
- Since It is A* is best and popular technique used in path-finding and graph traversals. It is used many computer games and web-map.
How A* is actually work
A* Algorithm use this formula to provide a optimal path
n-node (in current state)
F- Least cost from source (start node ) to the destination (goal node)
G-Actual cost from start node to n node.
H-Estimated cost from n node to the Goal node (heuristic value of node).
In the above diagram, we see two paths to go from source to Goal. From both, we should take the path of minimum cost.
H- Values shows in green color are heuristic/ estimated value of the nodes. (Generally heuristic value of the goal is zero.)
Note: The heuristic function is a way to inform the search about the direction to a goal. It provides an informed way to guess which neighbor of a node will lead to a goal.
G- values in maroon color shows actual cost between nodes.
Let's calculate formula and see the values
F(S)= 0 + 5 =5 , F(S-A) =3 +4 =7 and F(S-B) = 4+5 = 9
As we can see the path (S-A) is less costly than path (S-B)we will take it.
F(S-A-G) = 3+10+0 =13 and F(S-B-G) = 4 + 2 +0 = 6
From the given example we can say that our path will we F(S-B-G). In this way we find optimal path to destination.
For Practical implementation of Algorithm Click Here