Name: Abhishek Karad
PRN No.: 1032232220
Date of Performance:21 July 2025
Experiment No.: 2 Title: Implementation of A* Algorithm for Problem Solving
In [2]: graph = {
'S': [('A', 2), ('B', 1), ('F', 3)],
'A': [('C', 2), ('D', 3)],
'B': [('D', 2), ('E', 4)],
'C': [('G', 4)],
'D': [('G', 4)],
'E': [],
'F': [('G', 6)],
'G': []
}
heuristics = {'S': 6, 'A': 4, 'B': 5, 'C': 2, 'D': 2, 'E': 8, 'F': 4, 'G': 0}
def astar(S, G):
open_set = set([S])
closed_set = set()
g = {S: 0}
parents = {S: None}
step = 1
while open_set:
print(f"\nStep {step}:")
def fn(node): return g[node] + heuristics[node]
print("Open List: ", [(node, fn(node)) for node in open_set])
print("Closed List: ", [(node, fn(node)) for node in closed_set])
n = None
for v in open_set:
if n is None or fn(v) < fn(n):
n = v
if n == G:
gn = g[G]
hn = heuristics[G]
fn_val = gn + hn
print(f"\nGoal Node: {G}")
print(f"g({G}) = {gn}")
print(f"h({G}) = {hn}")
print(f"f({G}) = g({G}) + h({G}) = {fn_val}")
print(f"Total cost (shortest path): {gn}")
path = []
while n is not None:
path.append(n)
n = parents[n]
return path[::-1]
open_set.remove(n)
closed_set.add(n)
for (m, cost) in graph.get(n, []):
if m in closed_set:
continue
tentative_g = g[n] + cost
if m not in open_set or tentative_g < g.get(m, float('inf')):
g[m] = tentative_g
parents[m] = n
open_set.add(m)
step += 1
return None
result_path = astar('S', 'G')
print("\nA* Path:", result_path)
Step 1:
Open List: [('S', 6)]
Closed List: []
Step 2:
Open List: [('A', 6), ('B', 6), ('F', 7)]
Closed List: [('S', 6)]
Step 3:
Open List: [('D', 7), ('B', 6), ('C', 6), ('F', 7)]
Closed List: [('A', 6), ('S', 6)]
Step 4:
Open List: [('D', 5), ('E', 13), ('C', 6), ('F', 7)]
Closed List: [('A', 6), ('B', 6), ('S', 6)]
Step 5:
Open List: [('E', 13), ('G', 7), ('C', 6), ('F', 7)]
Closed List: [('A', 6), ('B', 6), ('D', 5), ('S', 6)]
Step 6:
Open List: [('E', 13), ('G', 7), ('F', 7)]
Closed List: [('S', 6), ('D', 5), ('B', 6), ('C', 6), ('A', 6)]
Goal Node: G
g(G) = 7
h(G) = 0
f(G) = g(G) + h(G) = 7
Total cost (shortest path): 7
A* Path: ['S', 'B', 'D', 'G']
Post Lab Questions
1. What is Heuristic Search?
Heuristic search is a type of search algorithm that uses domain-specific knowledge to find solutions more
efficiently than uninformed search methods.
Types of Heuristic Search:
• Greedy Best-First Search: Selects the node with the lowest heuristic value h(n) at each step.
• A* Search: Uses f(n) = g(n) + h(n) , where:
▪ g(n) is the cost from the start node to the current node.
▪ h(n) is the heuristic estimate from the current node to the goal.
• Hill Climbing: Moves to neighboring nodes that have better (lower) heuristic values.
• Beam Search: Similar to Best-First Search, but only keeps a fixed number of best candidates at each
level.
• IDA* (Iterative Deepening A*): Combines the benefits of A* and iterative deepening search.
Advantages:
• Reduces search time by focusing on promising paths.
• Can find solutions faster than uninformed methods.
• Effective in large or complex state spaces.
Limitations:
• The quality of the solution depends on the accuracy of the heuristic.
• If the heuristic is not admissible, it may miss the optimal solution.
• Designing a good heuristic is often difficult.
2. Solutions for the Given State Space Graph
Legend:
• States: S, A, B, C, D, E, F, G
• Costs are given on edges (from the diagram).
• Heuristic values (examples): h(S) = 6, h(A) = 4, h(B) = 5, h(C) = 2, h(D) = 2, etc.
• Goal state: G
• All actions are one-way (directed edges).
A. Breadth-First Search (BFS)
• Explores all nodes at the current depth before going deeper.
• Uses a queue (FIFO).
Path from S:
1. From S, visit children: A, B, F
2. Expand A → add C, D
3. Expand B → add D, E
4. Expand F → add G
First time G is reached: via F
BFS Path: S → F → G
Total Cost: 3 (S-F) + 6 (F-G) = 9
B. Depth-First Search (DFS)
• Explores as deep as possible before backtracking.
• Uses a stack or recursion.
One possible DFS path:
1. S
2. A
3. C
4. G
DFS Path: S → A → C → G
Total Cost: 2 (S-A) + 2 (A-C) + 4 (C-G) = 8
Note: DFS path may vary depending on the order of visiting children.
C. A* Search (with Heuristics)
• A* uses the formula: f(n) = g(n) + h(n)
▪ g(n) is the cost so far from start node S to node n
▪ h(n) is the estimated cost from n to goal G
Steps:
1. Start at S:
f(S) = 0 + h(S) = 6
Expand S:
• A: g=2, h=4 → f=6
• B: g=1, h=5 → f=6
• F: g=3, h=4 → f=7
2. Expand A (tie-break):
• C: g=4, h=2 → f=6
• D: g=5, h=2 → f=7
3. Expand B:
• D: g=3, h=2 → f=5 (lowest so far)
• E (skip for now)
4. Expand D:
• G: g=7, h=0 → f=7
Final Path: S → B → D → G
Total Cost: 1 (S-B) + 2 (B-D) + 4 (D-G) = 7
Summary of Results
BFS Path: S → F → G → Total Cost = 9
DFS Path: S → A → C → G → Total Cost = 8
A* Path: S → B → D → G → Total Cost = 7
Conclusion
Heuristic search algorithms like A* can efficiently reach the goal by using extra information (heuristics) to
guide the search process.
Among the three strategies applied on this graph:
• A* was the most cost-effective.
• DFS found a valid solution but not always optimal.
• BFS is complete and finds the shortest path only when all step costs are equal.
Learnings from A* Algorithm Implementation
• Gained understanding of how the A* algorithm combines both the actual cost (g) and estimated cos
(heuristic, h) to determine the most promising path.
• Learned to manage the OPEN list (nodes to be explored) and the CLOSED list (already explored
nodes) for efficient graph traversal.
• Explored how heuristics significantly guide the search direction, improving efficiency compared to
uninformed algorithms.
• Realized the importance of using an admissible heuristic (never overestimates) to ensure optimal
solutions.
• Observed how consistent heuristics (where h(n) ≤ cost(n → n') + h(n')) further enhance algorithm
performance and correctness.
Conclusions
• A* is a powerful and efficient algorithm for optimal pathfinding, especially in weighted graphs.
• It combines the strengths of Uniform Cost Search and Greedy Best-First Search.
• The choice of heuristic critically affects both speed and accuracy of the solution.
• When the heuristic is both admissible and consistent, A* is guaranteed to find the shortest possible
path.
