[C++知识库]Haywire（模拟退火）

TSP问题

旅行商问题（Traveling Salesman Problem），假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

解

对于TSP问题，一个解决方案就是遍历不同的排列顺序，采用模拟退火算法，在产生新解时可以随机选取两个节点，然后交换位置（看起来还是很暴力，但是效果确实不错）；
需要明确的时，模拟退火算法虽然相对一些方法来说更容易跳出局部最优，但还是不能保证得到的结果一定是全局最优

Haywire

思路

模拟退火，解的更新为随机选取两个牛交换位置

代码

代码参考：添加链接描述

#include<bits/stdc++.h>
using namespace std;
int n;
const double h=0.996;   //参数
int a[50][50];
int ans;
int pos[50];
int calc()
{
//计算当前排列顺序所需要建造的线路长
	int res=0;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=3;++j)
				res+=abs(pos[i]-pos[a[i][j]]);
	return res>>1;
}
void solve()
{
//模拟退火算法
	double T=6000;   //参数
	while(T>1e-16){
		int x=rand()%n+1;
		int y=rand()%n+1;
		swap(pos[x],pos[y]);
		int Num=calc();
		if(Num<ans)
			ans=Num;
		else if(exp(ans-Num)/T<double(rand())/RAND_MAX) //Metroplis准则
			swap(pos[x],pos[y]);
		T*=h;
	}
}
void work()
{
//60次模拟退火
	for(int i=1;i<=60;++i)
		solve();
	printf("%d\n",ans);
}
int main()
{
	srand(time(0));
	//time(0)用于获取当前时间值，srand（初始化随机数种子）
	//计算机产生随机数是模拟出来的，如果不更改种子，那么每次运行的结果都是一样的
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i][1]);
		scanf("%d",&a[i][2]);
		scanf("%d",&a[i][3]);
		pos[i]=i;
	}
	ans=0x3f3f3f3f;
	work();
	return 0;
}