SL-1 lab practical
Practical book for an Ai
Ai Codes .....
Q1.
from collections import deque
# -------------------------------
# Undirected Graph Representation
# -------------------------------
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# -------------------------------
# Depth First Search (Recursive)
# -------------------------------
def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node, end=" ")
for neighbour in graph[node]:
if neighbour not in visited:
dfs_recursive(graph, neighbour, visited)
# -------------------------------
# Breadth First Search (Iterative)
# -------------------------------
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=" ")
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
# -------------------------------
# Driver Code
# -------------------------------
print("DFS Traversal (Recursive):")
dfs_recursive(graph, 'A')
print("\nBFS Traversal:")
bfs(graph, 'A')
Q2.
import heapq
# -------------------------------
# A* Search Algorithm
# -------------------------------
def a_star_search(grid, start, goal):
rows, cols = len(grid), len(grid[0])
# 4-directional movement (up, down, left, right)
directions = [(0,1), (1,0), (0,-1), (-1,0)]
# Heuristic: Manhattan distance
def heuristic(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
# Priority queue (f, g, position, path)
open_list = []
heapq.heappush(open_list, (heuristic(start, goal), 0, start, [start]))
visited = set()
while open_list:
f, g, current, path = heapq.heappop(open_list)
if current == goal:
return path # Path found!
if current in visited:
continue
visited.add(current)
for dx, dy in directions:
nx, ny = current[0] + dx, current[1] + dy
neighbor = (nx, ny)
if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 0:
if neighbor not in visited:
g_new = g + 1
f_new = g_new + heuristic(neighbor, goal)
heapq.heappush(open_list, (f_new, g_new, neighbor, path + [neighbor]))
return None # No path found
# -------------------------------
# Example Grid for a Game Map
# -------------------------------
# 0 = free cell, 1 = obstacle
grid = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 0, 0]
]
start = (0, 0) # Starting position
goal = (4, 4) # Goal position
# -------------------------------
# Run A* Search
# -------------------------------
path = a_star_search(grid, start, goal)
# -------------------------------
# Display Result
# -------------------------------
if path:
print("Shortest Path Found by A*:")
print(path)
else:
print("No path found!")
Q3.
# -------------------------------
# N-Queens using Backtracking
# -------------------------------
def is_safe(board, row, col, n):
# Check column
for i in range(row):
if board[i][col] == 1:
return False
# Check upper-left diagonal
i, j = row, col
while i >= 0 and j >= 0:
if board[i][j] == 1:
return False
i -= 1
j -= 1
# Check upper-right diagonal
i, j = row, col
while i >= 0 and j < n:
if board[i][j] == 1:
return False
i -= 1
j += 1
return True
def solve_n_queens_backtracking(board, row, n):
if row == n:
print_solution(board, n)
return True
res = False
for col in range(n):
if is_safe(board, row, col, n):
board[row][col] = 1
res = solve_n_queens_backtracking(board, row + 1, n) or res
board[row][col] = 0 # backtrack
return res
def print_solution(board, n):
for i in range(n):
for j in range(n):
print("Q" if board[i][j] == 1 else ".", end=" ")
print()
print("\n")
# -------------------------------
# Driver Code
# -------------------------------
n = 4
board = [[0] * n for _ in range(n)]
print("Solutions using Backtracking:")
solve_n_queens_backtracking(board, 0, n)
Q4.
import math
def alpha_beta(node, depth, is_max, values, alpha, beta, max_depth):
if depth == max_depth:
return values[node]
if is_max:
best = -math.inf
for i in range(2):
val = alpha_beta(node * 2 + i, depth + 1, False, values, alpha, beta, max_depth)
best = max(best, val)
alpha = max(alpha, best)
if beta <= alpha: # prune
break
return best
else:
best = math.inf
for i in range(2):
val = alpha_beta(node * 2 + i, depth + 1, True, values, alpha, beta, max_depth)
best = min(best, val)
beta = min(beta, best)
if beta <= alpha: # prune
break
return best
# Example game tree (depth = 3)
values = [3, 5, 6, 9, 1, 2, 0, -1]
max_depth = 3
best_val = alpha_beta(0, 0, True, values, -math.inf, math.inf, max_depth)
print("Best value for maximizing player:", best_val)
Q5.
user = input("You: ").lower()
if "hello" in user or "hi" in user:
print("Chatbot: Hello! How can I help you?")
elif "price" in user:
print("Chatbot: Our products start from ₹499.")
elif "order" in user:
print("Chatbot: You can place your order online.")
elif "refund" in user:
print("Chatbot: Refunds are processed within 5 days.")
elif "thanks" in user or "thank you" in user:
print("Chatbot: You're welcome!")
else:
print("Chatbot: Sorry, I didn’t understand that.")
Q6.
import sys
# ----------------------------------------
# Prim's Algorithm for MST (Greedy Search)
# ----------------------------------------
def prim_mst(graph):
num_vertices = len(graph)
selected = [False] * num_vertices
no_of_edges = 0
selected[0] = True # start from first vertex
print("Edge : Weight")
while no_of_edges < num_vertices - 1:
minimum = sys.maxsize
x = 0
y = 0
for i in range(num_vertices):
if selected[i]:
for j in range(num_vertices):
if (not selected[j]) and graph[i][j]:
if minimum > graph[i][j]:
minimum = graph[i][j]
x, y = i, j
print(f"{x} - {y} : {graph[x][y]}")
selected[y] = True
no_of_edges += 1
# ----------------------------------------
# Example Graph (Adjacency Matrix)
# ----------------------------------------
graph = [
[0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0]
]
# Run Prim's Algorithm
prim_mst(graph)
Practical code for an DBMS
Comments
Post a Comment