目录
本题涵盖的知识点主要包括嵌套列表，文件读取和处理，绘图。
TSP，即旅行商问题，又称TSP问题（Traveling Salesman Problem），是数学领域中著名问题之一。假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。下面将通过几个子问题以循环的方式解决TSP问题。
显然，起始点的选择不会影响路径长度。
例如：
A,B两个城市，路径为A--->B--->A
A,B,C三个城市，路径为A--->B--->C--->A，A--->C--->B--->A
A,B,C,D四个城市，路径有A--->B--->C--->D--->A，A--->B--->D--->C--->A，A--->C--->B--->D--->A，A-->C--->D--->B--->A，A--->D--->B--->C--->A，A--->D--->C--->B--->A，共有6条路径。
不加证明的给出当城市个数为n，路径总数为（n-1）!
这是题目所需的文件：
链接：https://pan.baidu.com/s/1u_ZBqbt_0odQwB0NT2eTJA?pwd=6666
提取码：6666
链接：https://pan.baidu.com/s/1lmAVdwCgfdi1NEMUuyqZPw?pwd=6666
提取码：6666
这是文章所有内容的压缩包：
链接：https://pan.baidu.com/s/1qOUmBJCoio7a6DMJyfEeXw?pwd=6666
提取码：6666
请定义阶层函数 f（n），n>=2，返回城市个数的方案数（n-1）!
例如
>>> f(2)
1
>>> f(4)
6
>>> f(10)
362880
#问题1
#********* Begin *********#
def f(n):
if n==2:
return 1
else:
return (n-1)*f(n-1)
#********* End *********#请定义函数read()（无输入参数），读取文件中储存的n个城市的地址（n>=2），要求返回n*2的嵌套列表。文件格式第一列为横坐标，第二列为纵坐标。
注：
关于文件地址的获取：鼠标右键复制文件地址会返回："C:\Users\username\Desktop\city_location.txt"这样一个字符串。
例如：
读取文件前六行时：（每行中间以四个空格隔开）
1304 2312
3639 1315
4177 2244
3712 1399
3488 1535
3326 1556
返回的列表：
[[1304, 2312],
[3639, 1315],
[4177, 2244],
[3712, 1399],
[3488, 1535],
[3326, 1556]]
提示：注意\n的处理
#问题2
from pprint import pprint
#********* Begin *********#
def read():
infile=open(r"C:\Users\hqh\Desktop\1.txt",'r').readlines()
n=len(infile)
l=[0]*n
for i in range(n):
l[i]=[eval(j) for j in infile[i].replace('\t',' ').replace('\n','').split()]
return l
#********* End *********#
location=read()
pprint(location[0:6])请定义distance(location)函数，location是问题二中read()的返回值，是一个n*2嵌套列表即n个城市的坐标。要求返回n*n列表dist，dist[i][j]表示第i到第j个城市的距离。
提示：dist[i][i]=0;dist[i][j]=dist[j][i]
例如：以问题二返回值为location
[[0.0,
2538.943481056638,
2873.8046210555094,
2575.27338354591,
2318.0994370388858,
2158.707946897866],
[2538.943481056638,
0.0,
1073.53854145997,
111.28791488746656,
266.83515510516975,
395.03164430207363],
[2873.8046210555094,
1073.53854145997,
0.0,
964.4946863513557,
988.6364346917425,
1094.3239922436135],
[2575.27338354591,
111.28791488746656,
964.4946863513557,
0.0,
262.0534296665472,
416.70733134899365],
[2318.0994370388858,
266.83515510516975,
988.6364346917425,
262.0534296665472,
0.0,
163.35544068074378],
[2158.707946897866,
395.03164430207363,
1094.3239922436135,
416.70733134899365,
163.35544068074378,
0.0]]
#问题3
#********* Begin *********#
def distance(l):
n=len(l)
dist=[[0]*n for i in range(n)]
for i in range(n):
for j in range(i,n):
dist[i][j]=((l[i][0]-l[j][0])**2+(l[i][1]-l[j][1])**2)**0.5
dist[j][i]=dist[i][j]
return dist
#********* End *********#
pprint(distance(location[0:6]))请定义函数length(way),way是传入的1*n列表，里面是0~（n-1）的一个排列，即路径，最后会返回出发点，要求函数返回路径和，
若代码正确则会输出如下：
[7161.093526113121, 7438.587165121758]
提示：可以利用问题3的dist进行计算
#问题4.1
#********* Begin *********#
dist=distance(location) #请在左侧为dist赋值
def length(way):
l=dist[way[0]][way[-1]]
for i in range((len(way)-1)):
l+=dist[way[i]][way[i+1]]
return l
#********* End *********#
print([length([0,1,2,3,4,5]),length([0,1,2,4,3,5])])由前面定义的阶层函数f（n）知路径总数为（n-1）！，而初始点的选择对结果没有影响，故默认以第n个城市为起点，关于0~(n-2)（索引值，对应第1个到（n-1）个城市）的全排列代码已给出，并储存在（n-1）！*（n-1）列表ways中。
例如，n=4，ways是0-2的全排列，ways=[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
ways是0~(n-2)的全排列，请你把n-1添加至ways每一个子列表开头，以上为例，添加元素后的ways=[[3, 0, 1, 2], [3, 0, 2, 1], [3, 1, 0, 2], [3, 1, 2, 0], [3, 2, 0, 1], [3, 2, 1, 0]]
提示：这是添加到子列表开头不是末尾
#问题4.2.1
import itertools
n=len(dist)
nums = list(range(n-1))
ways= [list(i) for i in list(itertools.permutations(nums))]
#********* Begin *********#
ways=[[n-1]+i for i in ways]
#********* End *********#在问题4.2.1的基础上，遍历所有方案并返回最短路径对应的方案bestway,bestway是一个1*n的列表。
提示：你可以使用length(way)帮助你解决问题
#问题4.2.2
#********* Begin *********#
def best(ways):
lways=[length(i) for i in ways]
bestway=ways[lways.index(min(lways))]
return bestway
#********* End *********#
bestway=best(ways)
请在同一张画布上绘制1*2两个子图，相关的库已经导入
请在第一个子图中绘制城市坐标散点图，函数已经定义，无返回值。要求：标题为”城市坐标散点图”，图例为”citylocation”。你无需添加show语句。
提示：plt.scatter(x,y)会绘制相应坐标的散点图
提示：在输入图例的时候传入的字符串应当储存在列表中，例如图例为”a”时，传入为[“a”]
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei']#显示中文标签
#问题5.1
def p1():
#********* Begin *********#
x=[i[0] for i in location]
x.append(x[0])
y=[i[1] for i in location]
y.append(y[0])
plt.subplot(1,2,1)
plt.scatter(x,y)
plt.title('城市坐标散点图')
plt.legend(['citylocation'])
#********* End *********#
p1()请在第二个子图中根据问题4求得的最短路径bestway绘制路径图，要求：标题为”最佳路径”，图例为”bestway”，线型要求为 ’r*-’。你无需添加show语句。
注意：终点和起点需要连接
提示：subplot(m,n,p)表示在有m*n个子图的画布上绘制第p张子图
当输入文件是1时输出如下
当输入文件是2时输出如下：
#问题5.2
def p2():
#********* Begin *********#
x=[location[i][0] for i in bestway]
x.append(x[0])
y=[location[i][1] for i in bestway]
y.append(y[0])
plt.subplot(1,2,2)
plt.plot(x,y,'r*-')
plt.legend(['bestway'])
plt.title('最佳路径')
#********* End *********#
p2()
plt.show()