A
A* algo-
Step 1: Understand the Graph
Nodes: A, B, C, D, E, F, G, H, I, J
Edges with actual cost (black numbers)
Heuristic values (red numbers) = estimated distance to goal
Goal node: Assume J (common in examples)
A* evaluation function:
f (n)=g(n)+ h(n)
Where:
g(n) = cost to reach node n from start
h(n) = heuristic estimate from node n to goal
Start Node = A, Goal Node = J
Step 2: Initialize
OPEN = {A}
g(A) = 0
h(A) = 10 → f(A) = 0 + 10 = 10
CLOSED = {}
Step 3: Expand Node A
Neighbors of A: F (cost 3)
g(F) = g(A) + cost(A→F) = 0 + 3 = 3
h(F) = 6 → f(F) = g(F) + h(F) = 3 + 6 = 9
OPEN = {F (f=9)}
CLOSED = {A}
Step 4: Expand Node F
Neighbors: G (cost 1)
g(G) = g(F) + cost(F→G) = 3 + 1 = 4
h(G) = 5 → f(G) = 4 + 5 = 9
OPEN = {G (f=9)}
CLOSED = {A, F}
Step 5: Expand Node G
Neighbors: I (cost 3)
g(I) = g(G) + cost(G→I) = 4 + 3 = 7
h(I) = 1 → f(I) = 7 + 1 = 8
OPEN = {I (f=8)}
CLOSED = {A, F, G}
Step 6: Expand Node I
Neighbors: J (cost 3)
g(J) = g(I) + cost(I→J) = 7 + 3 = 10
h(J) = 0 → f(J) = 10 + 0 = 10
OPEN = {J (f=10)}
CLOSED = {A, F, G, I}
Step 7: Expand Node J (Goal)
Node J is goal → stop
Path found
Step 8: Reconstruct Path
Path:
A→F→G→I→J
Costs:
g(A) = 0
g(F) = 3
g(G) = 4
g(I) = 7
g(J) = 10
Total cost = 10
Step 9: Summary Table of f(n)
Node g(n) h(n) f(n)
A 0 10 10
F 3 6 9
G 4 5 9
I 7 1 8
J 10 0 10
✅ Final Answer:
Optimal Path (A*):
A→F→G→I→J
Total Cost: 10
A algo
A (best-first search) algorithm, which uses heuristic only (f(n) = h(n)), ignoring actual path cost. This
is slightly different from A*.
Step 1: Initialize
Start node = A
Goal node = J
OPEN = {A}
CLOSED = {}
A algorithm:
f (n)=h (n)
Select node with lowest heuristic value to expand.
Step 2: Expand Node A
Neighbors of A: F
h(F) = 6 → f(F) = 6
OPEN = {F (f=6)}
CLOSED = {A}
Step 3: Expand Node F
Neighbors: G
h(G) = 5 → f(G) = 5
OPEN = {G (f=5)}
CLOSED = {A, F}
Step 4: Expand Node G
Neighbors: I
h(I) = 1 → f(I) = 1
OPEN = {I (f=1)}
CLOSED = {A, F, G}
Step 5: Expand Node I
Neighbors: J
h(J) = 0 → f(J) = 0
OPEN = {J (f=0)}
CLOSED = {A, F, G, I}
Step 6: Expand Node J
Node J is goal → stop
Step 7: Reconstruct Path
Path (A algorithm / heuristic only):
A→F→G→I→J
Heuristic sequence:
10 → 6 → 5 → 1 → 0
Note
A algorithm uses heuristic only → may not give optimal path in all graphs
In this case, the path is same as A* because heuristic values are consistent.
Total actual cost = 10 (but A algorithm doesn’t consider this while choosing nodes)
✅ Final Answer (A search):
A→F→G→I→J
Total Cost (actual g(n)) = 10
Breadth First Search (BFS)
🔹 Concept (AI definition)
BFS explores level by level
Uses QUEUE (FIFO)
Finds shortest path in unweighted graphs
🔹 BFS Traversal Steps (starting from A)
Step 1: Start at A
Queue = [A]
Visited = A
Step 2: Visit A → enqueue its neighbor F
Queue = [F]
Visited = A, F
Step 3: Visit F → enqueue G
Queue = [G]
Visited = A, F, G
Step 4: Visit G → enqueue I
Queue = [I]
Visited = A, F, G, I
Step 5: Visit I → enqueue J
Queue = [J]
Visited = A, F, G, I, J
Step 6: Visit J → no new neighbors
Queue = [ ]
✅ BFS Traversal Order
A→F→G→I→J
3️⃣ Depth First Search (DFS)
🔹 Concept (AI definition)
DFS explores as deep as possible
Uses STACK / RECURSION (LIFO)
Does NOT guarantee shortest path
🔹 DFS Traversal Steps (starting from A)
Step 1: Visit A
Go to F
Step 2: Visit F
Go to G
Step 3: Visit G
Go to I
Step 4: Visit I
Go to J
Step 5: Visit J
No more children → backtrack
✅ DFS Traversal Order
A→F→G→I→J