问题描述不展开了，感兴趣可以自己搜一下。csdn上这篇文章介绍的很详细，可以看一下 ，http://blog.csdn.net/q345852047/article/details/6626684 感谢作者辛勤码字，我就偷懒啦～
1.贪心
"""
Functions:
find_path:
Data structures:
path_vertexs：保存遍历过的顶点，防止重复遍历
path_length：保存遍历过的每条边的权值
"""
def find_path(j):
path_vertexs.append(j) #把该节点标记为已走过
row=c[j]
#创建copy_row,删除row中已走过的顶点,防止直接在row上操作.
copy_row=[value for value in row]
walked_vertex=[]
for i in path_vertexs:#已走过的顶点
walked_vertex.append(copy_row[i])
for vertex in walked_vertex:
copy_row.remove(vertex)
#寻找row中的未遍历过的最短边
if len(path_vertexs)<5:
min_e=min(copy_row)
j=row.index(min_e)
path_length.append(min_e)
find_path(j)
else:
min_e=c[j][0]
path_length.append(min_e)
path_vertexs.append(0)
return path_vertexs,path_length
def print_path(vertexs,lengths):
path=''
vertexs=[vertex+1 for vertex in vertexs]
for i,vertex in enumerate(vertexs):
path+=str(vertex)
if i==5:
break
path+='->'
print("最小总旅费为：",sum(lengths))
print("路 径：",path)
if __name__ == "__main__":
c=[[0,3,1,5,8],
[3,0,6,7,9],
[1,6,0,4,2],
[5,7,4,0,3],
[8,9,2,3,0]]
path_length=[]
path_vertexs=[]
path_vertexs,path_length=find_path(0)
print_path(path_vertexs,path_length)
""" 从顶点0开始：
把0加入到已遍历集合，寻找第0行的最小值，并返回其所在列j，
转到第j行，寻找未遍历过的最短边。
把顶点加入已遍历集合，保存对应的最小权值。
停止： 当走过的顶点集长度=5时，停止
"""```
二. 动态规划
Note： 当前代码只输出最短路径长度，没有输出最短路径，以后有时间补上，实在要是忘了....那就忘了吧～
以下代码采用动态规划的思想，实现TSP最短路径的求解问题。
matrix for undirected graph
c=[[0,3,1,5,8],
[3,0,6,7,9],
[1,6,0,4,2],
[5,7,4,0,3],
[8,9,2,3,0]]
n=len(c)
初始化d
d=[[0 for j in range(2**(n-1))] for i in range(n)]
for i in range(1,n): # 1234
d[i][0]=c[i][0]
用二进制表示顶点集合v，j代表其相应的编号：
"""0 000 {}
1 001 {1}
2 002 {2}
3 011 {1,2}
4 100 {3}
5 101 {1,3}
6 110 {2,3}
7 111 {1,2,3}
"""
判断集合是否包含某元素 judge()
def judge(i,j):#3=1+2 5=101 1+3 6=3+2
involve=(i&j)==0#结果为0说明不包含
return involve #若j不包含i 返回true
计算j包含那些顶点,利用与运算
def find_vertex(j):
vertexs=[]#j包含哪几个顶点
for v in range(n-1):
if (2v)&j!=0:#0123 2i表示顶点i+1
vertexs.append(v+1) #说明j包含顶点v+1
return vertexs
-------------------
for j in range(2(n-1)):# j从0-15
for i in range(1,n):# 1234
temp=[]
vertexes=find_vertex(j)
if i not in vertexes:
for k in vertexes:
temp.append(c[i][k]+d[k][j-2(k-1)])
if temp:
d[i][j]=min(temp)
print(d[i][j])
对v[2(n-1)-1]中的每个元素k计算，d[0][2(n-1)-1]=min(c[0][k]+d[k][...])
temp=[]
for k in find_vertex(2(n-1)-1):
j=2(n-1)-1
new_j=2(n-1)-1-2(k-1)
temp.append(c[0][k]+d[k][new_j])
d[0][2**(n-1)-1]=min(temp)
print("Shortest path length:",d[0][2**(n-1)-1])
for row in d:
for col in row:
print(str(col)+" ",end="")
print()
