DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Experiment-1.1
Student Name: Preet Kumar UID: 21BCS2931
Branch: CSE Section/Group:21BCS-627/A
Semester: 5th Date of Performance: 17/08/23
Subject Name: AIML Subject Code: 21CSH-316
1. Aim: Implement A* algorithm in python.
2. Objective: Implement the A* algorithm to efficiently find the shortest
path in a graph while considering both the cost to reach a node and a
heuristic estimate of its potential to reach the goal.
3. Algorithm Loop:
1. While the open_set is not empty:
Find the node n in the open_set with the lowest value of f(n) = g(n) + h(n),
where g(n) is the cost to reach node n from the start node and h(n) is the
heuristic estimate of the cost to reach the goal from node n.
2. If n is the goal node, the shortest path has been found. Reconstruct the
path using the parents dictionary and return it.
3. Move n from the open_set to the closed_set to mark it as evaluated.
4. Source Code:
def aStarAlgo(start_node, stop_node):
open_set = set([start_node]) closed_set
= set()
g = {} # store distance from starting node
parents = {} # parents contains an adjacency map of all nodes
# distance of starting node from itself is zero g[start_node]
=0
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
# start_node is root node i.e it has no parent nodes
# so start_node is set to its own parent node
parents[start_node] = start_node
while len(open_set) > 0:
n = None
# node with lowest f() is found for
v in open_set:
if n is None or g[v] + heuristic(v) < g[n] + heuristic(n):
n=v
if n == stop_node or Graph_nodes[n] is None: pass
else:
for (m, weight) in get_neighbors(n):
# nodes 'm' not in first and last set are added to first
# n is set its parent if m not in open_set and
m not in closed_set:
open_set.add(m)
parents[m] = n g[m]
= g[n] + weight
# for each node m, compare its distance from start i.e g(m) to the
# from start through n node else:
if g[m] > g[n] + weight: #
update g(m) g[m] = g[n]
+ weight # change parent
of m to n parents[m] = n
# if m in closed set, remove and add to
open if m in closed_set:
closed_set.remove(m) open_set.add(m)
# if n is still None, then path does not exist
if n is None: print('Path does not exist!')
return None
# if the current node is the stop_node
# then we begin reconstruction the path from it to the start_node
if n == stop_node:
path = [] while
parents[n] != n:
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
path.append(n) n =
parents[n]
path.append(start_node)
path.reverse()
print('Path found: {}'.format(path)) return
path
# remove n from the open_set, and add it to closed_set #
because all of its neighbors were inspected
open_set.remove(n)
closed_set.add(n)
print('Path does not exist!') return
None
# define function to return neighbor and its distance
# from the passed node def
get_neighbors(v):
if v in Graph_nodes:
return Graph_nodes[v] else:
return None
# for simplicity, we'll consider heuristic distances given
# and this function returns heuristic distance for all
nodes def heuristic(n):
H_dist = {
'A': 11,
'B': 6,
'C': 99,
'D': 1,
'E': 7,
'G': 0,
}
return H_dist[n]
# Describe your graph here Graph_nodes
={
'A': [('B', 2), ('E', 3)],
'B': [('C', 1), ('G', 9)],
'C': None,
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
'E': [('D', 6)],
'D': [('G', 1)],
}
print('Name – Preet
Kumar')
print('UID - 21BCS2931')
aStarAlgo('A', 'G')
5. Output:
