#从其中的某一城市出发,不重复地走完其余5个并回到原出发点,在所有可能的路径中求出路径长度最短的一条。
六个市坐标为:1(87,7).2(91,38)、3(83,46).4(71,44).5(64,60)、6(68,58)
import math
city={'x':[87,91,83,71,64,68],'y':[7,38,46,44,60,58]}
n=6
x=city['x']
y=city['y']
import numpy as np
#计算距离
a=np.zeros((n,n))
for i in range(6):
for j in range(6):
a[i,j] = math.sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2))
#生成6个城市的全部排列
import itertools
v=list(itertools.permutations([1,2,3,4,5,6],n))
#计算最短总距离
m=len(v)
juli=[]
for i in range(m):
sum=0
for j in range(n-1):
sum=sum+a[v[i][j]-1,v[i][j+1]-1]
sum=sum+a[v[i][j+1]-1,v[i][0]-1]
juli.append(sum)
print('最小距离:',min(juli))
zuiyou=min(juli)
c=juli.index(min(juli))
print('最短路径:',v[c])
原问题采用先生成全部可能结果的排列,存下来,在比较的方法;
如何修改为不依赖存储的排列结果,换句话说,一个一个比较,算一个,比较一个的方法呢?