**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

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 **