FAIRFIELD INSTITUTE OF MANAGEMENT & TECHNOLOGY
SUBJECT :- ARTIFICIAL INTELLIGENCE
PRACTICAL FILE
SUBJECT CODE:- BCA(214)
SUBMITTED TO:- SUBMITTED BY:-
MRS. SHWETA RANA RANIK PRABHAKAR
ASSISTANT PROFESSOR 01151402021
IT DEPARTMENT B.C.A 4 SEMESTER
TH
TABLE OF CONTENT
S.NO CONTENTS PAGE NO. T.SIGN
Write a program to implement Breadth First
1.) and Depth First Search. 1-2
Write a Program for the Best First Search and
2.) A* search algorithm. 3-5
Write a program to implement Water Jug
3.) Problem. 6-8
Write a program to implement 4-Queen
4.) Problem. 9-10
Write a program to implement AO*
5.) algorithm. 11-13
Write a program to implement hill climbing &
6.) steepest ascent hill climbing algorithm. 14-16
Write a program to implement Travelling
7.) Salesman Problem. 17-18
(a) Write a program to implement List
opera ons (Nested List, Length,
8.) Concatena on, Membership, Itera on, 19-24
Indexing and Slicing)?
(b) Write a program to implement List
methods (Add, Append, and Extend & Delete)
Write a program to implement First Order
Predicate using:
9.) a. Backward Chaining 25-27
b. Forward Chaining
Write a program to implement ANN for
10.) Bayesian networks. 28-29
1.) Write a program to implement Breadth First and
Depth First Search.
from collec ons import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def bfs(self, start):
visited = [False] * (max(self.graph) + 1)
queue = []
queue.append(start)
visited[start] = True
while queue:
start = queue.pop(0)
print(start, end=" ")
for neighbor in self.graph[start]:
if not visited[neighbor]:
queue.append(neighbor)
visited[neighbor] = True
def dfs(self, start):
visited = [False] * (max(self.graph) + 1)
self._dfs_u l(start, visited)
def _dfs_u l(self, v, visited):
visited[v] = True
print(v, end=" ")
1
for neighbor in self.graph[v]:
if not visited[neighbor]:
self._dfs_u l(neighbor, visited)
# Test the graph traversal
algorithms graph = Graph()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 0)
graph.add_edge(2, 3)
graph.add_edge(3, 3)
print("BFS traversal:")
graph.bfs(2) # Start from node 2
print("\nDFS traversal:")
graph.dfs(2) # Start from node 2
OUTPUT:-
2
2.) Write a Program for the Best First Search and A* search algorithm.
from queue import PriorityQueue
class Graph:
def __init__(self, heuris c):
self.graph = {}
self.heuris c = heuris c
def add_edge(self, u, v, weight):
if u not in self.graph:
self.graph[u] = []
self.graph[u].append((v, weight))
def best_first_search(self, start, goal):
visited = set()
queue = PriorityQueue()
queue.put((self.heuris c[start], start))
while not queue.empty():
_, current = queue.get()
visited.add(current)
if current == goal:
print("Goal found!")
return
print("Visi ng node:", current)
for neighbor, _ in self.graph.get(current, []):
if neighbor not in visited:
queue.put((self.heuris c[neighbor], neighbor))
print("Goal not found!")
def a_star_search(self, start, goal):
3
visited = set()
queue = PriorityQueue()
queue.put((self.heuris c[start], 0, start, []))
while not queue.empty():
_, cost, current, path = queue.get()
visited.add(current)
if current == goal:
print("Goal found!")
print("Path:", path + [current])
return
print("Visi ng node:", current)
for neighbor, weight in self.graph.get(current, []):
if neighbor not in visited:
queue.put((cost + weight + self.heuris c[neighbor], cost
+ weight, neighbor, path + [current]))
print("Goal not found!")
# Test the graph search algorithms
graph = Graph(heuris c={
'A': 6,
'B': 2,
'C': 1,
'D': 5,
'E': 10,
'F': 0
})
graph.add_edge('A', 'B', 2)
graph.add_edge('A', 'C', 1)
4
graph.add_edge('B', 'D', 3)
graph.add_edge('B', 'E', 5)
graph.add_edge('C', 'F', 8)
graph.add_edge('D', 'F', 4)
graph.add_edge('E', 'F', 3)
print("Best First Search:")
graph.best_first_search('A', 'F')
print("\nA* Search:")
graph.a_star_search('A', 'F')
OUTPUT:-
5
3.) Write a program to implement water jug problem.
from collec ons import deque
def Solu on(a, b, target):
m = {}
isSolvable = False
path = []
q = deque()
#Ini alizing with jugs being empty
q.append((0, 0))
while (len(q) > 0):
# Current state
u = q.pople ()
if ((u[0], u[1]) in
m): con nue
if ((u[0] > a or u[1] > b or
u[0] < 0 or u[1] <
0)): con nue
path.append([u[0],
u[1]]) m[(u[0], u[1])] = 1
if (u[0] == target or u[1] ==
target): isSolvable = True
if (u[0] == target):
if (u[1] != 0):
path.append([u[0], 0])
else:
if (u[0] != 0):
6
path.append([0, u[1]])
sz = len(path)
for i in range(sz):
print("(", path[i][0], ",",
path[i][1], ")")
break
q.append([u[0], b]) # Fill Jug2
q.append([a, u[1]]) # Fill Jug1
for ap in range(max(a, b) + 1):
c = u[0] + ap
d = u[1] - ap
if (c == a or (d == 0 and d >= 0)):
q.append([c, d])
c = u[0] - ap
d = u[1] + ap
if ((c == 0 and c >= 0) or d == b):
q.append([c, d])
q.append([a, 0])
q.append([0, b])
if (not isSolvable):
print("Solu on not possible")
if __name__ == '__main__':
Jug1, Jug2, target = 4, 3, 2
print("Path from ini al state "
"to solu on state ::")
Solu on(Jug1, Jug2, target)
7
OUTPUT:-
8
4.) Write a program to implement 4-Queen Problem.
def is_safe(board, row, col):
for i in range(row):
if board[i][col] == 1:
return False
i = row - 1
j = col - 1
while i >= 0 and j >= 0:
if board[i][j] == 1:
return False
i -= 1
j -= 1
i = row - 1
j = col + 1
while i >= 0 and j < 4:
if board[i][j] == 1:
return False
i -= 1
j += 1
return True
def solve_queens(board, row):
if row == 4:
return True
for col in range(4):
if is_safe(board, row, col):
board[row][col] = 1
9
if solve_queens(board, row + 1):
return True
board[row][col] = 0
return False
def print_board(board):
for row in board:
for cell in row:
print(cell, end=" ")
print()
chessboard = [[0] * 4 for _ in range(4)]
# Solve the 4-Queen Problem
if solve_queens(chessboard, 0):
print("Solu on found:")
print_board(chessboard)
else:
print("No solu on found.")
OUTPUT:-
10
5.) Write a program to implement AO* algorithm.
def Cost(H, condi on, weight = 1):
cost = {}
if 'AND' in condi on:
AND_nodes = condi on['AND']
Path_A = ' AND '.join(AND_nodes)
PathA = sum(H[node]+weight for node in AND_nodes)
cost[Path_A] = PathA
if 'OR' in condi on:
OR_nodes = condi on['OR']
Path_B =' OR '.join(OR_nodes)
PathB = min(H[node]+weight for node in OR_nodes)
cost[Path_B] = PathB
return cost
# Update the cost
def update_cost(H, Condi ons, weight=1):
Main_nodes = list(Condi ons.keys())
Main_nodes.reverse()
least_cost= {}
for key in Main_nodes:
condi on = Condi ons[key]
print(key,':', Condi ons[key],'>>>', Cost(H, condi on, weight))
c = Cost(H, condi on, weight)
H[key] = min(c.values())
least_cost[key] = Cost(H, condi on, weight)
return least_cost
11
# Print the shortest path
def shortest_path(Start,Updated_cost, H):
Path = Start
if Start in Updated_cost.keys():
Min_cost = min(Updated_cost[Start].values())
key = list(Updated_cost[Start].keys())
values = list(Updated_cost[Start].values())
Index = values.index(Min_cost)
# FIND MINIMIMUM PATH
KEY Next = key[Index].split()
# ADD TO PATH FOR OR
PATH if len(Next) == 1:
Start =Next[0]
Path += '<--' +shortest_path(Start, Updated_cost, H)
else:
Path +='<--('+key[Index]+')
' Start = Next[0]
Path += '[' +shortest_path(Start, Updated_cost,
H) + ' + ' Start = Next[-1]
Path += shortest_path(Start, Updated_cost, H) + ']'
return Path
H = {'A': -1, 'B': 10, 'C': 2, 'D': 12, 'E': 7, 'F': 9, 'G': 3, 'H': 1,
'I':0, 'J':0} Condi ons = {
'A': {'OR': ['B'], 'AND': ['C', 'D']},
'B': {'OR': ['E', 'F']},
'C': {'OR': ['G'], 'AND': ['H', 'I']},
12
'D': {'OR': ['J']}
}
# weight
weight = 1
# Updated cost
print('Updated Cost :')
Updated_cost = update_cost(H, Condi ons,
weight=1) print('*'*75)
print('Shortest Path :\n',shortest_path('A', Updated_cost,H))
OUTPUT:-
13
6.) Write a program to implement hill climbing & steepest
ascent hill climbing algorithm.
import random
# Hill Climbing Algorithm
def hill_climbing(problem, max_itera ons):
current_state = problem.generate_random_state()
for _ in range(max_itera ons):
neighbors = problem.generate_neighbors(current_state)
next_state = max(neighbors, key=lambda state: problem.evaluate(state))
if problem.evaluate(next_state) <= problem.evaluate(current_state):
return current_state
current_state = next_state
return current_state
# Steepest Ascent Hill Climbing Algorithm
def steepest_ascent_hill_climbing(problem, max_itera ons):
current_state = problem.generate_random_state()
for _ in range(max_itera ons):
neighbors = problem.generate_neighbors(current_state)
best_state = current_state
for neighbor in neighbors:
if problem.evaluate(neighbor) > problem.evaluate(best_state):
best_state = neighbor
if problem.evaluate(best_state) <= problem.evaluate(current_state):
return current_state
current_state = best_state
return current_state
14
# Example Problem Class
class ExampleProblem:
def __init__(self):
self.target_state = 10 # The goal state we want
to reach def generate_random_state(self):
return random.randint(1, 20) def
generate_neighbors(self, state):
return [state + 1, state -
1] def evaluate(self, state):
return abs(state - self.target_state)
# Usage
problem = ExampleProblem()
max_itera ons = 100
print("Hill Climbing:")
final_state = hill_climbing(problem, max_itera ons)
print("Final State:", final_state)
print("Evalua on:", problem.evaluate(final_state))
print("\nSteepest Ascent Hill Climbing:")
final_state = steepest_ascent_hill_climbing(problem, max_itera ons)
print("Final State:", final_state)
print("Evalua on:", problem.evaluate(final_state))
15
OUTPUT:-
16
7.) Write a program to implement Travelling Salesman problem.
import itertools
def tsp(ci es):
permuta ons = itertools.permuta ons(ci es)
min_distance = float('inf')
best_route = None
for route in permuta ons:
# Calculate the total distance of the
current route total_distance = 0
for i in range(len(route)
- 1): city1 = route[i]
city2 = route[i + 1]
distance = distance_between_ci es(city1,
city2) total_distance += distance
if total_distance < min_distance:
min_distance = total_distance
best_route = route
return best_route, min_distance
def distance_between_ci es(city1, city2):
# This example assumes ci es are represented as (x, y)
coordinates x1, y1 = city1
x2, y2 = city2
distance = ((x2 - x1) ** 2 + (y2 - y1) ** 2)
** 0.5 return distance
ci es = [(0, 0), (1, 5), (5, 9), (6, 2), (3, 8)]
best_route, min_distance = tsp(ci es)
17
print("Best Route:", best_route)
print("Minimum Distance:", min_distance)
OUTPUT:-
18
8.) (a) Write a program to implement List opera ons (Nested List,
Length, Concatena on, Membership, Itera on, Indexing and Slicing)?
NESTED LIST:-
Nested_List = [10, 20, 30,['a', 'b', 'c'], 50]
Sub_List = Nested_List[3]
data = Nested_List[3][1]
print("List inside the nested list: ", Sub_List)
print("Second element of the sublist: ", data)
OUTPUT:-
LENGTH:-
List1 = [10, 20, 30,['a', 'b', 'c'], 50]
print("Total elements present in list1 is: ",len(List1))
OUTPUT:-
19
CONCATENATION:-
List1 = [10, 20, 30, 50]
List2=[-1,-4,89,"Nikhil"]
newList=List1+List2
print("The new added list is: ",newList)
OUTPUT:-
MEMBERSHIP:-
List1 = [10, 20, 30, 50]
if(20 in List1):
print("Yes 20 is present in List1")
else:
print("NO 20 is not present in List1")
OUTPUT:-
20
ITERATION:-
list = [1, 3, 5, 7, 9]
for i in list:
print(i)
OUTPUT:-
INDEXING:-
fruits = ['apple', 'banana', 'cherry']
x = fruits.index("cherry")
print("The cherry is present at the index number is: ",x)
OUTPUT:-
21
SLICING:-
Lst = [50, 70, 30, 20, 90, 10, 50]
print("The normal list is: ",Lst)
print("The slicing in list: ",Lst[1:5])
OUTPUT:-
22
(b) Write a program to implement List methods (Add,
Append, and Extend & Delete).
def print_list(lst):
print("List elements:", lst)
def add_element(lst, index, element):
lst.insert(index, element)
print("Element added successfully!")
def append_element(lst, element):
lst.append(element)
print("Element appended successfully!")
def extend_list(lst, elements):
lst.extend(elements)
print("List extended successfully!")
def delete_element(lst, element):
if element in lst:
lst.remove(element)
print("Element deleted successfully!")
else:
print("Element not found in the list!")
# Tes ng the list methods
my_list = [1, 2, 3, 4, 5]
print_list(my_list)
add_element(my_list, 2,
10) print_list(my_list)
append_element(my_list,
6) print_list(my_list)
23
extend_list(my_list, [7, 8, 9])
print_list(my_list)
delete_element(my_list, 4)
print_list(my_list)
delete_element(my_list, 11)
print_list(my_list)
OUTPUT:-
24
9.) Write a program to implement First Order Predicate using:
a. Backward Chaining
knowledge_base = [
("Parent", "John", "Mary"),
("Parent", "Mary", "Ann"),
("Parent", "Ann", "Tom"),
("Ancestor", ("?x"), ("?y")), # Rule 1
("Ancestor", ("?x"), ("?y")), # Rule 2
]
goal = ("Ancestor", "John", "Tom")
def backward_chaining(query, kb):
if query in kb:
return True
matching_rules = [rule for rule in kb if rule[0] ==
query[0]] for rule in matching_rules:
subs tu on = unify(rule[1:], query[1:])
if subs tu on is not None:
new_kb = subs tute(subs tu on, kb)
if backward_chaining(rule[1], new_kb):
return True
return False
def unify(variables1, variables2):
subs tu on = {}
for var1, var2 in zip(variables1, variables2):
if var1 != var2:
if var1 in subs tu on:
25
if subs tu on[var1] != var2:
return None
else:
subs tu on[var1] = var2
return subs tu on
def subs tute(subs tu on, kb):
new_kb = []
for rule in kb:
new_rule = list(rule)
for i, term in enumerate(new_rule[1:]):
if term in subs tu on:
new_rule[i + 1] = subs tu on[term]
new_kb.append(tuple(new_rule))
return new_kb
result = backward_chaining(goal, knowledge_base)
if result:
print("Goal is proven!")
else:
print("Goal cannot be proven.")
OUTPUT:-
26
b.) Forward Chaining
knowledge_base = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['E', 'F'],
'D': [], 'E': [],
'F': ['G'], 'G': []
} facts = ['A']
while facts:
fact = facts.pop(0)
print("Inferred:", fact)
if fact in knowledge_base: new_facts
= knowledge_base[fact]
facts.extend(new_facts)
print("Forward chaining completed.")
OUTPUT:-
27
10.) Write a program to implement ANN for Bayesian networks.
import tensorflow as
import numpy as np
# Define the Bayesian network structure
# In this example, we have 3 input nodes, 2 hidden layers with 4
and 3 nodes, and 1 output node.
network_structure = [3, 4, 3, 1]
# Define the training data
# Each input-output pair represents a training example for the ANN.
# Modify the data according to your specific problem.
train_data = np.array([[0, 0, 0, 0],
[0, 0, 1, 0],
[0, 1, 0, 0],
[0, 1, 1, 1],
[1, 0, 0, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[1, 1, 1, 1]])
# Separate the input features and target
outputs train_input = train_data[:, :-1]
train_output = train_data[:, -1:]
# Define the neural network model
model = .keras.Sequen al()
for i in range(1, len(network_structure)):
model.add( .keras.layers.Dense(network_structure[i], ac va on='sigmoid'))
model.compile(op mizer='adam',
loss='binary_crossentropy', metrics=['accuracy'])
28
# Train the model
model.fit(train_input, train_output, epochs=1000, verbose=0)
# Evaluate the trained model
loss, accuracy = model.evaluate(train_input, train_output)
print(f'Training accuracy: {accuracy}')
# Test the model
test_data = np.array([[0, 0, 1],
[0, 1, 1],
[1, 0, 0],
[1, 1, 1]])
test_input = test_data
predic ons = model.predict(test_input)
print('Test predic ons:')
for i in range(len(test_input)):
print(f'Input: {test_input[i]}, Predicted Output: {predic ons[i]}')
OUTPUT:-
29
