CSL 411
Artificial Intelligence Lab
Department of Computer Science
Bahria University, Islamabad
1
Lab # 6: Uninformed Search
Objectives:
To learn about uniformed searching, recall your previous lab on Graphs in Python where you implemented a
basic path finding algorithm for Directed, Weighted graphs.
Tools Used:
Visual Studio Code
2
Lab Tasks:
Task # 1: Use the following pseudocode to implement DFS in Python
Pseudocode of iterative approach for DFS:
Use a stack and a list to keep track of the visited nodes.
Begin at the root node, append it to the path and mark it as visited. Then add all its neighbors to the
stack.
At each step pop out an element from the stack and check if it has been visited.
If it has not been visited add it to the path and all its neighbors to the stack.
def dfs_iterative(graph, start):
visited = set()
stack = [start]
path = []
while stack:
node = [Link]()
if node not in visited:
[Link](node)
[Link](node)
[Link](reversed(graph[node]))
return path
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F', 'G'],
'D': [],
'E': ['H'],
'F': ['I'],
3
'G': [],
'H': [],
'I': []
}
if __name__ == "__main__":
start_node = 'A'
dfs_path = dfs_iterative(graph, start_node)
print("DFS Traversal Path:", dfs_path)
Task # 2: Consider the graph given below and traverse the graph through DFS using the network library.
import networkx as nx
def create_graph():
G = [Link]()
edges = [
('A', 'B'), ('A', 'C'), ('B', 'D'), ('B', 'E'),
4
('C', 'F'), ('C', 'G'), ('E', 'H'), ('F', 'I')
G.add_edges_from(edges)
return G
if __name__ == "__main__":
graph = create_graph()
print("DFS Path:", dfs_iterative(graph, 'A'))
Task # 3: Bonus Question
Consider a room service robot that has three rooms (A, B, C) to serve. There is a service room as well.
The robot can serve one room at a time and must go back to the service room before serving the next
room.
Each room will get exactly one service.
Goal: all rooms get service
States: rooms and robot status
Initial state: all rooms need service; robot is in the service room.
Actions: Left move + serve, right move+ serve, up move+ serve, back
5
Make a state space tree. Apply Depth first and Iterative Deepening search to find the goal. Display the path and
path cost. Consider Left move + serve, right move+ serve, have cost 5, whereas up move+ serve has unit cost
and back operation has zero cost.
Your functions of DFS and IDDFS should each return the first path they find from the start node to the goal node,
as well as the total cost of the path undertaken. Note that it is possible to return more than one item/variable in
python using the syntax:
return variable_1, variable_2
DFS
class RoomServiceRobot:
def __init__(self):
[Link] = {
'S': {'A': 5, 'B': 5, 'C': 1},
'A': {'S': 0},
'B': {'S': 0},
'C': {'S': 0}
def dfs(self, start, goal):
stack = [(start, [start], 0)]
while stack:
node, path, cost = [Link]()
if node == goal:
6
return path, cost
for neighbor, move_cost in [Link](node, {}).items():
if neighbor not in path:
[Link]((neighbor, path + [neighbor], cost + move_cost))
return None, float('inf')
if __name__ == "__main__":
robot = RoomServiceRobot()
dfs_path, dfs_cost = [Link]('S', 'A')
print("DFS Path to serve A:", dfs_path, "Cost:", dfs_cost)
IDDFS
class RoomServiceRobotIDDFS:
def __init__(self):
[Link] = {
'S': {'A': 5, 'B': 5, 'C': 1},
'A': {'S': 0},
'B': {'S': 0},
'C': {'S': 0}
}
7
def iddfs(self, start, goal, max_depth=5):
def dls(node, path, cost, depth):
if node == goal:
return path, cost
if depth == 0:
return None, float('inf')
for neighbor, move_cost in [Link](node, {}).items():
if neighbor not in path:
result, total_cost = dls(neighbor, path + [neighbor], cost + move_cost, depth - 1)
if result:
return result, total_cost
return None, float('inf')
for depth in range(max_depth):
result, total_cost = dls(start, [start], 0, depth)
if result:
return result, total_cost
return None, float('inf')
if __name__ == "__main__":
robot = RoomServiceRobotIDDFS()
iddfs_path, iddfs_cost = [Link]('S', 'A')
print("IDDFS Path to serve A:", iddfs_path, "Cost:", iddfs_cost)
8
9
