A* Search Algorithm:-
A* (A-star) is a widely used search algorithm that combines the best features of
both Dijkstra's algorithm and heuristic search. It is commonly applied to solve
the path-finding problem in graphs or grids, where the goal is to find the
shortest path from a start node to a goal node.
The A* algorithm works by maintaining two main values for each node: the cost
to reach the node from the start node (known as g-value), and an estimate of the
cost from the node to the goal node (known as h-value). It uses a priority queue,
typically implemented as a min-heap, to prioritize the nodes for exploration
based on their f-value, which is the sum of the g-value and h-value.
The A* algorithm follows these steps:
a) Initialize the open list, closed list, and set the g-value of the start node to
0.
b) Calculate the h-value for each node in the graph or grid based on a
heuristic function. The heuristic function estimates the cost from
each node to the goal node. Common heuristic functions include
Euclidean distance, Manhattan distance, or any other admissible and
consistent heuristic.
c) Enqueue the start node to the open list with its f-value as the priority.
d) Repeat the following steps until the open list becomes empty or the goal
node is reached:
I. Dequeue the node with the lowest f-value from the open list.
This node becomes the current node.
II. If the current node is the goal node, the algorithm terminates,
and the path has been found.
III. Add the current node to the closed list to mark it as visited.
IV. Explore the neighboring nodes of the current node:
i. Calculate the tentative g-value for each neighbor by
adding the cost to reach the neighbor from the current
node to the g-value of the current node.
ii. If the neighbor is not in the closed list or its tentative g-
value is lower than its current g-value:
1) Update the g-value of the neighbor to the new lower
value.
2) Calculate the f-value of the neighbor by adding its g-
value and h-value.
3) If the neighbor is not in the open list, enqueue it with
its f-value as the priority.
4) If the neighbor is already in the open list, update its
priority if the new f- value is lower.
5) Set the parent of the neighbor to the current node.
e) If the open list becomes empty before reaching the goal node, there is no
path available.
f) Once the goal node is reached, reconstruct the path by following the
parent pointers from the goal node to the start node.
The A* algorithm is both complete (able to find a solution if one exists) and
optimal (guaranteed to find the shortest path) under certain conditions. The
heuristic used must be admissible, meaning it never overestimates the actual
cost to reach the goal node. Additionally, the heuristic must be consistent (or
monotonic), meaning the estimated cost from a node to its successor plus the
heuristic value of the successor is always less than or equal to the estimated
cost from the current node to the goal node.
Consider g(n) = Depth of Node and h(n) = No. of Misplaced tiles.
Example 2:-
The numbers written on edges represent the distance between the nodes.
The numbers written on nodes represents the heuristic value.
Find the most cost-effective path to reach from start state A to final state J using
A* Algorithm.
Step 1 :-
We start with node A.
Node B and Node F can be reached from node A.
A* Algorithm calculates
f(n) = g(n) + h(n)
f(B) = g(B) + h(B) = 6 + 8 = 14
f(F) = g(F) + h(F) = 3 + 6 = 9
Since f(F) < f(B), So it decides to go to node F.
Path : A ---- F
Step 2 :-
Node G and Node H can be reached from node F.
A* algorithm calculates
F(n) = g(n) + h(n)
F(g) = g(G) + h(G) = (3+1) + 5 = 9
F(h) = g(H) + g(H) = (3+7) + 3 = 13
Since f(G) < f(H), so it decides to go to node G.
Path : A ----- F ------- G
Step 3 :-
Node I can be reached from node G.
A* Algorithm calculates
f(n) = g(n) + h(n)
f(I) = g(I) + h(I)
= (3+1+3) + 1 = 8
So it decides to go to node I.
Path : A ----- F ----- G ------ I
Step 4 :-
Node E, Node H and Node J can be reached from node I.
A* Algorithm calculates
f(n) = g(n) + h(n)
f(E) = (3+1+3+5) + 3 = 15
f(H) = (3+1+3+2) + 3 = 12
f(J) = (3+1+3+3) + 0 = 10
Since f(J) is least, so it decides to go to node J.
Path : A ------ F ------ G ------- I ------- J