TSP问题一直是个头疼的问题，但是解决的方法数不胜数，很多的算法也都能解决。百度资料一大堆，但是我找到了代码比较简练的一种。随机法。下面只是个人的看法而已，如果有任何问题虚心接受。
顾名思义，随机法就是随机一个序列然后用这个序列去解决问题。
TSP问题描述中，一个人走一圈回到原点要使走过的路程最短，那么他一定有一个路径，随机法，随机的就是这个路径。
首先我们要明白的是，只要随机的量足够大，最终一定能得到结果，因为能随机到枚举的全部。
第二，随机了一个路径之后，我们要在这个路径下面找到最短的路径，方法是通过交换两个位置得到的。
第三，要根据题目意思，确定图不是很大，或者数据量并非那种特别巨大的题目，也就是说看清题目。灵活选用方法。
1、我们随机一个路线出来
0-3-1-2-0（最终是要返回0的）
2、我们根据这个路径找到这个路径的路程s。
3、除了首尾的0之外，交换任意两个数，如果交换完了之后s变小了，就更新s
听上去是不是觉得这个算法很扯，是不是感觉最终得不到最优解，可是当你循环个50000次试试，你就知道，基本上99%都能拿到最优解，这个比暴力搜索快，但是比dp不稳，这个算法的有点在于编码不复杂，而且在基本问题上面都能得到最优解，所以最终我选择了这个。
下面附上代码：
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm> using namespace std;
/*TSP随机法*/ int n;//图的大小
int maps[][];//记录任意两点的距离
int order[];//记录行走的顺序 //计算当前行走顺序下的距离
int dis()
{
int nowDis=;
int i;
//因为是从0开始走最后返回所以是n+1
for (i = ; i <= n+; i++)
{
nowDis += maps[order[i-]][order[i]];
}
return nowDis;
} int main()
{
int i,j;
int answer;//记录答案
int result;//记录最终输出
int ready=;//记录是否成功
int temp;//临时变量
cin>>n;
//用户输入家到任意一点的距离，保存在第一行中
for (i = ; i <= n; i++)
{
cin>>maps[][i];
maps[i][] = maps[][i];
}
//用户输入任意两点间的距离
for (i = ; i <= n; i++)
{
for (j = ; j <= n; j++)
{
cin>>maps[i][j];
maps[j][i] = maps[i][j];
}
} result = ;
//下面是随机开始 int t;//随机的次数
for (t = ; t < ; t++)
{
//初始化随机序列
for (i = ; i <= n; i++)
order[i] = i;
order[] = ;//一定是从0点开始走
order[n+] = ;//一定最终回到0点 //交换任意随机序列中的值，不动0点和n+1点的值
for (i = ; i <= n; i++)
{
j = rand()%n + ;
swap(order[i],order[j]);
} //获取当前最短路
answer = dis();
while (true)
{
ready = ;
for (i = ; i <= n; i++)
{
for (j = i+; j <= n; j++)
{
//交换每两个值
swap(order[i],order[j]);
temp = dis();
//如果当前交换之后，比当前路径小，那么就更新值
if(temp < answer)
{
answer = temp;
ready = ;
}
else//如果不比当前小，交换回来
swap(order[i],order[j]);
}
}
//只要有一次交换，那么就再一次循环，确保不存在更小的路径
if(ready == )
break;
} if(result > answer)
result = answer;
}
cout<<result<<endl;
return ;
}