Scribd
Upload
3 views5 pages

Ai Pgms Python

The document contains Python implementations of two algorithms: Depth First Search (DFS) for the Water Jug Problem and Best First Search for the Missionaries-Cannibals Problem. The DFS algorithm explores all possible states of two jugs to reach a target volume, while the Best First Search algorithm finds a valid sequence of moves to transport missionaries and cannibals across a river. Both implementations include state management, validation, and path tracking to demonstrate the solutions.

Uploaded by

Subhashri C
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views5 pages

Ai Pgms Python

The document contains Python implementations of two algorithms: Depth First Search (DFS) for the Water Jug Problem and Best First Search for the Missionaries-Cannibals Problem. The DFS algorithm explores all possible states of two jugs to reach a target volume, while the Best First Search algorithm finds a valid sequence of moves to transport missionaries and cannibals across a river. Both implementations include state management, validation, and path tracking to demonstrate the solutions.

Uploaded by

Subhashri C
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

1.

Implement and Demonstrate Depth First Search Algorithm on Water Jug Problem

class State:

def __init__(self, jug1, jug2):

self.jug1 = jug1

self.jug2 = jug2

def __eq__(self, other):

return self.jug1 == other.jug1 and self.jug2 == other.jug2

def __hash__(self):

return hash((self.jug1, self.jug2))

def __str__(self):

return f"({self.jug1}, {self.jug2})"

def dfs(jug1_capacity, jug2_capacity, target):

visited = set()

stack = [(0, 0, [])] # (jug1, jug2, path)

while stack:

jug1, jug2, path = [Link]()

if jug1 == target or jug2 == target:

return path + [(jug1, jug2)]

if (jug1, jug2) in visited:

continue

[Link]((jug1, jug2))

# Fill jug1
[Link]((jug1_capacity, jug2, path + [(jug1, jug2)]))

# Fill jug2

[Link]((jug1, jug2_capacity, path + [(jug1, jug2)]))

# Empty jug1

[Link]((0, jug2, path + [(jug1, jug2)]))

# Empty jug2

[Link]((jug1, 0, path + [(jug1, jug2)]))

# Pour jug1 to jug2

pour_amount = min(jug1, jug2_capacity - jug2)

[Link]((jug1 - pour_amount, jug2 + pour_amount, path + [(jug1, jug2)]))

# Pour jug2 to jug1

pour_amount = min(jug2, jug1_capacity - jug1)

[Link]((jug1 + pour_amount, jug2 - pour_amount, path + [(jug1, jug2)]))

return None

# Example usage:

jug1_capacity = 5

jug2_capacity = 3

target = 4

result = dfs(jug1_capacity, jug2_capacity, target)

if result:

print("Solution found:")

for step in result:

print(step)

else:

print("No solution exists.")

[Link] and Demonstrate Best First Search Algorithm on Missionaries-Cannibals Problems


using Python
class State:

def __init__(self, missionaries, cannibals, boat):

[Link] = missionaries

[Link] = cannibals

[Link] = boat

def __eq__(self, other):

return [Link] == [Link] and \

[Link] == [Link] and \

[Link] == [Link]

def __hash__(self):

return hash(([Link], [Link], [Link]))

def __str__(self):

return f"M({[Link]}) C({[Link]}) B({[Link]})"

def is_valid(state):

if [Link] < 0 or [Link] > 3:

return False

if [Link] < 0 or [Link] > 3:

return False

if [Link] < [Link] and [Link] != 0:

return False

if [Link] > [Link] and [Link] != 3:

return False

return True

def successors(state):
moves = [(2, 0), (1, 0), (1, 1), (0, 1), (0, 2)]

next_states = []

for move in moves:

if [Link] == 1:

next_state = State([Link] - move[0], [Link] - move[1], 0)

else:

next_state = State([Link] + move[0], [Link] + move[1], 1)

if is_valid(next_state):

next_states.append(next_state)

return next_states

def best_first_search():

start_state = State(3, 3, 1)

goal_state = State(0, 0, 0)

visited = set()

queue = [(start_state, [start_state])]

while queue:

[Link](key=lambda x: heuristic(x[0], goal_state))

state, path = [Link](0)

if state == goal_state:

return path

[Link](state)

for next_state in successors(state):

if next_state not in visited:

new_path = path + [next_state]


[Link]((next_state, new_path))

return None

def heuristic(state, goal_state):

return abs([Link] - goal_state.missionaries) + abs([Link] -


goal_state.cannibals)

def print_solution(path):

for i, state in enumerate(path):

print(f"Step {i + 1}: {state}")

# Example usage:

solution_path = best_first_search()

if solution_path:

print("Solution found:")

print_solution(solution_path)

else:

print("No solution exists.")

You might also like