Module – 3 (Solution)
1. Explain the A* search to minimize the total estimated cost.
The A* search algorithm is one of the most important algorithms used to find the optimal
(minimum-cost) path from a start node to a goal node. It minimizes the total estimated cost using a
combination of actual cost and estimated future cost.
A* guarantees the optimal solution if Heuristic is:
Admissible → Never overestimates actual cost
Consistent (Monotonic) → Follows triangle inequality
The lowest total estimated cost: f(n)=g(n)+h(n)
f(n) → Total estimated cost of a solution through node n
g(n) → Actual cost from start node to node n
h(n) → Heuristic estimate (approximate cost) from n to goal
A* always expands the node with the smallest f(n) value and A* balances two things:
1. Path already travelled (g(n))
o Keeps track of the exact cost so far
2. Estimated future cost (h(n))
o Predicts how far the goal is
Working of Algorithm:
1. Start from the initial node
2. Add it to the open list (nodes to explore)
3. Repeat:
o Select node with lowest f(n)
o Move it to closed list (already explored)
o Expand its neighbors
o For each neighbor:
Compute g(n), h(n), f(n)
Add/update in open list
4. Stop when goal node is reached
Advantages:
1. Finds shortest path efficiently
2. Reduces unnecessary exploration
3. Widely used in:
Pathfinding (maps, GPS)
Games (AI movement)
Robotics
2. Apply search algorithm to find the solution path from the start node (S) to the goal node
(G). The heuristic values (h) are provided with the nodes, and the travel costs (C) are
provided with the edges as shown in the figure.
Given:
Start node = S
Goal node = G
Heuristic values (h):
S=11.5, A=10.1, B=5.8, C=3.4, D=9.2, E=7.1, F=3.5, G=0
Edge costs:
S-A=3, S-D=4
A-B=4, A-D=5
B-C=4, B-E=5
D-E=2
E-F=4
F-G=3.5
A* Formula:
f(n) = g(n) + h(n)
Open List: Nodes to be explored
Closed List: Nodes already explored
Step 1: Start at node S
g(S)=0
f(S)=0+11.5=11.5
Choose node with lowest f(n) → A
----------------------------------------
Step 2: Expand A
Neighbors:
B: g(B)=3+4=7 → f(B)=7+5.8=12.8
D: g(D)=3+5=8 → f(D)=8+9.2=17.2
Choose node with lowest f (n)→ B
----------------------------------------
Step 3: Expand B
Neighbors:
C: g(C)=7+4=11 → f(n)=11+3.4=14.4
E: g(E)=7+5=12 → f(n)=12+7.1=19.1
Open list now:
D (13.2), C (14.4), E (19.1)
Choose → D
----------------------------------------
Step 4: Expand D
Neighbor:
E: g(E)=4+2=6 → f(n)=6+7.1=13.1 (better than previous E)
Update E
Choose → E
----------------------------------------
Step 5: Expand E
Neighbor:
F: g(F)=6+4=10 → f(n)=10+3.5=13.5
Choose → F
----------------------------------------
Step 6: Expand F
Neighbor:
G: g(G)=10+3.5=13.5 → f(n)=13.5+0=13.5
Choose → G (Goal reached)
----------------------------------------
Final Path:
S→D→E→F→G
Total Cost:
= 4 + 2 + 4 + 3.5
= 13.5
The optimal path using A* algorithm is: S → D → E → F → G with total cost = 13.5
3. Solve the following eight-tile puzzle using heuristic function approach and the tree diagram
considering the initial and final states as specified.
4. In the below graph, find the path from A to G. Using Greedy Best First search and A* search
algorithm. The values in the table represent heuristic values of reaching the goal node G pass
Greedy Best-First Search:
• Selects the node with the lowest heuristic value at each step.
• Doesn't consider the actual cost of the path traversed so far.
• May not find the optimal solution.
Solution
Step 1: Start at A
Current node: A
Neighbors:
o B (h=6)
o C (h=4)
Choose node with lowest h(n) → C
Step 2: Move to C
Current node: C
Neighbors:
o E (h=3)
Open list also contains: B (h=6)
Choose E (h=3) (smallest)
Step 3: Move to E
Current node: E
Neighbor:
o G (h=0)
Choose G (goal node)
Final Path: A → C → E → G
A Search:*
A* considers both the heuristic cost and the actual cost to reach a node. And uses the evaluation
function f(n) = g(n) + h(n)
where: g(n) is the actual cost from the start node to node n.
h(n) is the estimated cost from node n to the goal node.
Solution:
• Start at node A: Calculate f(n) for each neighbour:
f(B) = g(B) + h(B) = 0 + 6 = 6
f(C) = g(C) + h(C) = 4 + 3 = 7
Choose node B as it has the lowest f(n) value.
• From node B: Calculate f(n) for each neighbour:
f(D) = g(D) + h(D) = 3 + 2 = 5
Choose node D as it has the lowest f(n) value.
5. Apply the A* search to find the solution path from a to z. Heuristics are with nodes, and cost
is with edges. Write all steps as well as open and closed lists for full marks
Solution:
A* Search Solution from a to z, where the start node = a & goal node = z
A* Formula: f(n) = g(n) + h(n)
where
g(n) = path cost from start
h(n) = heuristic value
---------------------------------
Initialization
Open List: { a }
Closed List: { }
f(a) = g(a)+h(a)
f(a) = 0 + 14 = 14 (Choose a)
---------------------------------
Step 1: Expand a
Neighbors: b, c
f(b): g = 4 → f = 4 + 12 = 16
f(c): g = 3 → f = 3 + 11 = 14 (Choose c)
Open List: { c(14), b(16) }
Closed List: { a }
---------------------------------
Step 2: Expand c (lowest f = 14)
Neighbors: e, d
e: g = 3 + 10 = 13 → f = 13 + 4 = 17
d: g = 3 + 7 = 10 → f = 10 + 6 = 16 (Choose d)
Open List: { b(16), d(16), e(17) }
Closed List: { a, c }
------------------------------------------------------
Step 3: Expand b (tie → choose b)
Neighbors: f, e
f: g = 4 + 5 = 9 → f = 9 + 11 = 20
e: g = 16 + 4= 20
Open List: { d(16), e(17), f(20) }
Closed List: { a, c, b }
--------------------------------------------------------------------------------
Step 4: Expand d
Neighbor: e
e: g = 10 + 2 = 12 → f = 12 + 4 = 16 (Choose e)
Open List: { e(16), f(20) }
Closed List: { a, c, b, d }
---------------------------------------------------------------------------------
Step 5: Expand e
Neighbor: z (goal reached)
z: g = 12 + 5 = 17 → f = 17 + 0 = 17
Open List: { z(17), f(20) }
Closed List: { a, c, b, d, e }
----------------------------------------------------------------
Optimal Path with total cost = 17
a→c→d→e→z
-----------------------------------------------------------------