Scribd
Upload
8 views

problem

The document explains the Greedy Best-First Search (GBFS) algorithm, which prioritizes nodes based on their heuristic value, leading to a path S→A→D→G. It also details the A* algorithm, which combines cost and heuristic to find the optimal path S→B→D→G with a total cost of 16. Lastly, it describes the Uniform Cost Search (UCS) method, which focuses on the lowest cost path, ultimately leading to the goal G.

Uploaded by

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

problem

The document explains the Greedy Best-First Search (GBFS) algorithm, which prioritizes nodes based on their heuristic value, leading to a path S→A→D→G. It also details the A* algorithm, which combines cost and heuristic to find the optimal path S→B→D→G with a total cost of 16. Lastly, it describes the Uniform Cost Search (UCS) method, which focuses on the lowest cost path, ultimately leading to the goal G.

Uploaded by

akshatravi12315
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

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!).

You might also like