Implement A* Search algorithm.(Part-1)

Question

Implement A* Search algorithm.

Answer 1

A* Search Algorithm

1. As we know, Human is a wanderer.He uses many routes to get from one place to another.

2. 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.

3. Actually A* is a  part of informed search techniques(Algorithms) in Artificial Intelligence.
4. Before moving on Informed search algorithm let's understand search technique first.
5. 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.
6. Search Algorithm divided into two parts informed search and uninformed search or blind.
7. Here we are discussing Informed Search Algorithm.
8. 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. 
9. A* algorithm is a type of  Informed Search Algorithm.
10. 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.
11. 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

F(n) = G(n) + H(n)

A*  Algorithm use this formula to provide a optimal path

Here 

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