AIML Lab Programs
[Link] a breadth-first search algorithm.
graph = {
'5': ['3', '7'],
'3': ['2', '4'],
'7': ['8'],
'2': [],
'4': ['8'],
'8': []
# BFS function
def bfs(graph, start_node):
visited = []
queue = [start_node]
while queue:
node = [Link](0)
if node not in visited:
[Link](node)
print(node, end=" ")
[Link](graph[node])
print("Following is the Breadth-First Search:")
bfs(graph, '5')
Output:
Following is the Breadth-First Search:
537248
2. Implement a Depth-First search algorithm.
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
if node not in visited:
print(node)
[Link](node)
for neighbour in graph[node]:
dfs(graph, neighbour, visited)
print("Following is the Depth-First Search:")
dfs(graph, 'A')
Output:
Following is the Depth-First Search:
3. Implement Travel salesman problem
from sys import maxsize
from itertools import permutations
v=4
def tsp(graph, start):
vertices = [i for i in range(v) if i != start]
min_cost = maxsize
for path in permutations(vertices):
current_cost = 0
k = start
for j in path:
current_cost += graph[k][j]
k=j
current_cost += graph[k][start]
min_cost = min(min_cost, current_cost)
return min_cost
graph = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
start = 0
print(tsp(graph, start))
Output:
80
4. Implement water jug problem
from collections import deque
def water_jug(a, b, target):
visited = set()
queue = deque([(0, 0)])
path = []
while queue:
x, y = [Link]()
if (x, y) in visited:
continue
[Link]((x, y))
[Link]((x, y))
if x == target or y == target:
if x == target and y != 0:
[Link]((x, 0))
elif y == target and x != 0:
[Link]((0, y))
print("Path from initial to solution state:")
for p in path:
print(f"{p[0]}, {p[1]}")
return
next_states = [
(a, y),
(x, b),
(0, y),
(x, 0),
(x - min(x, b - y), y + min(x, b - y)),
(x + min(y, a - x), y - min(y, a - x))
for s in next_states:
if s not in visited:
[Link](s)
print("No solution possible.")
if __name__ == "__main__":
water_jug(4, 3, 2)
Output:
path from initial state to solution state::
0,0
4,0
0,3
4,3
1,3
3,0
1,0
3,3
0,1
4,2
0,2
5. Implement A* search algorithm
def a_star(start, goal):
open = {start}
closed = set()
cost = {start: 0}
parent = {start: None}
while open:
node = min(open, key=lambda x: cost[x] + h[x])
if node == goal:
path = []
while node:
[Link](node)
node = parent[node]
print("Path found:", path[::-1])
return path[::-1]
for neigh, c in [Link](node, []):
new_cost = cost[node] + c
if neigh not in cost or new_cost < cost[neigh]:
cost[neigh] = new_cost
parent[neigh] = node
[Link](neigh)
[Link](node)
[Link](node)
print("No path found.")
return None
h = {'A':11,'B':6,'C':5,'D':7,'E':3,'F':6,'G':5,'H':3,'I':1,'J':0}
graph = {
'A':[('B',6),('F',3)], 'B':[('C',3),('D',2)],
'C':[('E',5)], 'D':[('E',8)], 'E':[('I',5),('J',5)],
'F':[('G',1),('H',7)], 'G':[('I',3)], 'H':[('I',2)],
'I':[('J',3)], 'J':[]
a_star('A','J')
Output:
path found: ['A', 'F', 'G', 'I', 'J']
6. Implement AO* search algorithm.
def ao_star(H, graph, w=1):
order = list([Link]())[::-1]
updated = {}
for node in order:
cost_paths = {}
if 'AND' in graph[node]:
nodes = graph[node]['AND']
path = ' AND '.join(nodes)
cost_paths[path] = sum(H[n] + w for n in nodes)
if 'OR' in graph[node]:
nodes = graph[node]['OR']
path = ' OR '.join(nodes)
cost_paths[path] = min(H[n] + w for n in nodes)
H[node] = min(cost_paths.values())
updated[node] = cost_paths
print(f"{node}: {graph[node]} >>> {cost_paths}")
return updated
def show_path(start, updated):
path = start
if start in updated:
best = min(updated[start], key=updated[start].get)
parts = [Link]()
if len(parts) == 1:
path += " → " + show_path(parts[0], updated)
else:
path += " → (" + best + ") [" + show_path(parts[0], updated)
path += " + " + show_path(parts[-1], updated) + "]"
return path
H = {'A': -1, 'B': 5, 'C': 2, 'D': 4, 'E': 7, 'F': 9, 'G': 3,
'H': 0, 'I': 0, 'J': 0}
graph = {
'A': {'OR': ['B'], 'AND': ['C', 'D']},
'B': {'OR': ['E', 'F']},
'C': {'OR': ['G'], 'AND': ['H', 'I']},
'D': {'OR': ['J']}
}
print("Updated Costs:")
updated = ao_star(H, graph)
print("\n" + "*" * 50)
print("Shortest Path:\n", show_path('A', updated))
Output:
Updated Cost :
D : {'OR': ['J']} >>> {'J': 1}
C : {'OR': ['G'], 'AND': ['H', 'I']} >>> {'H AND I': 2, 'G': 4}
B : {'OR': ['E', 'F']} >>> {'E OR F': 8}
A : {'OR': ['B'], 'AND': ['C', 'D']} >>> {'C AND D': 5, 'B': 9}
***************************************************************************
Shortest Path :
A <- (C AND D) [C <- (H AND I) [H + I] + D <- J]
7 . Implement and Demonstrate the find-S
algorithm.
Sky AirTemp Humidity Wind Water Forecast EnjoySport
Sunny Warm Normal Strong Warm Same Yes
Sunny Warm High Strong Warm Same Yes
Rainy Cold High Strong Warm Change No
Sunny Warm High Strong Cool Change Yes
import pandas as pd
# Load the CSV data
data = [Link]([
['Sunny', 'Warm', 'Normal', 'Strong', 'Warm', 'Same', 'Yes'],
['Sunny', 'Warm', 'High', 'Strong', 'Warm', 'Same', 'Yes'],
['Rainy', 'Cold', 'High', 'Strong', 'Warm', 'Change', 'No'],
['Sunny', 'Warm', 'High', 'Strong', 'Cool', 'Change', 'Yes']
], columns=['Sky', 'AirTemp', 'Humidity', 'Wind', 'Water', 'Forecast', 'EnjoySport'])
# Step 1: Initialize hypothesis to the first positive example
positive_examples = data[data['EnjoySport'] == 'Yes']
hypothesis = positive_examples.iloc[0, :-1].tolist()
# Step 2: Compare with other positive examples
for i in range(1, len(positive_examples)):
for j in range(len(hypothesis)):
if positive_examples.iloc[i, j] != hypothesis[j]:
hypothesis[j] = '?'
# Step 3: Output final hypothesis
print("Final Specific Hypothesis:", hypothesis)
Output:
Final Specific Hypothesis: ['Sunny', 'Warm', '?', 'Strong',
'?', '?']
8 . Implement and demonstrate the candidate
elimination algorithm
import pandas as pd
import numpy as np
# Step 1: Create dataset
data = [Link]({
'Sky': ['Sunny', 'Sunny', 'Rainy', 'Sunny'],
'AirTemp': ['Warm', 'Warm', 'Cold', 'Warm'],
'Humidity': ['Normal', 'High', 'High', 'High'],
'Wind': ['Strong', 'Strong', 'Strong', 'Strong'],
'Water': ['Warm', 'Warm', 'Warm', 'Cool'],
'Forecast': ['Same', 'Same', 'Change', 'Change'],
'EnjoySport': ['Yes', 'Yes', 'No', 'Yes']
})
# Step 2: Separate features and target
X, Y = [Link][:, :-1].values, [Link][:, -1].values
# Step 3: Initialize S and G
S = X[0].copy()
G = [Link]([['?' for _ in range(len(S))]])
# Step 4: Apply algorithm
for i, val in enumerate(X):
if Y[i] == 'Yes':
for j in range(len(S)):
if val[j] != S[j]:
S[j] = '?'
G = [Link]([g for g in G if all(S[k] == '?' or g[k] == '?' or g[k] == S[k] for k in range(len(S)))])
else:
new_G = []
for j in range(len(S)):
if S[j] != '?' and val[j] != S[j]:
temp = G[0].copy()
temp[j] = S[j]
new_G.append(temp)
G = [Link](new_G)
# Step 5: Output
print("Final General Boundary G = ", [Link]())
print("Final Specific Boundary S = ", [Link]())
9. Demonstrate the working of decision tree based on ID3
algorithm.
Outlook Temperature Humidity Wind PlayTennis
Sunny Hot High Weak No
Sunny Hot High Strong No
Overcast Hot High Weak Yes
Rain Mild Normal Weak Yes
Rain Cool Normal Weak Yes
Rain Cool High Strong Yes
Overcast Cool Normal Strong No
Sunny Mild Normal Weak Yes
Sunny Cool High Weak Yes
Rain Mild Normal Weak Yes
Sunny Mild Normal Strong Yes
Overcast Mild High Strong Yes
Overcast Hot Normal Weak Yes
Rain Mild High Strong No
import pandas as pd
from [Link] import DecisionTreeClassifier
from [Link] import LabelEncoder
from [Link] import accuracy_score
# Dataset
data = [Link]({
'Outlook': ['Sunny', 'Sunny', 'Overcast', 'Rain', 'Rain', 'Rain', 'Overcast',
'Sunny', 'Sunny', 'Rain', 'Sunny', 'Overcast', 'Overcast', 'Rain'],
'Temperature': ['Hot', 'Hot', 'Hot', 'Mild', 'Cool', 'Cool', 'Cool',
'Mild', 'Cool', 'Mild', 'Mild', 'Mild', 'Hot', 'Mild'],
'Humidity': ['High', 'High', 'High', 'Normal', 'Normal', 'High', 'Normal',
'Normal', 'High', 'Normal', 'Normal', 'High', 'Normal', 'High'],
'Wind': ['Weak', 'Strong', 'Weak', 'Weak', 'Weak', 'Strong', 'Strong',
'Weak', 'Weak', 'Weak', 'Strong', 'Strong', 'Weak', 'Strong'],
'PlayTennis': ['No', 'No', 'Yes', 'Yes', 'Yes', 'Yes', 'No',
'Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'No']
})
# Encode categorical columns
le = LabelEncoder()
encoded = [Link](le.fit_transform)
# Split features and target
X, y = [Link][:, :-1], [Link][:, -1]
# Train ID3 decision tree
model = DecisionTreeClassifier(criterion='entropy')
[Link](X, y)
# Predict and print only accuracy
print("accuracy:", accuracy_score(y, [Link](X)))
Output:
accuracy: 1.0