解决tsp问题的算法,
1.TSP问题
TSP (Traveling Salesman Problem)即旅行商问题，也译为旅行商问题和旅行商问题。这是数学领域中著名的问题之一。假设一个出差的商人想去N个城市，他必须选择他想走的路线。路线的限制是每个城市他只能去一次，最后还得回到原来的城市。路径选择的目标是所需的路径距离是所有路径中最小的。
TSP问题是一个组合优化问题。这个问题可以证明具有NPC的计算复杂性。TSP问题可以分为两类，一类是对称TSP问题，一类是非对称TSP问题。所有TSP问题都可以用图来描述：
V={c1，c2，…，ci，…，cn}，i=1，2，…，n，这是所有城市的集合。ci代表第I个城市，N是城市个数；
TSP问题可以表示为：
求解遍历图G=(V，E，C)，所有节点都是一次并返回到初始节点，使得连接这些节点的路径代价最低。
二、爬山算法
爬山算法是一种局部优化方法，采用启发式方法，是深度优先搜索的改进。它使用反馈信息来帮助制定解决方案的决策。该算法每次从当前解的相邻解空间中选择一个最优解作为当前解，直到达到一个局部最优解。它属于一种人工智能算法。
爬山算法实现简单，主要缺点是会陷入局部最优解，但不一定能搜索到全局最优解。如下图所示：假设C点为当前解，爬山算法在搜索A点时会停止搜索局部最优解，因为无论往哪个方向移动，都无法在A点得到更好的解.
爬山算法的实现步骤：
3.求解TSP问题的爬山算法。
在这个JAVA实现中，我们选择使用tsplib上的数据att48，这是一个对称的TSP问题。城市规模为48，其最优值为10628。距离计算方法如下图所示：
具体代码如下：
包诺亚；
导入Java . io . buffered reader；
导入Java . io . file inputstream；
导入Java . io . io exception；
导入Java . io . inputstreamreader；
导入Java . util . random；
公共类爬山{
private int MAX _ GEN//迭代次数
private int cityNum//城市数量，编码长度
private int[][]距离；//距离矩阵
private int bestT//最佳出现代数
private int[]best GH；//最佳路径编码
私有int bestEvaluation
私有Random random
公共爬山(){
* GA的构造者
* @param n
*城市数量
* @param g
*运行代数
公共爬山(int n，int g) {
city num=n；
MAX _ GEN=g；
//给编译器一个指令，让它对带注释的代码元素中的一些警告保持沉默。
@SuppressWarnings(resource )
*初始化爬山算法类
* @param filename数据文件名，存储所有城市节点坐标数据。
* @抛出IOException
私有void init(字符串文件名)引发IOException {
//读取数据
int[]x；
int[]y；
字符串strbuff
buffered reader data=new buffered reader(new InputStreamReader(
新文件输入流(文件名)))；
distance=new int[city num][city num]；
x=new int[city num]；
y=new int[city num]；
for(int I=0；i cityNumi ) {
//读取一行数据，数据格式1 6734 1453
strbuff=data . readline()；
//字符分割
string[]strcol=strbuff . split()；
x[I]=integer . value of(strcol[1])；//x坐标
y[I]=integer . value of(strcol[2])；//y坐标
//计算距离矩阵
//针对具体问题，距离计算方法不同，
//这里以att48为例。它有48个城市。距离计算方法为伪欧氏距离，最优值为10628。
for(int I=0；I city num-1；i ) {
距离[I][I]=0；//对角线为0
for(int j=I 1；j cityNumj ) {
double rij=数学。sqrt((x[I]-x[j])*(x[I]-x[j))(y[I]-y[j])
*(y[I]-y[j])/10.0)；
//圆形，圆形
int tij=(int)math . round(rij)；
if (tij rij) {
距离[I][j]=tij 1；
距离[j][i]=距离[I][j]；
}否则{
距离[I][j]=tij；
距离[j][i]=距离[I][j]；
距离[城市编号-1][城市编号-1]=0；
best GH=new int[city num]；
最佳评估=整数最大值
bestT=0；
Random=新的Random(系统。当前时间毫秒())；
//初始化编码德国
void initGroup() {
int i，j；
最佳GH[0]=随机。nextint(65535)%城市号码；
for(I=1；i cityNum)//编码长度
最佳GH[I]=random。nextint(65535)%城市号码；
for(j=0；j j ) {
if (bestGh[i]==bestGh[j]) {
打破；
if (j==i) {
我；
public int evaluate(int[] chr) {
int len=0；
//染色体，起始城市，城市1,城市2.城市n
for(int I=1；i cityNumi ) {
len=distance[chr[I-1]][chr[I]]；
//城市n，起始城市
len=distance[chr[城市编号-1]][chr[0]]；
返回低输入联网（low-entry networking的缩写）
//爬山算法
public void pashan(int[] Gh，int T) {
int i，temp，TT=0；
int ran1，ran2
int e；//评价新值
int[]tempGh=new int[city num]；
最佳评价=评价(Gh)；
//爬山代数T
for(TT=0；tt tt ) {
for(I=0；i cityNumi ) {
tempGh[I]=Gh[I]；
ran 1=随机。nextint(65535)%城市号码；
ran 2=随机。nextint(65535)%城市号码；
while (ran1==ran2) {
ran 2=随机。nextint(65535)%城市号码；
//两交换法实施邻域操作
temp=tempGh[ran 1]；
tempGh[ran 1]=tempGh[ran 2]；
tempGh[ran 2]=temp；
e=evaluate(tempGh)；//评价新值
如果（最佳评估){
bestT=TT；
最佳评价=e；
for(I=0；i cityNumi ) {
GH[I]=tempGh[I]；
公共void solve() {
init group()；//初始化编码
帕山(bestGh，MAX _ GEN)；
System.out.println(最佳长度出现代数：);
系统。出去。println(bestT)；
System.out.println(最佳长度);
系统。出去。println(最佳评价)；
System.out.println(最佳路径：);
for(int I=0；i cityNumi ) {
System.out.print(bestGh[i]，)；
if (i % 10==0 i！=0) {
系统。出去。println()；
* @param args
* @抛出异常
公共静态void main(String[] args)引发IOException {
System.out.println(Start . );
爬山爬山=新爬山(48,5000);
希尔剪辑。init( c://data。txt’)；
希尔剪辑。solve()；
运行结果截图：
四、总结
爬山算法由于其简单的结构，在处理多约束大规模问题时比较力不从心，很难得到较好的解，但在小规模的公证人问题求解中，解的质量还是比较好的；此外爬山算法结构简单，在某些情况下，整体效率比A星算法的效果还好。
注：本文部分内容来源于网络，但程序以及分析结果属于本人成果，转载请注明！
