A* Search Algo

Suppose the graph (figure 5(a))is drawn showing interconnected cities. It is a two way graph. A person can move in any direction like from vertex 2 to vertex 4 or from vertex 4 to vertex 2. An edge tells distance between two connected cities. Different search algorithms use different strategies to find the path from the source node to the destination node

Figure 5(a)

A* Search

A* search algorithm is an informed search works on weighted graph. This search uses the sum of the heuristic function (i.e. estimated value to reach from a given node to goal node) and the actual distance to find the shortest distance from source node to destination node.

Suppose for above drawn graph (figure 5(a)) showing connected cities
Source node – 2
Destination node – 5

1. We need to add heuristic value to each node. Heuristic value is estimated value to reach from a given node to goal node. It should be less than or equal to actual distance.
Heuristic values added to each node for destination node 5 is shown below in figure 5(b).

Figure 5(b)

2. Source Node is Node 2. On pressing any key, it is highlighted with another round of red colour as shown in figure 5(c).

Figure 5(c)

3. The Child nodes or the connected nodes to Node 2 are Node 4 (heuristic value 3) and Node 3 (heuristic value 2). A* uses the sum of the heuristic value and actual distance from source node to explore next node.

Cost to reach Node 3 is 5 (actual distance) + 3 (heuristic value) = 8
Cost to reach Node 4 is 3 + 3 = 6

The cost to reach node 4 is less than the cost to reach node 3.So next explored node will be 4 as shown in figure 5(d).

Figure 5(d)

4. The connected nodes to Node 4 are Node2, Node 3 and Node 1. Same as Best first Search, it will also not consider visited nodes. So we left with Node 1 and Node 3.

Cost to reach node 1 is 6 (actual distance from source node) + 2 (heuristic value) = 8
Cost to reach node 3 is 7 (actual distance from source node) + 2 (heuristic value) = 9

It is clear that next node to explore is Node 1 as shown in figure 5(e).

Figure 5(e)

5. Node 1 has child nodes Node 4 and Node 5. Node 5 is having 0 heuristic value, which shows it is destination node. So it is next visited node as shown in figure 5(f).

Figure 5(f)

Hence Destination Node 5 is found. So search is complete.

NB: The system displays the path from destination node to source node. It first checks for the shortest path route and then displays nodes in reverse direction.