用Python解决TSP问题(1)——贪心算法

文章源码在Github：https://github.com/jinchenghao/TSP

关于TSP问题网上有很多介绍，这里再简单描述一下。旅行商问题(TravelingSalesmanProblem，TSP)一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要遍历所有城市一次且只能一次，回到出发地。应如何选择行进路线，以使总的行程最短。目前解决TSP问题的方法有许多种，比如：贪心算法、动态规划算法、分支限界法；也有智能算法，比如：蚁群算法、遗传算法、A*等。由于网上使用python解决这类问题的比较少，所以我会用python实现这些算法。本文先介绍贪心算法：

数据格式

数据格式如下：

城市XYCity1100200City2150200City3345313...  

即输入的数据有3列，第一列是城市编号，第二列和第三列是城市坐标(x,y)。

算法简介

贪心算法非常容易理解，是一种解决实际问题中的常用方法，经常用来和其他算法进行比较。所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

在TSP问题上，假设城市集合为B，我们每次只选择距离当前城市最近的城市移动。同时集合s记录已经遍历过得城市，下次从集合(B-s)中选择。

程序

输入：

1 2066 2333 2 935 1304 3 1270 200 4 1389 700 5 984 2810 6 2253 478 7 949 3025 8 87 2483 9 3094 1883 10 2706 3130

代码如下：

#贪心法 import pandas as pd import numpy as np import math import time dataframe = pd.read_csv("./data/TSP100cities.tsp",sep=" ",header=None) v = dataframe.iloc[:,1:3] train_v= np.array(v) train_d=train_v dist = np.zeros((train_v.shape[0],train_d.shape[0])) #计算距离矩阵 for i in range(train_v.shape[0]): for j in range(train_d.shape[0]): dist[i,j] = math.sqrt(np.sum((train_v[i,:]-train_d[j,:])**2)) """ s:已经遍历过的城市 dist：城市间距离矩阵 sumpath:目前的最小路径总长度 Dtemp：当前最小距离 flag：访问标记 """ i=1 n=train_v.shape[0] j=0 sumpath=0 s=[] s.append(0) start = time.clock() while True: k=1 Detemp=10000000 while True: l=0 flag=0 if k in s: flag = 1 if (flag==0) and (dist[k][s[i-1]] < Detemp): j = k; Detemp=dist[k][s[i - 1]]; k+=1 if k>=n: break; s.append(j) i+=1; sumpath+=Detemp if i>=n: break; sumpath+=dist[0][j] end = time.clock() print("结果：") print(sumpath) for m in range(n): print("%s-> "%(s[m]),end='') print() print("程序的运行时间是：%s"%(end-start))

结果：