GURU GOBIND SINGH INDRAPRASTHA UNIVERSITY

INSTITUTE OF INFORMATION TECHNOLOGY &

MANAGEMENT

ARTIFICIAL INTELLIGENCE
PRACTICAL FILE
SUBJECT CODE: BCAP - 254

Submitted To: Submitted By:

Dr. Manzoor Ansari Name: Jayant Chaudhary
Ms. Lakshmi Kumari Class: BCA IV – M2
Enroll. No: 07113702022

Institute of Information Technology & Management, New Delhi

(Affiliated to GGSIP University)
Lecture- No Topic/ Module Details with subtopics/ Title of Project Date on Signature
which
delivered

Write steps to install Python and required libraries for AI:

L-1 Write instructions for setting up a Python virtual 29-01-24
environment:

L-2 Write a program to implement Breadth First Search and

Depth First Search 05-02-24

L-3 Write a program for Best First Search and A* Search Algorithm
12-02-24

Write a program to solve the Water Jug Problem

L-4
19-02-24

L-5 Write a program to solve the 4-Queen Problem

26-02-24

L-6 Write a program to implement AO* Algorithm 04-03-24

Write a program to implement Hill Climbing and Steepest Ascent

L-7 Hill Climbing Algorithm 11-03-24

Write a program to solve the Travelling Salesman Problem 18-03-24

L-8

Write a program for list operations (Nested List, Length,

Concatenation, Membership, Iteration, Indexing, and Slicing) 01-04-24
L-9

Write a program for list methods (Add, Append, Extend & Delete) 08-04-24
L-
10
Write a program to implement First Order Predicate using
L- 15-04-24
11 I. Forward Chaining ii. Backward Chaining

Tille of Project Group Number Members Name Section

L-
12
07113702022 Jayant Chaudhary BCA – M2

Q1: Write steps to install Python and required libraries for AI. Write
instructions for setting up a Python virtual environment.
Sol:
Steps to install Python and required libraries for AI
1. Install Python

• Go to the official Python website (https://www.python.org/) and download the

latest version of Python.
• Follow the installation instructions for your operating system (Windows, macOS,
or Linux).

2. Set Up Environment (Optional):

• Consider setting up a virtual environment using virtualenv or conda to manage

dependencies for your projects. This step is optional but recommended for better project
isolation.

3. Install Required Libraries

• Here are some commonly used libraries for AI development and their installation
commands:
- NumPy: For numerical computing
pip install numpy

- Pandas: For data manipulation and analysis

pip install pandas

- Matplotlib: For data visualization

pip install matplotlib

- Scikit-learn: For machine learning algorithms and tools

pip install scikit-learn

1
07113702022 Jayant Chaudhary BCA – M2

- TensorFlow or PyTorch: For deep learning

• For TensorFlow:

pip install tensorflow

• For PyTorch (with CUDA support):

pip install torch torchvision torchaudio cudatoolkit=xx.x -c pytorch

Replace `xx.x` with the version of CUDA installed on your system.

- Keras: High-level neural networks API (usually used with TensorFlow or Theano)
pip install keras

- OpenCV: For computer vision tasks

pip install opencv-python

- Natural Language Toolkit (NLTK)*: For natural language processing

pip install nltk

- Jupyter Notebook (Optional): For interactive development and data visualization

pip install jupyterlab

4. Verify Installations

• After installing the libraries, it's a good idea to verify that they were
installed correctly. You can do this by importing them in a Python script or
in a Jupyter Notebook and running some basic commands.

2
07113702022 Jayant Chaudhary BCA – M2

• That's it! You should now have Python installed along with some essential
libraries for AI development. Remember that the specific libraries you need
may vary depending on your project requirements.

Instructions for setting up a Python virtual environment:

1. Install virtualenv (if not already installed):
• Open a terminal or command prompt.
• Install virtualenv using pip (Python's package installer) with the
following command:

pip install virtualenv

2. Create a Virtual Environment:

• Choose or create a directory where you want to store your virtual
environments. Navigate to this directory in your terminal or command
prompt.
• Create a new virtual environment using the `virtualenv` command followed by
the name of your environment. For example:

virtualenv myenv

• Replace `myenv` with the desired name for your virtual environment.

3. Activate the Virtual Environment:

• Once the virtual environment is created, you need to activate it.
• On Windows:
myenv\Scripts\activate

• On macOS and Linux:

source myenv/bin/activate

• After activation, you should see the name of your virtual environment in
the terminal or command prompt prompt.

4. Install Dependencies:

3
07113702022 Jayant Chaudhary BCA – M2

• While your virtual environment is active, you can install Python packages just like you
pip install numpy pandas matplotlib

would in a global Python environment using `pip`. For example:

5. Deactivate the Virtual Environment:

• To deactivate the virtual environment and return to your global
Python environment, simply run:

deactivate

6. Use the Virtual Environment:

• Whenever you work on a project, activate the corresponding virtual environment
first. This ensures that you're using the correct set of dependencies for that
project.

7. (Optional) Delete the Virtual Environment:

• If you no longer need a virtual environment, you can simply delete its
directory. Be cautious as this will also remove all installed packages within
that environment.

4
07113702022 Jayant Chaudhary BCA – M2

5
07113702022 Jayant Chaudhary BCA – M2

Q2: Write a program to implement Breadth First Search and Depth First
Search.
Source Code:
from collections 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] * (len(self.graph))
queue = []
queue.append(start)
visited[start] = True
while queue:
start = queue.pop(0)
print(start, end=" ")
for i in self.graph[start]:
if not visited[i]:
queue.append(i)
visited[i] = True
def dfs_util(self, v, visited):
visited[v] = True
print(v, end=" ")
for i in self.graph[v]:
if not visited[i]:
self.dfs_util(i, visited)
def dfs(self, start):
visited = [False] * (len(self.graph))
self.dfs_util(start, visited)
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
print("Breadth First Search:")
g.bfs(2)
print("\nDepth First Search:")
g.dfs(2)

6
07113702022 Jayant Chaudhary BCA – M2

Output:

7
07113702022 Jayant Chaudhary BCA – M2

Q3: Write a program for Best First Search and A* Search Algorithm.
Source Code:
Best First Search:
from queue import PriorityQueue
v = 14
graph = [[] for i in range(v)]
def best_first_search(actual_Src, target, n):
visited = [False] * n
pq = PriorityQueue()
pq.put((0, actual_Src))
visited[actual_Src] = True
while pq.empty() == False:
u = pq.get()[1]
print(u, end=" ")
if u == target:
break
for v, c in graph[u]:
if visited[v] == False:
visited[v] = True
pq.put((c, v))
print()
def addedge(x, y, cost):
graph[x].append((y, cost))
graph[y].append((x, cost))
addedge(0, 1, 3)
addedge(0, 2, 6)
addedge(0, 3, 5)
addedge(1, 4, 9)
addedge(1, 5, 8)
addedge(2, 6, 12)
addedge(2, 7, 14)
addedge(3, 8, 7)
addedge(8, 9, 5)
addedge(8, 10, 6)
addedge(9, 11, 1)
addedge(9, 12, 10)
addedge(9, 13, 2)
source = 0
target = 9
best_first_search(source, target, v)

8
07113702022 Jayant Chaudhary BCA – M2

Output:

A* Search Algorithm:
import heapq
class Graph:
def init (self):
self.graph = {}
def add_edge(self, u, v, w):
if u in self.graph:
self.graph[u].append((v, w))
else:
self.graph[u] = [(v, w)]
def astar_search(self, start, goal):
pq = [(0, start)]
visited = set()
while pq:
f_cost, current = heapq.heappop(pq)
if current == goal:
return True
if current not in visited:
visited.add(current)
for neighbor, weight in self.graph[current]:
if neighbor not in visited:
heapq.heappush(pq, (f_cost + weight + self.heuristic(neighbor, goal), neighbor))
return False
def heuristic(self, u, v):
x1, y1 = u
x2, y2 = v
return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
g = Graph()
g.add_edge((0, 0), (1, 0), 1)
g.add_edge((1, 0), (2, 0), 1)
g.add_edge((1, 1), (2, 1), 1)
g.add_edge((2, 0), (2, 1), 1)
g.add_edge((2, 1), (2, 2), 1)
start = (0, 0)
goal = (2, 2)

9
07113702022 Jayant Chaudhary BCA – M2

print("A* Search Path Found:", g.astar_search(start, goal))

print("\n --> Finally checking the goal path has been found: ",g.astar_search(start,goal))

Output:

10
07113702022 Jayant Chaudhary BCA – M2

Q4: Write a program to solve the Water Jug Problem.

Source Code:
from collections import defaultdict
jug1, jug2, aim = 4, 3, 2
visited = defaultdict(lambda: False)
def waterJugSolver(amt1, amt2):
if (amt1 == aim and amt2 == 0) or (amt2 == aim and amt1 == 0):
print(amt1, amt2)
return True
if visited[(amt1, amt2)] == False:
print(amt1, amt2)
visited[(amt1, amt2)] = True
return (waterJugSolver(0, amt2) or
waterJugSolver(amt1, 0) or
waterJugSolver(jug1, amt2) or
waterJugSolver(amt1, jug2) or
waterJugSolver(amt1 + min(amt2, (jug1-amt1)),
amt2 - min(amt2, (jug1-amt1))) or
waterJugSolver(amt1 - min(amt1, (jug2-amt2)),
amt2 + min(amt1, (jug2-amt2))))
else:
return False
print("Steps: ")
waterJugSolver(0, 0)

Output:

11
07113702022 Jayant Chaudhary BCA – M2

Q5: Write a program to solve the 4-Queen Problem.

Source Code:
N=4
ld = [0] * 30
rd = [0] * 30
cl = [0] * 30
def printSolution(board):
for i in range(N):
for j in range(N):
print(" Q " if board[i][j] == 1 else " . ", end="")
print()
def solveNQUtil(board, col):
if col >= N:
return True
for i in range(N):
if (ld[i - col + N - 1] != 1 and rd[i + col] != 1) and cl[i] != 1:
board[i][col] = 1
ld[i - col + N - 1] = rd[i + col] = cl[i] = 1
if solveNQUtil(board, col + 1):
return True
board[i][col] = 0 # BACKTRACK
ld[i - col + N - 1] = rd[i + col] = cl[i] = 0
return False
def solveNQ():
board = [[0 for _ in range(N)] for _ in range(N)]
if not solveNQUtil(board, 0):
print("Solution does not exist")
return False
printSolution(board)
return True
if name == " main ":
solveNQ()
Output:

12
07113702022 Jayant Chaudhary BCA – M2

Q6: Write a program to implement AO* Algorithm.

Source Code:
def Cost(H, condition, weight = 1):
cost = {}
if 'AND' in condition:
AND_nodes = condition['AND']
Path_A = ' AND '.join(AND_nodes)
PathA = sum(H[node]+weight for node in AND_nodes)
cost[Path_A] = PathA
if 'OR' in condition:
OR_nodes = condition['OR']
Path_B =' OR '.join(OR_nodes)
PathB = min(H[node]+weight for node in OR_nodes)
cost[Path_B] = PathB
return cost
def update_cost(H, Conditions, weight=1):
Main_nodes = list(Conditions.keys())
Main_nodes.reverse()
least_cost= {}
for key in Main_nodes:
condition = Conditions[key]
print(key,':', Conditions[key],'>>>', Cost(H, condition, weight))
c = Cost(H, condition, weight)
H[key] = min(c.values())
least_cost[key] = Cost(H, condition, weight)
return least_cost
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)
Next = key[Index].split()
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]

13
07113702022 Jayant Chaudhary BCA – M2

Path += shortest_path(Start, Updated_cost, H) + ']'

return Path
H = {'A': -1, 'B': 5, 'C': 2, 'D': 4, 'E': 7, 'F': 9, 'G': 3, 'H': 0, 'I':0, 'J':0}
Conditions = {
'A': {'OR': ['B'], 'AND': ['C', 'D']},
'B': {'OR': ['E', 'F']},
'C': {'OR': ['G'], 'AND': ['H', 'I']},
'D': {'OR': ['J']}
}
weight = 1
print('Updated Cost :')
Updated_cost = update_cost(H, Conditions, weight=1)
print('*'*75)
print('Shortest Path :\n',shortest_path('A', Updated_cost,H))

Output:

14
07113702022 Jayant Chaudhary BCA – M2

Q7: Write a program to implement Hill Climbing and Steepest Ascent Hill
Climbing Algorithm.
Source Code:
Hill Climbing Algorithm:
import random
def hill_climbing(problem, max_iterations=1000):
current_solution = problem.random_solution()
current_value = problem.evaluate(current_solution)
for _ in range(max_iterations):
neighbors = problem.get_neighbors(current_solution)
next_solution = max(neighbors, key=lambda x: problem.evaluate(x))
next_value = problem.evaluate(next_solution)
if next_value <= current_value:
break
current_solution = next_solution
current_value = next_value
return current_solution
class OptimizationProblem:
def random_solution(self):
return [random.uniform(0, 10), random.uniform(0, 10)]
def evaluate(self, solution):
x, y = solution
return -((x - 5) ** 2 + (y - 5) ** 2)
def get_neighbors(self, solution):
x, y= solution
neighbors = [
[x + random.uniform(-1, 1), y + random.uniform(-1, 1)] for _ in range(10)
]
return neighbors
problem = OptimizationProblem()
best_solution = hill_climbing(problem)
print("--> Best Solution:", best_solution)
print("--> Best Value:", problem.evaluate(best_solution))
Output:

15
07113702022 Jayant Chaudhary BCA – M2

Steepest Ascent Hill Climbing:

import random
defobjective_function(x):
return -(x ** 2)
def neighbor(x, step_size=0.1):
return x + random.uniform(-step_size, step_size)
def steepest_ascent_hill_climbing(max_iter=100, step_size=0.1):
current_solution = random.uniform(-10, 10)
current_value = objective_function(current_solution)
for _ in range(max_iter):
next_solution = neighbor(current_solution, step_size)
next_value = objective_function(next_solution)
if next_value > current_value:
current_solution = next_solution
current_value = next_value
return current_solution, current_value
best_solution, best_value = steepest_ascent_hill_climbing()
print("Best solution:", best_solution)
print("Objective value at best solution:", best_value)

Output:

16
07113702022 Jayant Chaudhary BCA – M2

Q8: Write a program to solve the Travelling Salesman Problem.

Source Code:
import itertools
class TSP:
def init (self, cities):
self.cities = cities
self.num_cities = len(cities)
self.min_distance = float('inf')
self.best_path = None
def calculate_distance(self, path):
total_distance = 0
for i in range(self.num_cities - 1):
total_distance += self.distance(path[i], path[i + 1])
total_distance += self.distance(path[-1], path[0])
return total_distance
def distance(self, city1, city2):
x1, y1 = city1
x2, y2 = city2
return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
def solve(self):
for perm in itertools.permutations(self.cities):
distance = self.calculate_distance(perm)
if distance < self.min_distance:
self.min_distance = distance
self.best_path = perm
return self.min_distance, self.best_path
cities = [(0, 0), (1, 2), (3, 1), (2, 3)]
tsp = TSP(cities)
min_distance, best_path = tsp.solve()
print("\n --> Minimum Distance:", min_distance)
print("\n --> Best Path:", best_path)
Output:

17
07113702022 Jayant Chaudhary BCA – M2

Q9: Write a program for list operations (Nested List, Length, Concatenation,
Membership, Iteration, Indexing, and Slicing).
Source Code:
nested_list = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print("-> 1. Nested List:", nested_list)
print("-> 2. Length of the nested list:", len(nested_list))
list1 = [1, 2, 3]
list2 = [4, 5, 6]
concatenated_list = list1 + list2
print("-> 3. Concatenated list:", concatenated_list)
element = 3
if element in concatenated_list:
print(f"-> {element} is present in the concatenated list")
else:
print(f"-> {element} is not present in the concatenated list")
print("-> 5. Iterating through the concatenated list: ")
for item in concatenated_list:
print("\t",item,end = " ")
index = 2
print("\n-> 6. Element at index", index, ":", concatenated_list[index])
start_index = 1
end_index = 4
print("-> 7. Sliced list from index", start_index, "to", end_index, ":",
concatenated_list[start_index:end_index])

Output:

18
07113702022 Jayant Chaudhary BCA – M2

Q10: Write a program for list methods (Add, Append, Extend & Delete).
Source Code:
my_list = [1, 2, 3]
my_list.append(4)
print("-> After appending 4:", my_list)
another_list = [5, 6, 7]
my_list.extend(another_list)
print("-> After extending by [5, 6, 7]:", my_list)
my_list.insert(2, 8)
print("-> After inserting 8 at index 2:", my_list)
my_list.remove(3)
print("-> After removing 3:", my_list)
del my_list[1]
print("-> After deleting element at index 1:", my_list)

Output:

19
07113702022 Jayant Chaudhary BCA – M2

Q11: Write a program to implement First Order Predicate using:

i. Forward Chaining
ii. Backward Chaining
Source Code:
(i) Forward Chaining
class Rule:
def init (self, conclusion, premises):
self.conclusion = conclusion
self.premises = premises
class KnowledgeBase:
def init (self):
self.facts = set()
self.rules = []
def add_fact(self, fact):
self.facts.add(fact)
def add_rule(self, rule):
self.rules.append(rule)
def forward_chaining(self):
inferred_facts = set()
while True:
new_inferences = False
for rule in self.rules:
if all(premise in inferred_facts or premise in self.facts for premise in rule.premises) \
and rule.conclusion not in self.facts:
self.facts.add(rule.conclusion)
inferred_facts.add(rule.conclusion)
new_inferences = True
if not new_inferences:
break
def print_facts(self):
print("--> Facts: ")
for fact in self.facts:
print(fact)
kb = KnowledgeBase()
kb.add_fact("-> human(socrates)")
kb.add_fact("-> mortal(socrates)")
kb.add_rule(Rule("\n -> mortal(?x)", ["human(?x)"]))
kb.forward_chaining()
kb.print_facts()

20
07113702022 Jayant Chaudhary BCA – M2

Output:

(ii) Backward Chaining

class Rule:
def init (self, conclusion, premises):
self.conclusion = conclusion
self.premises = premises
class KnowledgeBase:
def init (self):
self.rules = []
def add_rule(self, rule):
self.rules.append(rule)
def backward_chaining(self, goal, facts):
if goal in facts:
return True
for rule in self.rules:
if rule.conclusion == goal:
if all(self.backward_chaining(premise, facts) for premise in rule.premises):
return True
return False
kb = KnowledgeBase()
kb.add_rule(Rule("\n -> mortal(?x)", ["human(?x)"]))
facts = {"\n -> human(socrates)"}
goal = "mortal(socrates)"
result = kb.backward_chaining(goal, facts)
if result:
print(f"-> {goal} can be inferred fromthe given facts and rules.")
else:
print(f"-> {goal} cannot be inferred from the given facts and rules.")
Output:

21