AI Lab Experiment No.

Aim: Implement any one of the uninformed search techniques.

Theory: Based on the search problems we can classify the search algorithms into uninformed (Blind
search) search and informed search (Heuristic search) algorithms.

Uninformed Search:
The uninformed search does not contain any domain knowledge such as closeness, the location of the
goal. It operates in a brute-force way as it only includes information about how to traverse the tree and
how to identify leaf and goal nodes. Uninformed search applies a way in which search tree is searched
without any information about the search space like initial state operators and test for the goal, so it is
also called blind search.It examines each node of the tree until it achieves the goal node.
It can be divided into five main types:
Breadth-first search
Uniform cost search
Depth-first search
Iterative deepening depth-first search
Bidirectional Search
Informed Search:
Informed search algorithms use domain knowledge. In an informed search, problem information is
available which can guide the search. Informed search strategies can find a solution more efficiently
than
an uninformed search strategy. Informed search is also called a Heuristic search.
A heuristic is a way which might not always be guaranteed for best solutions but guaranteed to find a
good solution in reasonable time.
Informed search can solve many complex problems which could not be solved in another way.
BFS algorithm
In this article, we will discuss the BFS algorithm in the data structure. Breadth-first search is a graph
traversal algorithm that starts traversing the graph from the root node and explores all the neighboring
nodes. Then, it selects the nearest node and explores all the unexplored nodes. While using BFS for
traversal, any node in the graph can be considered as the root node.
There are many ways to traverse the graph, but among them, BFS is the most commonly used
approach.
It is a recursive algorithm to search all the vertices of a tree or graph data structure. BFS puts every
vertex of the graph into two categories - visited and unvisited. It selects a single node in a graph and,
after
that, visits all the nodes adjacent to the selected node.

TSEC T21 Gaurang Patyane-86

 AI Lab Experiment No.4

Algorithm
The steps involved in the BFS algorithm to explore a graph are given as follows -
Step 1: SET STATUS = 1 (ready state) for each node in G
Step 2: Enqueue the starting node A and set its STATUS = 2 (waiting state)
Step 3: Repeat Steps 4 and 5 until QUEUE is empty
Step 4: Dequeue a node N. Process it and set its STATUS = 3 (processed state).
Step 5: Enqueue all the neighbors of N that are in the ready state (whose STATUS = 1) and set their
STATUS = 2
(waiting state)
[END OF LOOP]
Step 6: EXIT
The space complexity of BFS can be expressed as O(V), where V is the number of vertices.
Example:

DFS algorithm:
Depth-First Search or DFS algorithm is a recursive algorithm that uses the backtracking
principle. It
entails conducting exhaustive searches of all nodes by moving forward if possible and
backtracking, if
necessary. To visit the next node, pop the top node from the stack and push all of its nearby
nodes into a
stack. Topological sorting, scheduling problems, graph cycle detection, and solving puzzles
with just one
solution, such as a maze or a sudoku puzzle, all employ depth-first search algorithms.

TSEC T21 Gaurang Patyane-86

 AI Lab Experiment No.4

Algorithm
To implement DFS traversal, you need to take the following stages.
Step 1: Create a stack with the total number of vertices in the graph as the size.
Step 2: Choose any vertex as the traversal's beginning point. Push a visit to that vertex and
add it to the
stack.
Step 3 - Push any non-visited adjacent vertices of a vertex at the top of the stack to the top of
the stack.
Step 4 - Repeat steps 3 and 4 until there are no more vertices to visit from the vertex at the
top of the
stack.
Step 5 - If there are no new vertices to visit, go back and pop one from the stack using
backtracking.
Step 6 - Continue using steps 3, 4, and 5 until the stack is empty.
Step 7 - When the stack is entirely unoccupied, create the final spanning tree by deleting the
graph's
unused edges.
The space complexity of DFS is O(V), where V is the number of vertices.
Example:

TSEC T21 Gaurang Patyane-86

 AI Lab Experiment No.4

WATER JUG PROBLEM DFS:

You are given an m liter jug and a n liter jug. Both the jugs are initially empty. The jugs don’t
have
markings to allow measuring smaller quantities. You have to use the jugs to measure d liters
of water
where d is less than n.
(X, Y) corresponds to a state where X refers to the amount of water in Jug1 and Y refers to
the amount of
water in Jug2
Determine the path from e initial state (xi, yi) to the final state (xf, yf), where (xi, yi) is (0, 0)
which
indicates both Jugs are initially empty and (xf, yf) indicates a state which could be (0, d) or
(d, 0).
The operations you can perform are:
1. Empty a jug (X, 0)->(0, 0) Empty Jug
2. Fill a Jug, (0, 0)->(X, 0) Fill Jug 1

PROGRAM: OUTPUT:
def DFS(a, b, target, m, path):
if ((a, b) in m):
return
if (a > Jug1 or b > Jug2 or a < 0 or b < 0):
return
path.append((a, b))
m.add((a, b))
if (a == target or b == target):
print("Solution found:")
for point in path:
print(point)
return
# Fill Jug1
DFS(Jug1, b, target, m, path)
# Fill Jug2
DFS(a, Jug2, target, m, path)
# Empty Jug1
DFS(0, b, target, m, path)
# Empty Jug2
DFS(a, 0, target, m, path)
# Pour Jug1 to Jug2
pour = min(a, Jug2 - b)
DFS(a - pour, b + pour, target, m, path)
# Pour Jug2 to Jug1
pour = min(b, Jug1 - a)
DFS(a + pour, b - pour, target, m, path)
# Driver code
if __name__ == '__main__':
Jug1, Jug2, target = 4, 3, 2
print("Path from initial state to solution state ::")
m = set() # Set to store visited states
path = [] # List to store the solution path
DFS(0, 0, target, m, path)

TSEC T21 Gaurang Patyane-86

 AI Lab Experiment No.4

8 PUZZLE USING BFS:

Given a 3×3 board with 8 tiles (every tile has one number from 1 to 8) and one empty space. The
objective is to place the numbers on tiles to match the final configuration using the empty space. We
can
slide four adjacent (left, right, above, and below) tiles into the empty space.

PROGRAM: OUTPUT:

from collections import deque

# Goal state
GOAL_STATE = [1, 2, 3, 4, 5, 6, 7, 8, 0]
# Actions for moving the empty tile
MOVES = {
0: [1, 3],
1: [0, 2, 4],
2: [1, 5],
3: [0, 4, 6],
4: [1, 3, 5, 7],
5: [2, 4, 8],
6: [3, 7],
7: [4, 6, 8],
8: [5, 7]
}

def bfs(initial_state):
visited = set()
queue = deque([(initial_state, [])]) # Tuple: (state, path)
while queue:
current_state, path = queue.popleft()
if current_state == GOAL_STATE:
return path
visited.add(tuple(current_state))
empty_tile_index = current_state.index(0)
for move in MOVES[empty_tile_index]:
new_state = current_state[:]
new_state[empty_tile_index], new_state[move] = new_state[move],
new_state[empty_tile_index]
if tuple(new_state) not in visited:
queue.append((new_state, path + [move]))
visited.add(tuple(new_state))
return None # No solution found
def print_board(state):
for i in range(0, 9, 3):
print(state[i:i + 3])
# Initial state (change this to your desired initial configuration)
initial_state = [1, 2, 3, 4, 0, 5, 7, 8, 6]
solution_path = bfs(initial_state)
if solution_path:
print("Solution found! Moves:")
for move in solution_path:
print_board(initial_state)
print("Move empty tile to position:", move)
initial_state[move], initial_state[initial_state.index(0)] =
initial_state[initial_state.index(0)], initial_state[move]
print_board(initial_state)
else:
print("No solution found.")

TSEC T21 Gaurang Patyane-86