穷举法的结果比较方法

Question

#输入6个城市坐标，字典形式
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])
我是先生成全排列之后再把全排列存起来，然后再一个一个比较的；
能否修改成不依赖存储的排列结果，换句话说，一个一个比较，算一个，比较一个的方法呢？

Answer 1

```python
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 = []
min_sum = "inf"  # ==========================================================初始化min_sum为正无穷
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]
        """
        if sum < min_sum:
            min_sum = sun =========================================== 在计算出结果后，前一个结果和后一个结果直接比较
        """
    juli.append(sum)
print('最小距离：', min(juli))
zuiyou = min(juli)   # ==========================================这行可以注释
c = juli.index(min(juli))
print('最短路径：', v[c])
# 原问题采用先生成全部可能结果的排列，存下来，在比较的方法；
# 如何修改为不依赖存储的排列结果，换句话说，一个一个比较，算一个，比较一个的方法呢？

```