tsp问题-遍历算法/随机算法
旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
1 #!/user/bin/env python 2 # -*- coding:utf-8 -*- 3 4 # TSP旅行商问题：若干个城市，任意两个城市之间距离确定，要求一旅行商从某城市 5 # 出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，试 6 # 确定一条最短路径使旅行费用最少 7 8 # 遍历算法 9 10 # 给定某条路径，计算它的成本 11 def distcal(path, dist): 12 # 计算路径成本（路径，距离） 13 sum_dist = 0 # 总成本 14 for j in range(0, len(path) - 1): 15 di = dist[int(path[j]) - 1][int(path[j + 1]) - 1] # 查找第j和j+1个城市之间的成本 16 sum_dist = sum_dist + di # 累加 17 di = dist[int(path[len(path) - 1]) - 1][path[0] - 1] # 最后一个城市回到初始城市的成本 18 sum_dist = sum_dist + di 19 return sum_dist # 返回路径的成本 20 21 22 # 递归,构造所有可能路径 23 def perm(l): # 构造路径（城市列表） 24 if (len(l)) <= 1: # 只有一个城市，选择这个城市 25 return [l] 26 r = [] # 空列表 27 for i in range(len(l)): # 对每个城市，构建不包括这个城市的所有可能序列 28 s = l[:i] + l[i + 1:] # 去除当前城市的列表 29 p = perm(s) # 调用自身，构造不包含这个城市的序列 30 for x in p: 31 r.append(l[i:i + 1] + x) # 将序列和该城市合并，得到完整的序列 32 return r 33 34 35 if __name__ == '__main__': 36 city = [1, 2, 3, 4, 5] 37 38 dist = ((0, 1, 3, 4, 5), 39 (1, 0, 1, 2, 3), 40 (3, 1, 0, 1, 2), 41 (4, 2, 1, 0, 1), 42 (5, 3, 2, 1, 0)) 43 44 for i in range(0, 5): 45 print(dist[i][:]) 46 47 print('=============') 48 49 allpath = perm(city) # 调用路径产生函数，产生所有可能的路径 50 51 optimal = 1000000 # 初始化最优路径的总成本和索引号 52 53 index = 1 54 55 for i in range(0, len(allpath)): 56 pd = distcal(allpath[i], dist) 57 if pd < optimal: # 比较是否总成本更低，如果是替换最优解 58 optimal = pd 59 index = i 60 # print(pd) 61 62 print(optimal) 63 print(allpath[index]) 64 ------------------------------------------------------------------------ 65 (0, 1, 3, 4, 5) 66 (1, 0, 1, 2, 3) 67 (3, 1, 0, 1, 2) 68 (4, 2, 1, 0, 1) 69 (5, 3, 2, 1, 0) 70 ============= 71 9 72 [1, 2, 3, 4, 5]
1 #!/user/bin/env python 2 # -*- coding:utf-8 -*- 3 4 import random 5 6 # 给定某条路径，计算它的成本 7 def distcal(path, dist): 8 # 计算路径成本（路径，距离） 9 sum_dist = 0 # 总成本 10 for j in range(0, len(path) - 1): 11 di = dist[int(path[j]) - 1][int(path[j + 1]) - 1] # 查找第j和j+1个城市之间的成本 12 sum_dist = sum_dist + di # 累加 13 di = dist[int(path[len(path) - 1]) - 1][path[0] - 1] # 最后一个城市回到初始城市的成本 14 sum_dist = sum_dist + di 15 return sum_dist # 返回路径的成本 16 17 # 构造随机路径 18 def randompath(inc): # Inc城市列表 19 allcity = inc[:] # 城市列表 20 path = [] # 路径 21 loop = True 22 while loop: 23 if 1 == len(allcity): # 如果是最后一个城市 24 tmp = random.choice(allcity) 25 path.append(tmp) 26 loop = False # 结束 27 else: # 如果不是最后一个城市 28 tmp = random.choice(allcity) # 在城市列表中随机选择一个城市 29 path.append(tmp) # 添加路径 30 allcity.remove(tmp) # 在城市列表中移除该城市 31 return path 32 33 if __name__ == '__main__': 34 city = [1, 2, 3, 4, 5] 35 36 dist = ((0, 1, 3, 4, 5), 37 (1, 0, 1, 2, 3), 38 (3, 1, 0, 1, 2), 39 (4, 2, 1, 0, 1), 40 (5, 3, 2, 1, 0)) 41 42 for i in range(0, 5): 43 print(dist[i][:]) 44 45 print('=============') 46 47 num = 10 # 随机产生10条路径 48 49 optimal = 1000000 # 初始化最优路径的总成本和索引号 50 51 for i in range(0, num): 52 pd = distcal(randompath(city), dist) 53 if pd < optimal: # 比较是否总成本更低，如果是替换最优解 54 optimal = pd 55 print(pd) 56 57 print(optimal) 58 ------------------------------------------------------------ 59 (0, 1, 3, 4, 5) 60 (1, 0, 1, 2, 3) 61 (3, 1, 0, 1, 2) 62 (4, 2, 1, 0, 1) 63 (5, 3, 2, 1, 0) 64 ============= 65 9 66 12 67 11 68 14 69 12 70 11 71 14 72 9 73 14 74 9 75 最优： 9