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

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

```#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
*/```