# Como implementar uma solução computacional para o problema do caixeiro viajante?

0 votos
334 visitas

## 1 Resposta

0 votos
respondida Abr 9, 2016 por (5,581 pontos)

Uma solução ineficiente baseada em busca exaustiva é:

# The Euclidian version of the Travelling Salesman problem
import numpy as np
import matplotlib.pyplot as plt
from itertools import permutations

np.random.seed(0)
fig=plt.figure(num=None, figsize=(8, 8), dpi=80, facecolor='w', edgecolor='k')
plt.hold(True)
epsilon=0.1
plt.axis([0-epsilon, 1+epsilon, 0-epsilon, 1+epsilon])

def travelling_salesman(vector):
n=np.shape(vector)[0]
# I am supposing that the travel starts at vector[0]0]
thePermutations=list(permutations(range(1,n)))
numberPermutations=len(thePermutations)
print "numberPermutations",numberPermutations
minimalDistance=10000000
for i in range(numberPermutations):
totalDist=0
for j in range(n):
if(j==0):
l=0
m=thePermutations[i][j]
elif(j==n-1):
l=thePermutations[i][j-1]
m=0
else:
l=thePermutations[i][j-1]
m=thePermutations[i][j]
dist=np.sqrt(np.power(vector[l,0]-vector[m,0],2)+np.power(vector[l,1]-vector[m,1],2))
totalDist=totalDist+dist

if(totalDist<minimalDistance):
thePath=thePermutations[i][:]
minimalDistance=totalDist
return thePath

if __name__ == '__main__':

n=8
vector=np.random.uniform(size=[n,2])
thePath=travelling_salesman(vector)
plt.plot(vector[:,0],vector[:,1],'b.',markersize=20)
plt.plot(vector[0,0],vector[0,1],'r.',markersize=20)
plt.plot([vector[0][0],vector[thePath[0]][0]],[vector[0][1],vector[thePath[0]][1]],'r',markersize=20)
for i in range(n-2):
plt.plot([vector[thePath[i]][0],vector[thePath[i+1]][0]],[vector[thePath[i]][1],vector[thePath[i+1]][1]],'r',markersize=20)
plt.plot([vector[thePath[n-2]][0],vector[0][0]],[vector[thePath[n-2]][1],vector[0][1]],'r',markersize=20)
plt.savefig('path.eps')