Scribd
Upload
6 views2 pages

Greedy vs A* Search Algorithms Analysis

The document analyzes two search algorithms, Greedy Best-First Search (GBFS) and A* Search, for finding the optimal path from a start node S to a goal node G. GBFS focuses solely on heuristic values, resulting in 6 nodes expanded, while A* considers both the distance traveled and heuristic, expanding 8 nodes. Both algorithms yield the same final path, but A* guarantees the shortest path, whereas GBFS may be faster but less reliable in complex graphs.

Uploaded by

abdullahnasarullah9595
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views2 pages

Greedy vs A* Search Algorithms Analysis

The document analyzes two search algorithms, Greedy Best-First Search (GBFS) and A* Search, for finding the optimal path from a start node S to a goal node G. GBFS focuses solely on heuristic values, resulting in 6 nodes expanded, while A* considers both the distance traveled and heuristic, expanding 8 nodes. Both algorithms yield the same final path, but A* guarantees the shortest path, whereas GBFS may be faster but less reliable in complex graphs.

Uploaded by

abdullahnasarullah9595
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

AI Assignment Greedy Best-First

Search & A* Search


In this assignment, I analyze a search graph with heuristic values (h) and edge costs to find the
optimal path from the start node S to the goal node G. We solve it using two algorithms:

1. 1. Greedy Best-First Search (GBFS)


2. 2. A* Search

1. Greedy Best-First Search


Greedy Best-First Search is like picking the node that *feels closest* to the goal. It ignores how
far you’ve come and only looks at the heuristic h(n), which estimates how far you are from the
goal.

Step-by-step Execution:

 Step 1
Open: [S(h=7)]
Closed: [] → Expand S → Add A(h=5), B(h=4) → Pick B (lowest h)
 Step 2
Open: [A(h=5), B(h=4)]
Closed: [S] → Expand B → Add C(h=5), E(h=2) → Pick E
 Step 3
Open: [A(h=5), C(h=5), E(h=2)]
Closed: [S, B] → Expand E → Add D(h=2), F(h=1) → Pick F
 Step 4
Open: [A(h=5), C(h=5), D(h=2), F(h=1)]
Closed: [S, B, E] → Expand F (does not lead to G)
 Step 5
Open: [A(h=5), C(h=5), D(h=2)]
Closed: [S, B, E, F] → Expand D → Add G(h=0) → Pick G
 Step 6
Open: [A(h=5), C(h=5), G(h=0)]
Closed: [S, B, E, F, D] → Expand G → Goal Reached!

Final Path (reconstructed): S → B → E → D → G

Total Nodes Expanded: 6

2. A* Search
A* Search is smarter. It looks at both the distance you've already traveled (g) and the estimated
distance left (h). It picks the node with the lowest f(n) = g(n) + h(n).
Step-by-step Execution:

 Step 1
Open: [S(f=0+7=7)]
Closed: [] → Expand S → Add A(f=3+5=8), B(f=2+4=6) → Pick B
 Step 2
Open: [A(f=8), B(f=6)]
Closed: [S] → Expand B → Add C(f=3+5=8), E(f=6+2=8) → Pick A (tie break)
 Step 3
Open: [C(f=8), E(f=8), A(f=8)]
Closed: [S, B] → Expand A → Add D(f=6+2=8)
 Step 4
Open: [C(f=8), E(f=8), D(f=8)]
Closed: [S, B, A] → Expand C (leads to H, not useful)
 Step 5
Open: [E(f=8), D(f=8)]
Closed: [S, B, A, C] → Expand E → Add F(f=7+1=8)
 Step 6
Open: [D(f=8), F(f=8)]
Closed: [S, B, A, C, E] → Expand D → Add G(f=9+0=9)
 Step 7
Open: [F(f=8), G(f=9)]
Closed: [S, B, A, C, E, D] → Expand F (not helpful)
 Step 8
Open: [G(f=9)]
Closed: [S, B, A, C, E, D, F] → Expand G → Goal Reached!

Final Path (reconstructed): S → B → E → D → G

Total Nodes Expanded: 8

3. Comparison of Efficiency
Both algorithms found the same final path (S → B → E → D → G). However, Greedy Best-First
Search was a bit faster here with 6 nodes expanded versus A* which expanded 8. But A*
guarantees the shortest path, while Greedy can sometimes get stuck or take longer in tricky
graphs.

You might also like