Scribd
Upload
3 views2 pages

Practical 4

The document presents implementations of the Brute Force Method and Nearest Neighbour Approach for solving the Traveling Salesman Problem (TSP) using Python. It includes code snippets that read a distance matrix from a CSV file, calculate the best tour and minimum distance, and measure the time taken for execution. The results show the best tour and minimum distance for both methods, with specific examples provided for different starting cities.

Uploaded by

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

Practical 4

The document presents implementations of the Brute Force Method and Nearest Neighbour Approach for solving the Traveling Salesman Problem (TSP) using Python. It includes code snippets that read a distance matrix from a CSV file, calculate the best tour and minimum distance, and measure the time taken for execution. The results show the best tour and minimum distance for both methods, with specific examples provided for different starting cities.

Uploaded by

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

### JENIN PATEL

### 24BTM052
### AIML(1CS101CC22)

### BRUTE FORCE METHOD

import pandas as pd
import numpy as np
import time
from itertools import permutations
mat=pd.read_csv("6citytsp.csv",header=None)
city_name=list(range(mat.shape[0]))
tour=list(permutations(city_name))
st=time.process_time()
dmin=np.inf
best_tour=None
for i in range(len(tour)):
d=0
for j in range(mat.shape[0]-1):
d=d+mat.iloc[tour[i][j],tour[i][j+1]]
tour_length=d+mat.iloc[tour[i][mat.shape[0]-1],tour[i][0]]
if tour_length<dmin:
dmin=tour_length
best_tour=tour[i]
et=time.process_time()
print("Best Tour:",best_tour)
print("Minimum Distance:",dmin)
print("Time taken: ",et-st)

Best Tour: (0, 1, 2, 3, 4, 5)


Minimum Distance: 1248
Time taken: 0.07022165800000124

### BRUTE FORCE METHOD (STARTING CITY INPUTED)

import pandas as pd
import numpy as np
from itertools import permutations
mat=pd.read_csv("6citytsp.csv",header=None)
scity=int(input("Enter Starting City:"))
citynames=list(range(mat.shape[0]))
citynames.remove(scity)
citynames.insert(0,scity)
tour=list(permutations(citynames))
dmin=np.inf
best_tour=None
for i in range(len(tour)):
d=0
for j in range(len(tour[i])-1):
d=d+mat.iloc[tour[i][j],tour[i][j+1]]

tour_length=d+mat.iloc[tour[i][-1],tour[i][0]]
if tour_length<dmin:
dmin=tour_length
best_tour=tour[i]
et=time.process_time()
print("Time Taken:",et-st)
print("Best Tour:",best_tour)
print("Minimum Distance:",dmin)

Enter Starting City:5


Time Taken: 3.5871656509999994
Best Tour: (5, 0, 1, 2, 3, 4)
Minimum Distance: 1248

### NEAREST NEIGHBOUR APPROACH

import pandas as pd
import numpy as np

df = pd.read_csv("6citytsp.csv", header=None)
startcity = int(input("Enter Starting City: "))

num_cities = df.shape[0]
currentcity = startcity
tour = [currentcity]
totaldistance = 0
citiesleft = list(range(num_cities))
citiesleft.remove(currentcity)

while citiesleft:
distances = df.iloc[currentcity, citiesleft]
closestcityindex = np.argmin(distances)
nearest_city = citiesleft[closestcityindex]

tour.append(nearest_city)
totaldistance += distances.iloc[closestcityindex]
currentcity = nearest_city
citiesleft.remove(currentcity)

totaldistance += df.iloc[tour[-1], tour[0]]


tour.append(tour[0])

print("Best Tour:", tour)


print("Minimum Distance:", totaldistance)

Enter Starting City: 0


Best Tour: [0, 1, 5, 4, 3, 2, 0]
Minimum Distance: 1272

You might also like