A PRACTICAL FILE
OF
Artificial Intelligence
Submitted in partial fulfillment for the award of Degree Of
MASTER OF COMPUTER APPLICATIONS
SUBMITTED TO :
SUBMITTED BY:
Dr. MONIK Anshul
Ms. SABHYA 25/MCA/108
MCA 2st Semester
Department of Computer Science & Application
Kurukshetra University, Kurukshetra
Session : 2025-27
1. A* Search Algorithm Heuristic-guided search; minimize f(n) = g(n)+h(n) to find optimal
paths efficiently.
graph = {
'A': {'B': 1, 'C': 3},
'B': {'D': 3, 'E': 1},
'C': {'F': 5},
'D': {},
'E': {'F': 1},
'F': {}
}
heuristic = {
'A': 6,
'B': 4,
'C': 4,
'D': 2,
'E': 1,
'F': 0
}
def a_star(start, goal):
open_list = [start]
closed_list = []
g = {start: 0}
parent = {start: None}
while open_list:
current = min(open_list, key=lambda x: g[x] + heuristic[x])
if current == goal:
path = []
while current:
[Link](current)
current = parent[current]
return path[::-1]
open_list.remove(current)
closed_list.append(current)
for neighbor, cost in graph[current].items():
if neighbor in closed_list:
continue
new_g = g[current] + cost
if neighbor not in open_list:
open_list.append(neighbor)
elif new_g >= [Link](neighbor, float('inf')):
continue
g[neighbor] = new_g
parent[neighbor] = current
return None
path = a_star('A', 'F')
print("Shortest Path:", path)
Output:
2. Greedy Best-First Search Use only heuristic h(n) to expand nodes; faster but not
guaranteed optimal.
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
heuristic = {
'A': 6,
'B': 4,
'C': 3,
'D': 2,
'E': 1,
'F': 0
}
def greedy_bfs(start, goal):
open_list = [start]
visited = []
parent = {start: None}
while open_list:
current = min(open_list, key=lambda x: heuristic[x])
if current == goal:
path = []
while current:
[Link](current)
current = parent[current]
return path[::-1]
open_list.remove(current)
[Link](current)
for neighbor in graph[current]:
if neighbor not in visited and neighbor not in open_list:
open_list.append(neighbor)
parent[neighbor] = current
return None
path = greedy_bfs('A', 'F')
print("Path:", path)
Output:
3. Hill Climbing Local search that moves to the best neighbouring state; illustrates local
optima problem.
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
heuristic = {
'A': 6,
'B': 4,
'C': 5,
'D': 3,
'E': 2,
'F': 0
}
def hill_climbing(start, goal):
current = start
path = [current]
while current != goal:
neighbors = graph[current]
if not neighbors:
break
next_node = min(neighbors, key=lambda x: heuristic[x])
if heuristic[next_node] >= heuristic[current]:
break
current = next_node
[Link](current)
return path
path = hill_climbing('A', 'F')
print("Path:", path)
Output:
4. Minimax with Alpha-Beta Pruning Adversarial search for two-player games; prune
branches that can't affect the outcome.
def minimax(depth, node, isMax, values, alpha, beta):
if depth == 3:
return values[node]
if isMax:
best = -1000
for i in range(2):
val = minimax(depth + 1, node * 2 + i, False, values, alpha, beta)
best = max(best, val)
alpha = max(alpha, best)
if beta <= alpha:
break
return best
else:
best = 1000
for i in range(2):
val = minimax(depth + 1, node * 2 + i, True, values, alpha, beta)
best = min(best, val)
beta = min(beta, best)
if beta <= alpha:
break
return best
values = [3, 5, 6, 9, 1, 2, 0, -1]
result = minimax(0, 0, True, values, -1000, 1000)
print("Optimal Value:", result)
Output:
5. Travelling Salesman Problem — GA Apply Genetic Algorithm to find near-optimal tour
through cities; benchmark population strategies.
import random
cities = {
'A': (0, 0),
'B': (2, 6),
'C': (3, 1),
'D': (5, 5),
'E': (8, 3)
}
def distance(c1, c2):
return ((c1[0] - c2[0])**2 + (c1[1] - c2[1])**2) ** 0.5
def total_distance(route):
dist = 0
for i in range(len(route)):
dist += distance(cities[route[i]], cities[route[(i + 1) % len(route)]])
return dist
def fitness(route):
return 1 / total_distance(route)
def create_population(size):
population = []
for _ in range(size):
route = list([Link]())
[Link](route)
[Link](route)
return population
def selection(population):
[Link](key=lambda x: fitness(x), reverse=True)
return population[:2]
def crossover(p1, p2):
start, end = sorted([Link](range(len(p1)), 2))
child = p1[start:end]
for gene in p2:
if gene not in child:
[Link](gene)
return child
def mutate(route):
i, j = [Link](range(len(route)), 2)
route[i], route[j] = route[j], route[i]
def genetic_algorithm(generations=50, pop_size=10):
population = create_population(pop_size)
for _ in range(generations):
parents = selection(population)
new_population = [Link]()
while len(new_population) < pop_size:
child = crossover(parents[0], parents[1])
mutate(child)
new_population.append(child)
population = new_population
best = max(population, key=lambda x: fitness(x))
return best, total_distance(best)
best_route, best_dist = genetic_algorithm()
print("Best Route:", best_route)
print("Distance:", best_dist)
Output:
6. 8-Puzzle / 15-Puzzle Solver Classic state-space problem solved with A*, BFS, and IDA*;
compare time and space complexity.
import heapq
goal = [[1,2,3],[4,5,6],[7,8,0]]
def heuristic(state):
count = 0
for i in range(3):
for j in range(3):
if state[i][j] != 0 and state[i][j] != goal[i][j]:
count += 1
return count
def find_zero(state):
for i in range(3):
for j in range(3):
if state[i][j] == 0:
return i, j
def neighbors(state):
x, y = find_zero(state)
moves = [(0,1),(1,0),(0,-1),(-1,0)]
result = []
for dx, dy in moves:
nx, ny = x+dx, y+dy
if 0 <= nx < 3 and 0 <= ny < 3:
new_state = [row[:] for row in state]
new_state[x][y], new_state[nx][ny] = new_state[nx][ny],
new_state[x][y]
[Link](new_state)
return result
def a_star(start):
pq = []
[Link](pq, (heuristic(start), 0, start, []))
visited = []
while pq:
f, g, state, path = [Link](pq)
if state == goal:
return path + [state]
[Link](state)
for n in neighbors(state):
if n not in visited:
[Link](pq, (g+1+heuristic(n), g+1, n, path +
[state]))
return None
start = [[1,2,3],[4,0,6],[7,5,8]]
solution = a_star(start)
for step in solution:
for row in step:
print(row)
print()
Output:
7. Decision Tree, Build a decision tree using information gain; visualise splits and classify
test samples
from [Link] import DecisionTreeClassifier
from sklearn import tree
X=[
[0, 0],
[0, 1],
[1, 0],
[1, 1]
]
y = [0, 1, 1, 0] # Labels
model = DecisionTreeClassifier(criterion="entropy")
[Link](X, y)
prediction = [Link]([[1, 0]])
print("Prediction:", prediction)
tree.plot_tree(model, filled=True)
Output:
8. Formulate a state-space representation for the "8-puzzle problem." Represent states,
actions, and transitions clearly and define the goal state.
start = [[2,8,3],
[1,6,4],
[7,0,5]]
goal = [[1,2,3],
[4,5,6],
[7,8,0]]
def print_state(state):
for row in state:
print(row)
print()
def find_blank(state):
for i in range(3):
for j in range(3):
if state[i][j] == 0:
return i, j
def move(state, direction):
x, y = find_blank(state)
new_state = [row[:] for row in state]
if direction == "up" and x > 0:
new_state[x][y], new_state[x-1][y] = new_state[x-1][y],
new_state[x][y]
elif direction == "down" and x < 2:
new_state[x][y], new_state[x+1][y] = new_state[x+1][y],
new_state[x][y]
elif direction == "left" and y > 0:
new_state[x][y], new_state[x][y-1] = new_state[x][y-1],
new_state[x][y]
elif direction == "right" and y < 2:
new_state[x][y], new_state[x][y+1] = new_state[x][y+1],
new_state[x][y]
else:
return None
return new_state
print("Initial State:")
print_state(start)
print("Goal State:")
print_state(goal)
print("Possible Moves from Initial State:\n")
for d in ["up", "down", "left", "right"]:
new = move(start, d)
if new:
print("Move:", d)
print_state(new)
Output:
9. Implement Breadth-First Search (BFS) to solve a maze where the start and goal
positions are specified.
from collections import deque
maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 1, 0]
]
start = (0, 0)
goal = (4, 4)
rows = len(maze)
cols = len(maze[0])
def bfs(start, goal):
queue = deque([(start, [start])])
visited = set()
while queue:
(x, y), path = [Link]()
if (x, y) == goal:
return path
if (x, y) in visited:
continue
[Link]((x, y))
moves = [(0,1), (1,0), (0,-1), (-1,0)]
for dx, dy in moves:
nx, ny = x + dx, y + dy
if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == 0:
[Link](((nx, ny), path + [(nx, ny)]))
return None
path = bfs(start, goal)
print("Path:", path)
Output:
10. Use Depth-First Search (DFS) to navigate through a graph of cities and find a path
from a given source to a destination
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
def dfs(current, goal, visited, path):
[Link](current)
[Link](current)
if current == goal:
return path
for neighbor in graph[current]:
if neighbor not in visited:
result = dfs(neighbor, goal, visited, path)
if result:
return result
[Link]()
return None
start = 'A'
goal = 'F'
path = dfs(start, goal, set(), [])
print("Path:", path)
Output:
11. Apply Iterative Deepening DFS to solve a water-jug problem (e.g., measure exactly 4
liters using a 3-liter and a 5-liter jug).
def is_goal(state):
return state[0] == 4 or state[1] == 4
def get_moves(state):
x, y = state
moves = []
[Link]((3, y))
[Link]((x, 5))
[Link]((0, y))
[Link]((x, 0))
pour = min(x, 5 - y)
[Link]((x - pour, y + pour))
pour = min(y, 3 - x)
[Link]((x + pour, y - pour))
return moves
def dls(state, depth, visited):
if is_goal(state):
return [state]
if depth == 0:
return None
[Link](state)
for move in get_moves(state):
if move not in visited:
result = dls(move, depth - 1, visited)
if result:
return [state] + result
return None
def iddfs(start, max_depth):
for depth in range(max_depth):
visited = set()
result = dls(start, depth, visited)
if result:
return result
return None
start = (0, 0)
solution = iddfs(start, 10)
print("Solution Path:")
for step in solution:
print(step)
Output:
12. Develop a production system to solve the "Tower of Hanoi" problem.
def hanoi(n, source, auxiliary, destination):
if n == 1:
print(f"Move disk 1 from {source} to {destination}")
return
hanoi(n-1, source, destination, auxiliary)
print(f"Move disk {n} from {source} to {destination}")
hanoi(n-1, auxiliary, source, destination)
n=3
hanoi(n, 'A', 'B', 'C')
Output:
13. Write a program to implement a Genetic Algorithm to maximize a mathematical
function (e.g., f(x)=x2,0≤x≤31). Demonstrate the use of binary encoding for
chromosomes
import random
def decode(chrom):
return int(chrom, 2)
def fitness(chrom):
x = decode(chrom)
return x * x
def random_chrom():
return ''.join([Link]('01') for _ in range(5))
def selection(pop):
[Link](key=lambda x: fitness(x), reverse=True)
return pop[:2]
def crossover(p1, p2):
point = [Link](1, 4)
c1 = p1[:point] + p2[point:]
c2 = p2[:point] + p1[point:]
return c1, c2
def mutation(chrom):
i = [Link](0, 4)
chrom = list(chrom)
chrom[i] = '1' if chrom[i] == '0' else '0'
return ''.join(chrom)
population = [random_chrom() for _ in range(6)]
for _ in range(10):
parents = selection(population)
new_pop = parents[:]
while len(new_pop) < 6:
c1, c2 = crossover(parents[0], parents[1])
c1 = mutation(c1)
c2 = mutation(c2)
new_pop.extend([c1, c2])
population = new_pop[:6]
best = max(population, key=lambda x: fitness(x))
print("Best Chromosome:", best)
print("x =", decode(best))
print("Max f(x) =", fitness(best))
Output:
14. Define a fitness function for solving the "Travelling Salesman Problem (TSP)" using a
Genetic Algorithm.
import math
cities = {
'A': (0, 0),
'B': (2, 3),
'C': (5, 2),
'D': (6, 6)
}
def distance(c1, c2):
return [Link]((c1[0]-c2[0])**2 + (c1[1]-c2[1])**2)
def total_distance(route):
dist = 0
for i in range(len(route)):
dist += distance(cities[route[i]], cities[route[(i+1)%len(route)]])
return dist
def fitness(route):
return 1 / total_distance(route)
route = ['A', 'B', 'C', 'D']
print("Distance:", total_distance(route))
print("Fitness:", fitness(route))
Output: