AI LAB PROGRAMS
3.Write a program to find the solution for travelling salesman problem
AIM : To write a program to find the solution for travelling
salesman problem
DESCRIPTION :
Travelling Salesman Problem (TSP) : Given a set of cities and distances between every
pair of cities, the problem is to find the shortest possible route that visits every city exactly
once and returns to the starting point.
Note the difference between Hamiltonian Cycle and TSP. The Hamiltonian cycle problem
is to find if there exists a tour that visits every city exactly once. Here we know that
Hamiltonian Tour exists (because the graph is complete) and in fact, many such tours
exist, the problem is to find a minimum weight Hamiltonian Cycle.
For example, consider the graph shown in the figure on the right side. A TSP tour in the
graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80.
The problem is a famous NP-hard problem. There is no polynomial-time known solution for
this problem.
Examples:
Output of Given Graph:
minimum weight Hamiltonian Cycle :
10 + 25 + 30 + 15 := 80
In this post, the implementation of a simple solution is discussed.
1. Consider city 1 as the starting and ending point. Since the route is cyclic, we
can consider any point as a starting point.
2. Generate all (n-1)! permutations of cities.
3. Calculate the cost of every permutation and keep track of the minimum cost
permutation.
4. Return the permutation with minimum cost.
SOURCE CODE:
# Python3 program to implement traveling salesman
# problem using naive approach.
from sys import maxsize
from itertools import permutations
V=4
def travellingSalesmanProblem(graph, s):
vertex = []
for i in range(V):
if i != s:
vertex.append(i)
# store minimum weight Hamiltonian Cycle
min_path = maxsize
next_permutation=permutations(vertex)
for i in next_permutation:
current_pathweight = 0
k=s
for j in i:
current_pathweight += graph[k][j]
k=j
current_pathweight += graph[k][s]
# update minimum
min_path = min(min_path, current_pathweight)
return min_path
if __name__ == "__main__":
# matrix representation of graph
size = int(input("Enter number of levels : "))
print(f"Enter{size**2} elements to construct a graph")
list1 = []
sub = []
for iin range(size):
sub = []
for j in range(size):
sub.append(int(input()))
list1.append(sub)
s=0
print(travellingSalesmanProblem(list1, s))
INPUT AND OUTPUT:
80
4.Write a program to implement simulated annealing algorithm
AIM :to write a program to implement simulated annealing algorithm
DESCRIPTION :
Simulated Annealing
Simulated Annealing is a stochastic global search optimization algorithm.
The algorithm is inspired by annealing in metallurgy where metal is heated to a high
temperature quickly, then cooled slowly, which increases its strength and makes it easier
to work with.
The annealing process works by first exciting the atoms in the material at a high
temperature, allowing the atoms to move around a lot, then decreasing their excitement
slowly, allowing the atoms to fall into a new, more stable configuration.
When hot, the atoms in the material are more free to move around, and, through random
motion, tend to settle into better positions. A slow cooling brings the material to an
ordered, crystalline state.
SOURCE CODE-1:
In this section, we will apply the simulated annealing optimization algorithm to an
objective function.
First, let’s define our objective function.
We will use a simple one-dimensional x^2 objective function with the bounds [-5, 5].
The example below defines the function, then creates a line plot of the response surface
of the function for a grid of input values, and marks the optima at f(0.0) = 0.0 with a red
line
# convex unimodal optimization function
from numpy import arange
from matplotlib import pyplot
# objective function
def objective(x):
return x[0]**2.0
# define range for input
r_min, r_max = -5.0, 5.0
# sample input range uniformly at 0.1 increments
inputs = arange(r_min, r_max, 0.1)
# compute targets
results = [objective([x]) for x in inputs]
# create a line plot of input vs result
pyplot.plot(inputs, results)
# define optimal input value
x_optima = 0.0
# draw a vertical line at the optimal input
pyplot.axvline(x=x_optima, ls='--', color='red')
# show the plot
pyplot.show()
INPUT AND OUTPUT:
SOURCE CODE-2:
Before we apply the optimization algorithm to the problem, let’s take a moment to
understand the acceptance criterion a little better.
First, the fast annealing schedule is an exponential function of the number of iterations.
We can make this clear by creating a plot of the temperature for each algorithm iteration.
We will use an initial temperature of 10 and 100 algorithm iterations, both arbitrarily
chosen.
The complete example is listed below.
# explore temperature vs algorithm iteration for simulated annealing
from matplotlib import pyplot
# total iterations of algorithm
iterations = 100
# initial temperature
initial_temp = 10
# array of iterations from 0 to iterations - 1
iterations = [i for i in range(iterations)]
# temperatures for each iterations
temperatures = [initial_temp/float(i + 1) for i in iterations]
# plot iterations vs temperatures
pyplot.plot(iterations, temperatures)
pyplot.xlabel('Iteration')
pyplot.ylabel('Temperature')
pyplot.show()
INPUT AND OUTPUT:
SOURCE CODE-3:
# explore metropolis acceptance criterion for simulated annealing
from math import exp
from matplotlib import pyplot
# total iterations of algorithm
iterations = 100
# initial temperature
initial_temp = 10
# array of iterations from 0 to iterations - 1
iterations = [i for i in range(iterations)]
# temperatures for each iterations
temperatures = [initial_temp/float(i + 1) for i in iterations]
# metropolis acceptance criterion
differences = [0.01, 0.1, 1.0]
for d in differences:
metropolis = [exp(-d/t) for t in temperatures]
# plot iterations vs metropolis
label = 'diff=%.2f' % d
pyplot.plot(iterations, metropolis, label=label)
# inalize plot
pyplot.xlabel('Iteration')
pyplot.ylabel('Metropolis Criterion')
pyplot.legend()
pyplot.show()
INPUT AND OUTPUT:
5. Write a program to find the solution for wumpus world problem
AIM :write a program to find the solution for wumpus world problem
DESCRIPTION :
The Wumpus world is a simple world example to illustrate the worth of a knowledge-
based agent and to represent knowledge representation. It was inspired by a video
game Hunt the Wumpus by Gregory Yob in 1973.
The Wumpus world is a cave which has 4/4 rooms connected with passageways. So there
are total 16 rooms which are connected with each other. We have a knowledge-based
agent who will go forward in this world. The cave has a room with a beast which is called
Wumpus, who eats anyone who enters the room. The Wumpus can be shot by the agent,
but the agent has a single arrow. In the Wumpus world, there are some Pits rooms which
are bottomless, and if agent falls in Pits, then he will be stuck there forever. The exciting
thing with this cave is that in one room there is a possibility of finding a heap of gold. So
the agent goal is to find the gold and climb out the cave without fallen into Pits or eaten
by Wumpus. The agent will get a reward if he comes out with gold, and he will get a
penalty if eaten by Wumpus or falls in the pit.
Following is a sample diagram for representing the Wumpus world. It is showing some
rooms with Pits, one room with Wumpus and one agent at (1, 1) square location of the
world.
6.Program to find number of steps to solve 8-puzzle in python
AIM : to find number of steps to solve 8-puzzle in python
Suppose we have a 3x3 board of where all numbers are in range 0 to 8 and no repeating
numbers are there. Now, we can swap the 0 with one of its 4 neighbors, and we are trying
to solve it to get all arranged sequence, we have to find minimum number of steps required
to reach the goal.
So, if the input is like
3 1 2
4 7 5
6 8 0
then the output will be 4
To solve this, we will follow these steps −
Define a function find_next() . This will take node
moves := a map defining moves as a list corresponding to each value {0: [1, 3],1: [0,
2, 4],2: [1, 5],3: [0, 4, 6],4: [1, 3, 5, 7],5: [2, 4, 8],6: [3, 7],7: [4, 6, 8],8: [5, 7],}
results := a new list
pos_0 := first value of node
for each move in moves[pos_0], do
o new_node := a new list from node
o swap new_node[move] and new_node[pos_0]
o insert a new tuple from new_node at the end of results
return results
Define a function get_paths() . This will take dict
cnt := 0
Do the following infinitely, do
o current_nodes := a list where value is same as cnt
o if size of current_nodes is same as 0, then
return -1
o for each node in current_nodes, do
next_moves := find_next(node)
for each move in next_moves, do
if move is not present in dict, then
dict[move] := cnt + 1
if move is same as (0, 1, 2, 3, 4, 5, 6, 7, 8) , then
return cnt + 1
cnt := cnt + 1
From the main method do the following:
dict := a new map, flatten := a new list
for i in range 0 to row count of board, do
o flatten := flatten + board[i]
flatten := a copy of flatten
dict[flatten] := 0
if flatten is same as (0, 1, 2, 3, 4, 5, 6, 7, 8) , then
o return 0
return get_paths(dict)
Let us see the following implementation to get better understanding −
Example
Live Demo
classSolution:
defsolve(self, board):
dict={}
flatten =[]
foriin range(len(board)):
flatten += board[i]
flatten = tuple(flatten)
dict[flatten]=0
if flatten ==(0,1,2,3,4,5,6,7,8):
return0
returnself.get_paths(dict)
defget_paths(self,dict):
cnt=0
whileTrue:
current_nodes=[x for x indictifdict[x]==cnt]
iflen(current_nodes)==0:
return-1
for node incurrent_nodes:
next_moves=self.find_next(node)
for move innext_moves:
if move notindict:
dict[move]=cnt+1
if move ==(0,1,2,3,4,5,6,7,8):
returncnt+1
cnt+=1
deffind_next(self, node):
moves ={
0:[1,3],
1:[0,2,4],
2:[1,5],
3:[0,4,6],
4:[1,3,5,7],
5:[2,4,8],
6:[3,7],
7:[4,6,8],
8:[5,7],
}
results =[]
pos_0 =node.index(0)
for move in moves[pos_0]:
new_node= list(node)
new_node[move],new_node[pos_0]=new_node[pos_0],new_node[move]
results.append(tuple(new_node))
return results
ob=Solution()
matrix =[
[3,1,2],
[4,7,5],
[6,8,0]
]
print(ob.solve(matrix))
Input
matrix = [
[3, 1, 2],
[4, 7, 5],
[6, 8, 0] ]
Output
4
7.write a program to implement towers of Hanoi problem
AIM : to write a program to implement towers of Hanoi problem
Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The
objective of the puzzle is to move the entire stack to another rod, obeying the following
simple rules:
1) Only one disk can be moved at a time.
2) Each move consists of taking the upper disk from one of the stacks and placing it on top
of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3) No disk may be placed on top of a smaller disk.
Note: Transferring the top n-1 disks from source rod to Auxiliary rod can again be thought of
as a fresh problem and can be solved in the same manner.
Python#
# Recursive Python function to solve the tower of hanoi
def TowerOfHanoi(n , source, destination, auxiliary):
if n==1:
print ("Move disk 1 from source"),source,("to destination"),destination
return
TowerOfHanoi(n-1, source, auxiliary, destination)
print ("Move disk",n,"from source"),source,("to destination"),destination
TowerOfHanoi(n-1, auxiliary, destination, source)
# Driver code
n=4
TowerOfHanoi(n,'A','B','C')
# A, C, B are the name of rods
Output:
Move disk 1 from rod A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C
Move disk 3 from rod A to rod B
Move disk 1 from rod C to rod A
Move disk 2 from rod C to rod B
Move disk 1 from rod A to rod B
Move disk 4 from rod A to rod C
Move disk 1 from rod B to rod C
Move disk 2 from rod B to rod A
Move disk 1 from rod C to rod A
Move disk 3 from rod B to rod C
Move disk 1 from rod A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C
8.Write a program to implement A* Algorithm
AIM :to write a program to implement A * Algorithm
A* Algorithm in Python or in general is basically an artificial intelligence problem used for
the pathfinding (from point A to point B) and the Graph traversals. This algorithm is flexible
and can be used in a wide range of contexts. The A* search algorithm uses the heuristic path
cost, the starting point’s cost, and the ending point. This algorithm was first published by
Peter Hart, Nils Nilsson, and Bertram Raphael in 1968.
Why A* Algorithm?
This Algorithm is the advanced form of the BFS algorithm (Breadth-first search), which
searches for the shorter path first than, the longer paths. It is a complete as well as
an optimal solution for solving path and grid problems.
Optimal – find the least cost from the starting point to the ending point. Complete – It
means that it will find all the available paths from start to end.
Contents
Basic concepts of A*
Where
g (n) : The actual cost path from the start node to the current node.
h ( n) : The actual cost path from the current node to goal node.
f (n) : The actual cost path from the start node to the goal node.
For the implementation of A* algorithm we have to use two arrays namely OPEN and
CLOSE.
OPEN:
An array that contains the nodes that have been generated but have not been yet examined
till yet.
CLOSE:
An array which contains the nodes which are examined
Algorithm
1: Firstly, Place the starting node into OPEN and find its f (n) value.
2: Then remove the node from OPEN, having the smallest f (n) value. If it is a goal node,
then stop and return to success.
3: Else remove the node from OPEN, and find all its successors.
4: Find the f (n) value of all the successors, place them into OPEN, and place the removed
node into CLOSE.
5: Goto Step-2.
6: Exit.
Advantages of A* Algorithm in Python
It is fully complete and optimal.
This is the best one of all the other techniques. We use to solve all the complex
problems through this algorithm.
The algorithm is optimally efficient, i.e., there is no other optimal algorithm that is
guaranteed to expand fewer nodes than A*.
Disadvantages of A* Algorithm in Python
This algorithm is complete if the branching factor is finite of the algorithm and every
action has a fixed cost.
The speed execution of A* search is highly dependant on the accuracy of the
heuristic algorithm that is used to compute h (n) and is a bit slower than other
algorithms.
It is having complex problems.
Pseudo-code of A* algorithm
let openList equal empty list of nodes
let closedList equal empty list of nodes
put startNode on the openList (leave it's f at zero)
while openList is not empty
let currentNode equal the node with the least f value
remove currentNode from the openList
add currentNode to the closedList
if currentNode is the goal
You've found the exit!
let children of the currentNode equal the adjacent nodes
for each child in the children
if child is in the closedList
continue to beginning of for loop
child.g = currentNode.g + distance b/w child and current
child.h = distance from child to end
child.f = child.g + child.h
if child.position is in the openList's nodes positions
if child.g is higher than the openList node's g
continue to beginning of for loop
add the child to the openList
A* Algorithm code for Graph
A* algorithm is best when it comes to finding paths from one place to another. It always
makes sure that the founded path is the most efficient. This is the implementation of A* on
a graph structure
fromcollections importdeque
classGraph:
def__init__(self, adjac_lis):
self.adjac_lis =adjac_lis
defget_neighbors(self, v):
returnself.adjac_lis[v]
# This is heuristic function which is having equal values for all nodes
defh(self, n):
H ={
'A': 1,
'B': 1,
'C': 1,
'D': 1
}
returnH[n]
defa_star_algorithm(self, start, stop):
# In this open_lst is a lisy of nodes which have been visited, but who's
# neighbours haven't all been always inspected, It starts off with the start
#node
# And closed_lst is a list of nodes which have been visited
# and who's neighbors have been always inspected
open_lst =set([start])
closed_lst =set([])
# poo has present distances from start to all other nodes
# the default value is +infinity
poo ={}
poo[start] =0
# par contains an adjac mapping of all nodes
par ={}
par[start] =start
whilelen(open_lst) > 0:
n =None
# it will find a node with the lowest value of f() -
forv inopen_lst:
ifn ==Noneorpoo[v] +self.h(v) < poo[n] +self.h(n):
n =v;
ifn ==None:
print('Path does not exist!')
returnNone
# if the current node is the stop
# then we start again from start
ifn ==stop:
reconst_path =[]
whilepar[n] !=n:
reconst_path.append(n)
n =par[n]
reconst_path.append(start)
reconst_path.reverse()
print('Path found: {}'.format(reconst_path))
returnreconst_path
# for all the neighbors of the current node do
for(m, weight) inself.get_neighbors(n):
# if the current node is not presentin both open_lst and closed_lst
# add it to open_lst and note n as it's par
ifm notinopen_lst andm notinclosed_lst:
open_lst.add(m)
par[m] =n
poo[m] =poo[n] +weight
# otherwise, check if it's quicker to first visit n, then m
# and if it is, update par data and poo data
# and if the node was in the closed_lst, move it to open_lst
else:
ifpoo[m] > poo[n] +weight:
poo[m] =poo[n] +weight
par[m] =n
ifm inclosed_lst:
closed_lst.remove(m)
open_lst.add(m)
# remove n from the open_lst, and add it to closed_lst
# because all of his neighbors were inspected
open_lst.remove(n)
closed_lst.add(n)
print('Path does not exist!')
returnNone
INPUT:
1 adjac_lis ={
2 'A': [('B', 1), ('C', 3), ('D', 7)],
3 'B': [('D', 5)],
4 'C': [('D', 12)]
5 }
6 graph1 =Graph(adjac_lis)
7 graph1.a_star_algorithm('A', 'D')
OUTPUT:
Path found: ['A', 'B', 'D']
['A', 'B', 'D']
Explanation:
In this code, we have made the class named Graph, where multiple functions perform
different operations. There is written with all the functions what all operations that function
is performing. Then some conditional statements will perform the required operations to
get the minimum path for traversal from one node to another node. Finally, we will get the
output as the shortest path to travel from one node to another.
Conclusion
A* in Python is a powerful and beneficial algorithm with all the potential. However, it is only
as good as its heuristic function, which is highly variable considering a problem’s nature. It
has found its applications in software systems in machine learning and search optimization
to game development.
9.Write a program to implement Hill Climbing Algorithm
AIM : to write a program to implement hill climbing algorithm
DESCRIPTION:
o Hill climbing algorithm is a local search algorithm which
continuously moves in the direction of increasing elevation/value to
find the peak of the mountain or best solution to the problem. It
terminates when it reaches a peak value where no neighbor has a
higher value.
o Hill climbing algorithm is a technique which is used for optimizing
the mathematical problems. One of the widely discussed examples
of Hill climbing algorithm is Traveling-salesman Problem in which we
need to minimize the distance traveled by the salesman.
o It is also called greedy local search as it only looks to its good
immediate neighbor state and not beyond that.
o A node of hill climbing algorithm has two components which are
state and value.
o Hill Climbing is mostly used when a good heuristic is available.
o In this algorithm, we don't need to maintain and handle the search
tree or graph as it only keeps a single current state.
SOURCE CODE-1:
# hill climbing search of a one-dimensional objective function
from numpy import asarray
from numpy.random import randn
from numpy.random import rand
from numpy.random import seed
# objective function
def objective(x):
return x[0]**2.0
# hill climbing local search algorithm
def hillclimbing(objective, bounds, n_iterations, step_size):
# generate an initial point
solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] -
bounds[:, 0])
# evaluate the initial point
solution_eval = objective(solution)
# run the hill climb
for i in range(n_iterations):
# take a step
candidate = solution + randn(len(bounds)) * step_size
# evaluate candidate point
candidte_eval = objective(candidate)
# check if we should keep the new point
if candidte_eval<=solution_eval:
# store the new point
solution, solution_eval = candidate, candidte_eval
# report progress
print('>%d f(%s) = %.5f' % (i, solution, solution_eval))
return [solution, solution_eval]
# seed the pseudorandom number generator
seed(5)
# define range for input
bounds = asarray([[-5.0, 5.0]])
# define the total iterations
n_iterations = 1000
# define the maximum step size
step_size = 0.1
# perform the hill climbing search
best, score = hillclimbing(objective, bounds, n_iterations, step_size)
print('Done!')
print('f(%s) = %f' % (best, score))
INPUT AND OUTPUT:
1 f([-2.74290923]) = 7.52355
3 f([-2.65873147]) = 7.06885
4 f([-2.52197291]) = 6.36035
5 f([-2.46450214]) = 6.07377
7 f([-2.44740961]) = 5.98981
9 f([-2.28364676]) = 5.21504
12 f([-2.19245939]) = 4.80688
14 f([-2.01001538]) = 4.04016
15 f([-1.86425287]) = 3.47544
22 f([-1.79913002]) = 3.23687
24 f([-1.57525573]) = 2.48143
25 f([-1.55047719]) = 2.40398
26 f([-1.51783757]) = 2.30383
27 f([-1.49118756]) = 2.22364
28 f([-1.45344116]) = 2.11249
30 f([-1.33055275]) = 1.77037
32 f([-1.17805016]) = 1.38780
33 f([-1.15189314]) = 1.32686
36 f([-1.03852644]) = 1.07854
37 f([-0.99135322]) = 0.98278
38 f([-0.79448984]) = 0.63121
39 f([-0.69837955]) = 0.48773
42 f([-0.69317313]) = 0.48049
46 f([-0.61801423]) = 0.38194
48 f([-0.48799625]) = 0.23814
50 f([-0.22149135]) = 0.04906
54 f([-0.20017144]) = 0.04007
57 f([-0.15994446]) = 0.02558
60 f([-0.15492485]) = 0.02400
61 f([-0.03572481]) = 0.00128
64 f([-0.03051261]) = 0.00093
66 f([-0.0074283]) = 0.00006
78 f([-0.00202357]) = 0.00000
119 f([0.00128373]) = 0.00000
120 f([-0.00040911]) = 0.00000
314 f([-0.00017051]) = 0.00000
Done!
f([-0.00017051]) = 0.000000
SOURCE CODE-2:
# hill climbing search of a one-dimensional objective function
from numpy import asarray
from numpy.random import randn
from numpy.random import rand
from numpy.random import seed
from matplotlib import pyplot
# objective function
def objective(x):
return x[0]**2.0
# hill climbing local search algorithm
def hillclimbing(objective, bounds, n_iterations, step_size):
# generate an initial point
solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] -
bounds[:, 0])
# evaluate the initial point
solution_eval = objective(solution)
# run the hill climb
scores = list()
scores.append(solution_eval)
for i in range(n_iterations):
# take a step
candidate = solution + randn(len(bounds)) * step_size
# evaluate candidate point
candidte_eval = objective(candidate)
# check if we should keep the new point
if candidte_eval<=solution_eval:
# store the new point
solution, solution_eval = candidate, candidte_eval
# keep track of scores
scores.append(solution_eval)
# report progress
print('>%d f(%s) = %.5f' % (i, solution, solution_eval))
return [solution, solution_eval, scores]
# seed the pseudorandom number generator
seed(5)
# define range for input
bounds = asarray([[-5.0, 5.0]])
# define the total iterations
n_iterations = 1000
# define the maximum step size
step_size = 0.1
# perform the hill climbing search
best, score, scores = hillclimbing(objective, bounds, n_iterations,
step_size)
print('Done!')
print('f(%s) = %f' % (best, score))
# line plot of best scores
pyplot.plot(scores, '.-')
pyplot.xlabel('Improvement Number')
pyplot.ylabel('Evaluation f(x)')
pyplot.show()
INPUT AND OUTPUT:
10.Build a chatbot using AWS Lex,Pandora bots.
AIM : to build a chatbot using AWS Lex,Pandora bots
Here are the 5 steps to create a chatbot in Python from scratch:
1. Import and load the data file
2. Preprocess data
3. Create training and testing data
4. Build the model
5. Predict the response
1. Import and load the data file
