Greedy Best-First Search (GBFS) Algorithm
GBFS expands the node that appears to be closest to the goal, based only on the heuristic function
(h(n)). It does not consider the cost from the start node.
Steps to Apply GBFS on This Graph
1. Start at node S (h=9).
2. From S, choose the node with the smallest heuristic:
o A (h=2)
o B (h=3)
o Choose A (h=2), as it's the smallest.
3. From A, possible moves:
o D (h=5)
o Choose D (h=5), since it's the only option.
4. From D, possible moves:
o C (h=10)
o B (h=3)
o G (h=0) **(Goal found!)**
o Choose G, as h(G) = 0 means it's the goal.
Final Path Found by GBFS
S→A→D→G
Characteristics of GBFS
• It is not optimal because it ignores the actual cost.
• It is fast but may get stuck in loops or bad paths.
• It prioritizes nodes with the smallest heuristic (h(n)).
Step-by-Step Execution of A* Algorithm
1. Initialize:
• Start at S with f(S) = g(S) + h(S) = 0 + 9 = 9
• Open list: {S}
• Closed list: {}
2. Expand S:
• Neighbors:
o A: g(A) = 3, h(A) = 2, f(A) = 3 + 2 = 5
o B: g(B) = 3, h(B) = 3, f(B) = 3 + 3 = 6
• Open list: {A (f=5), B (f=6)}
• Closed list: {S}
• Choose A (smallest f).
3. Expand A:
• Neighbors:
o D: g(D) = 3 + 3 = 6, h(D) = 5, f(D) = 6 + 5 = 11
• Open list: {B (f=6), D (f=11)}
• Closed list: {S, A}
• Choose B (smallest f).
4. Expand B:
• Neighbors:
o D: g(D) = 3 + 1 = 4, h(D) = 5, f(D) = 4 + 5 = 9 (update D, as 9 < 11)
o E: g(E) = 3 + 8 = 11, h(E) = 6, f(E) = 11 + 6 = 17
• Open list: {D (f=9), E (f=17)}
• Closed list: {S, A, B}
• Choose D (smallest f).
5. Expand D:
• Neighbors:
o C: g(C) = 4 + 4 = 8, h(C) = 10, f(C) = 8 + 10 = 18
o G: g(G) = 4 + 12 = 16, h(G) = 0, f(G) = 16 + 0 = 16
• Open list: {E (f=17), C (f=18), G (f=16)}
• Closed list: {S, A, B, D}
• Choose G (goal found!).
Final A* Path:
S → B → D → G (Total cost = 16)
Step-by-Step Execution of UCS
1. Initialize:
• Start at S with g(S) = 0
• Open list (priority queue based on cost): {(S, g=0)}
• Closed list: {}
2. Expand S:
• Neighbors:
o A: g(A) = 0 + 3 = 3
o B: g(B) = 0 + 3 = 3
• Open list: {(A, g=3), (B, g=3)}
• Closed list: {S}
• Choose A (smallest g).
3. Expand A:
• Neighbors:
o D: g(D) = 3 + 3 = 6
• Open list: {(B, g=3), (D, g=6)}
• Closed list: {S, A}
• Choose B (smallest g).
4. Expand B:
• Neighbors:
o D: g(D) = 3 + 1 = 4 (update D since 4 < 6)
o E: g(E) = 3 + 8 = 11
• Open list: {(D, g=4), (E, g=11)}
• Closed list: {S, A, B}
• Choose D (smallest g).
5. Expand D:
• Neighbors:
o C: g(C) = 4 + 4 = 8
o G: g(G) = 4 + 12 = 16
• Open list: {(E, g=11), (C, g=8), (G, g=16)}
• Closed list: {S, A, B, D}
• Choose C (smallest g).
6. Expand C:
• Neighbors:
o G: g(G) = 8 + 9 = 17 (ignore since 16 < 17)
• Open list: {(E, g=11), (G, g=16)}
• Closed list: {S, A, B, D, C}
• Choose E.
7. Expand E:
• Neighbors:
o G: g(G) = 11 + 13 = 24 (ignore since 16 < 24)
• Open list: {(G, g=16)}
• Closed list: {S, A, B, D, C, E}
• Choose G (goal found!).
