Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

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

0 votos
188 visitas
perguntada Abr 9, 2016 em Ciência da Computação por danielcajueiro (5,726 pontos)  
Compartilhe

1 Resposta

0 votos
respondida Abr 9, 2016 por danielcajueiro (5,726 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')

Travelling Salesman Brute force

...