Problem Statement
Use the A* (A-Star) algorithm to find the most cost-effective path from Node A to Node J in the given graph. Edge weights represent the cost (distance), and node values represent the heuristic (h(n)) to the goal node (J).
Given Graph Structure:
- Nodes and their heuristics (h):
A (10), B (3), C (2), D (4), E (3), F (5), G (4), H (3), I (2), J (0) - Edges and their costs (g):
A → B (4), A → F (2)
B → C (3), B → D (1)
C → E (2)
D → E (7)
F → G (1)
G → D (4)
G → I (1)
H → I (2)
F → H (3)
I → J (5)
E → J (3)
Step-by-Step A* Search
A* uses f(n) = g(n) + h(n)
Where:
– g(n): cost from start node to node n
– h(n): heuristic cost from node n to goal
1. Start at Node A:
- f(A) = g(A) + h(A) = 0 + 10 = 10
- Expand A → B (g=4), f(B)=4+3=7; A → F (g=2), f(F)=2+5=7
- Open List: B(f=7), F(f=7)
2. Choose Node B:
- B → C (g=4+3=7), f(C)=7+2=9
- B → D (g=4+1=5), f(D)=5+4=9
3. Choose Node F (also had f=7):
- F → G (g=2+1=3), f(G)=3+4=7
- F → H (g=2+3=5), f(H)=5+3=8
4. Choose Node G (f=7, best):
- G → I (g=3+1=4), f(I)=4+2=6
- G → D (g=3+4=7), f(D)=7+4=11 (not better than previous D)
5. Choose Node I (f=6, best):
- I → J (g=4+5=9), f(J)=9+0=9
Goal Reached: J
- Total cost (g): 9
- Path: A → F → G → I → J
Conclusion
The most cost-effective path from Node A to Node J using A* algorithm is:
A → F → G → I → J
Total Cost: 9
This path is optimal based on the combination of actual cost and heuristic estimates.