Scribd
Upload
11 views3 pages

AI-LAb-Program-Std-2)-TSP

Lab program

Uploaded by

alone01112004
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
11 views3 pages

AI-LAb-Program-Std-2)-TSP

Lab program

Uploaded by

alone01112004
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

2) Implementation of TSP(Traveling Salesman Problem) using heuristic

approach

# Python3 program to implement traveling salesman

# problem using naive approach.

from sys import maxsize

from itertools import permutations

V=4

# implementation of traveling Salesman Problem

def travellingSalesmanProblem(graph, s):

# store all vertex apart from source vertex

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:

# store current Path weight(cost)

current_pathweight = 0

# compute current path weight

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

# Driver Code

if __name__ == "__main__":

# matrix representation of graph

graph = [[0, 10, 15, 20], [10, 0, 35, 25],

[15, 35, 0, 30], [20, 25, 30, 0]]

s=0

print(travellingSalesmanProblem(graph, s))
2) Implementation of TSP(Traveling Salesman Problem) using heuristic
approach
OUTPUT:

You might also like