/*********************************************************************
模拟退火算法解决TSP问题
*********************************************************************/
/*********************************************************************
输入格式(城市坐标.in)：
第行:1个整数N，表示城市的数量
第..N+1行：每行有个空格分开的整数x,y，第i+1行的x,y表示城市i的坐标
***********************************************************************/
#include <iostream>
#include <cmath>
#include <time.h>
using namespace std;
const int MAXN = 501; //最大城市数
const double INIT_T =2000; //初始温度
const double RATE = 0.95; //温度衰减率
const double FINAL_T = 1E-10; //终止温度
const int IN_LOOP = 13000; //内层循环次数
const int OUT_LOOP = 2000; //外层循环次数
const int P_LIMIT = 10000; //概率选择次数
struct path { //定义路径结构类型
int City[MAXN]; //依次遍历的城市的序号
double Length; //所有城市的路径总长度
};
int N; //城市数量
double D[MAXN][MAXN]; //任意两个城市之间的距离
path bestpath; //最优的遍历路径
inline double dist(int x1, int y1, int x2, int y2) //计算两点之间的距离
{
return sqrt(double((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)));
}
inline double totaldist(path p) //计算遍历路径P的总长度
{
int i;
double cost = 0;
for (i=1; i<N; i++)
{
cost += D[p.City[i]][p.City[i+1]];
}
cost += D[p.City[1]][p.City[N]];
return cost;
}
void init() //读入数据，并初始化
{
int C[MAXN][2]; //城市的坐标
int i, j;
freopen("城市坐标.in", "r", stdin);
//freopen("结果输出.out", "w", stdout);
scanf("%d", &N);
for (i=1; i<=N; i++)
scanf("%d%d", &C[i][0], &C[i][1]);
for (i=1; i<N; i++) //计算任意两个城市之间的路径长度
for (j=i+1; j<=N; j++)
{
D[i][j] = D[j][i] = dist(C[i][0], C[i][1], C[j][0], C[j][1]);
}
for (i=1; i<=N; i++) //最优解的初始状态
bestpath.City[i] = i;
bestpath.Length = totaldist(bestpath);
srand((unsigned)time(NULL));
}
/************************************************************
产生新路径方法
*************************************************************/
path getnext(path p) //新解产生函数
{
int x, y;
path ret;
ret = p;
do {
x = rand() % N + 1;
y = rand() % N + 1;
}while(x == y);
swap(ret.City[x], ret.City[y]); //交换两城市之间位置顺序
ret.Length = totaldist(ret);
return ret;
}
/****************************************************************
退火和降温过程
******************************************************************/
void sa()
{
double T; //温度
path newpath, curpath; //当前路径和新路径
int i, P_t=0, A_t=0;
double delta;
T = INIT_T; //赋值初始温度
curpath = bestpath;
while(true)
{
for (i=1; i<=IN_LOOP; i++)
{
newpath = getnext(curpath); //获取新路径
delta = newpath.Length - curpath.Length;
if (delta < 0.0)
{
curpath = newpath;
P_t = 0;
A_t = 0;
}
else
{
double rnd = rand()%10000 /10000.0;
double p = exp(-delta/T);
if (p > rnd)
curpath = newpath;
P_t++;
}
if (P_t >=P_LIMIT)
{
A_t++;
break;
}
}
if (curpath.Length<bestpath.Length)
bestpath = curpath;
if ( A_t >= OUT_LOOP || T < FINAL_T) break;
T = T * RATE; //降温
}
}
/****************************************************************
程序主函数
******************************************************************/
int main()
{
init();
printf("初始路径长度: %.4f\n", bestpath.Length);
for(int i=0;i<N;)
{
printf(" %d->", bestpath.City[++i]);
}
printf(" %d", bestpath.City[1]);
printf("\n");
sa();
printf("最优路径长度: %.4f\n", bestpath.Length);
for(int j=0;j<N;)
{
printf(" %d->", bestpath.City[++j]);
}
printf(" %d", bestpath.City[1]);
printf("\n");
return 0;
}
评论0