浙江财经大学
信息管理与工程学院

旅行商问题(模拟退火非最优解)

本文由 Ocrosoft 于 2016-12-21 22:24:27 发表

即旅行商问题(Traveling Salesperson Problem)。该问题给定n个城市和两两城市之间的距离,要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为:给定图G=(V, A),其中V为顶点集,A为各顶点相互连接组成的边集,已知各顶点间的连接距离,要求确定一条长度最短的回路,即遍历所有顶点当且仅当一次的最短回路。

好像说一般用的是遗传算法,不过这次用模拟退火,学习一下也是不错的。

模拟退火是近似最优解,不一定能得到全局最优解。

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define rep(a,v,b) for(int a=v;a<b;a++)
#define repe(a,v,b) for(int a=v;a<=b;a++)
#define pre(a,v,b) for(int a=v;a>b;a--)
#define pree(a,v,b) for(int a=v;a>=b;a--)
#define lowbit(x) x&-x
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 27;
const int MOD = 1000000007;
int gcd(int a, int b)
{
	if (!b)return a;
	return gcd(b, a%b);
}
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
/*(◕‿‿◕) 签订契约,成为马猴烧酒吧 (◕‿‿◕)*/
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
using namespace std;
const double MAX = 27.0; //城市数量  
const double INIT_T = 3000; //初始温度  
const double RATE = 0.95; //温度衰减率  
const double FINNAL_T = 1E-10; //终止温度  
const int IN_LOOP = 15000; //内循环次数  
const int LIMIT = 10000; //概率选择上限  
const int FINL_LOOP = 1000; //外层循环  
double DD = 0;
double D_Length[MAXN][MAXN] = { 0 };
/*定义路线结构  */
struct path
{
	int citys[MAXN];
	double length;
}D_BestPath;
/*定义点结构*/
struct point
{
	double x;
	double y;
}D_Point[MAXN];
/*计算点和点之间的距离  */
void point_dist()
{
	for (int i = 0; i < MAXN; i++)
		for (int j = i + 1; j < MAXN; j++)
			D_Length[i][j]=D_Length[j][i] = sqrt((D_Point[i].x - D_Point[j].x)*(D_Point[i].x - D_Point[j].x) + (D_Point[i].y - D_Point[j].y)*(D_Point[i].y - D_Point[j].y));
}
/*初始化*/
void init()
{
	printf("初始状态路径:");
	D_BestPath.length = 0;
	/*初始顺序经过路径*/
	for (int i = 0; i < MAXN; i++)
	{
		D_BestPath.citys[i] = i;
		printf("%d--", i);
	}
	/*计算路径长度*/
	for (int i = 0; i < MAXN - 1; i++)
		D_BestPath.length += D_Length[i][i + 1];
	printf("\n路径长度为:%.3lf\n\n", D_BestPath.length);
}
/*显示过程*/
void Dprintf(path p)
{
	int i;
	printf("路径是:");
	for (i = 0; i < MAXN; i++)
		printf("%d--", p.citys[i]);
	printf("\n路径长度为:%.3lf\n\n", p.length);
}
/*随机交换*/
path getnext(path p)
{
	path ret = p;
	int x, y;
	/*生成保证不同的x和y*/
	while (1)
	{
		x = (int)(MAX*rand() / (RAND_MAX + 1.0));
		y = (int)(MAX*rand() / (RAND_MAX + 1.0));
		if (x != y)break;
	}
	swap(ret.citys[x], ret.citys[y]);
	ret.length = 0;
	for (int i = 0; i < MAXN - 1; i++)
		ret.length += D_Length[ret.citys[i]][ret.citys[i + 1]];
	DD++;
	return ret;
}
/*模拟退火*/
void sa()
{
	int i, P_L = 0, P_F = 0;;
	path curPath, newPath;
	double T = INIT_T;
	double p, delta;
	srand((int)time(0));
	curPath = D_BestPath;
	while (1)
	{
		for (i = 0; i < IN_LOOP; i++)
		{
			newPath = getnext(curPath);
			delta = newPath.length - curPath.length;
			if (delta < 0)//新路径更优直接接受
			{
				curPath = newPath;
				P_L = P_F = 0;
			}
			else//否则以一定概率接受新路径
			{
				p = (double)(1.0*rand() / (RAND_MAX + 1.0));
				if (exp(delta / T) < 1 && exp(delta / T) > p)
					curPath = newPath;
				P_L++;
			}
			if (P_L > LIMIT)
			{
				P_F++;
				break;
			}
		}
		if (curPath.length < newPath.length)D_BestPath = curPath;
		if (P_F > FINL_LOOP || T < FINNAL_T)break;
		T = T * RATE;
	}
}
void main()
{
	/*读入*/
	for (int i = 0; i < MAXN; i++)scanf("%lf%lf", &D_Point[i].x, &D_Point[i].y);
	point_dist();init();sa();Dprintf(D_BestPath);
	printf("\n共测试%.0lf次\n", DD);
}
/*
测试数据
41 94 37 84 53 67 25 62 7 64 2 99 68 58 71 44 54 62 83 69 64 60 18 54 22 60 83 46 91 38 25 38 24 42 58 69 71 71 74 78 87 76 18 40 13 40 82 7 62 32 58 35 45 21
*/

欢迎分享与转载,请保留链接与出处。Ocrosoft » 旅行商问题(模拟退火非最优解)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址