基于回溯法的TSP问题解决方案,附有TSP问题相关的c++和matlab解法资料,及工程文件(西电02105143)
代码片段和文件信息
属性 大小 日期 时间 名称
----------- --------- ---------- ----- ----
文件 149079 2012-12-13 23:46 算法大作业TSP 2105143周萌(TSP问题).pdf
文件 305085 2006-05-08 21:13 算法大作业TSPc++TSP--传统算法.rar
文件 3802 2009-12-14 17:47 算法大作业TSPc++ sp.cpp
文件 88064 2010-12-01 21:45 算法大作业TSPc++TSPkeepTSP.doc
文件 10404 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程DebugBuildLog.htm
文件 67 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程Debugmt.dep
文件 357376 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程DebugTSP.exe
文件 406 2012-12-09 17:51 算法大作业TSPc++TSPkeepTSP工程DebugTSP.exe.embed.manifest
文件 472 2012-12-09 17:51 算法大作业TSPc++TSPkeepTSP工程DebugTSP.exe.embed.manifest.res
文件 381 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程DebugTSP.exe.intermediate.manifest
文件 173384 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程DebugTSP.ilk
文件 15977 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程DebugTSP.obj
文件 1780736 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程DebugTSP.pdb
文件 33792 2010-12-01 21:50 算法大作业TSPc++TSPkeepTSP工程Debugvc60.idb
文件 45056 2010-12-01 21:48 算法大作业TSPc++TSPkeepTSP工程Debugvc60.pdb
文件 44032 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程Debugvc90.idb
文件 61440 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程Debugvc90.pdb
文件 5574 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程TSP.C
文件 3363 2010-12-01 21:49 算法大作业TSPc++TSPkeepTSP工程TSP.DSP
文件 531 2010-12-01 21:50 算法大作业TSPc++TSPkeepTSP工程TSP.DSW
文件 584704 2012-12-09 21:05 算法大作业TSPc++TSPkeepTSP工程TSP.ncb
文件 53760 2010-12-01 21:52 算法大作业TSPc++TSPkeepTSP工程TSP.OPT
文件 240 2010-12-01 21:49 算法大作业TSPc++TSPkeepTSP工程TSP.PLG
文件 876 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程TSP.sln
..A..H. 8704 2012-12-09 21:05 算法大作业TSPc++TSPkeepTSP工程TSP.suo
文件 4803 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程TSP.vcproj
文件 1405 2012-12-09 21:05 算法大作业TSPc++TSPkeepTSP工程TSP.vcproj.c-PC.c.user
文件 33543 2012-12-09 18:04 算法大作业TSPc++TSPkeep图片1.png
文件 6114 2012-12-09 20:21 算法大作业TSPc++TSPkeep新建文件夹TSP工程DebugBuildLog.htm
文件 67 2012-12-09 20:21 算法大作业TSPc++TSPkeep新建文件夹TSP工程Debugmt.dep
............此处省略119个文件信息
#include
#include
#include
#include
#include
#define PI 3.141592
#define RRR 6378.388
using namespace std;
int n;
double longitude[10001]; //输入的GEO坐标或者XY坐标
double latitude[10001];
int cstep[10001]; //保存当前接受的状态
int nstep[10001]; //保存新扩展的状态
double minvalue; //当前所接受的最短长度
double dis(int iint j) //用于计算两个城市之间的距离
{
//double q1q2q3; //方法一为GEO坐标的距离算法,注释掉的为XY坐标的计算距离算法
// q1 = cos( longitude[i] - longitude[j] );
// q2 = cos( latitude[i] - latitude[j] );
//q3 = cos( latitude[i] + latitude[j] );
//return (int) ( RRR * acos( 0.5*((1.0+q1)*q2 - (1.0-q1)*q3) ) + 1.0);
return sqrt((longitude[i]-longitude[j])*(longitude[i]-longitude[j])+(latitude[i]-latitude[j])*(latitude[i]-latitude[j]));
}
void randomplace() //将初始状态任意交换两个位置得到一个起始状态
{
int changenum;
int xy;
int i;
int temp;
changenum=rand();
while(changenum>n ||changenum<1) changenum=rand();
for(i=1;i<=changenum;i++)
{
x=rand();
while(x>n ||x<1) x=rand();
y=rand();
while(y>n ||y<1 ||x==y) y=rand();
temp=cstep[x]; //按随机数xy交换这两个位置的城市
cstep[x]=cstep[y];
cstep[y]=temp;
}
}
void change(int state[]) //随机将状态中从x到y步的城市逆序
{
int xy;
int temp;
x=rand();
while(x>n ||x<1) x=rand();
y=rand();
while(y>n ||y<1 ||x==y) y=rand();
reverse(state+xstate+y);
}
double compute(int state[]) //计算当前状态的距离的和
{
int i;
double value;
value=0;
for(i=2;i<=n;i++)
{
value+=dis(state[i]state[i-1]);
}
value+=dis(state[1]state[n]);
return value;
}
int main()
{
ifstream input;
ofstream output;
int ij;
int count;
clock_t startfinish;
double temperature; //模拟退火的温度
double templtempg;
double mindeg; //中间值的保存
int receive; //用于保存在每个温度下所接受状态的数目
double newvalue; //保存新扩展出的距离和
double prevalue;
srand((unsigned)time(NULL));
input.open(“tsp2.in“ios::in);
input >>n;
for(i=1;i<=n;i++) //读入距离
{
input >>j;
input >>templ;
input >>tempg;
//deg=(int)templ;
//min=templ-deg;
//longitude[i]=PI * (deg + 5.0 * min/ 3.0) / 180.0;
//deg=(int)tempg;
//min=tempg-deg;
// latitude[i]=PI * (deg + 5.0 * min/ 3.0) / 180.0;
cstep[i]=i;
longitude[i]=templ;
latitude[i]=tempg;
}
input.close();
for(int t=1;t<=10;t++)
{
start=clock();
temperature=280; //将初始温度设为280度
randomplace();
minvalue=compute(cstep); //计算初始状态的距离和
prevalue=0;
while(1)
{
count=0;
if(temperature<0.01 ) break; //若温度小于0.01度随即结束搜索
receive=0;
while(1)
{
if(count>100*n) break; //每个温度下只扩展100*n次
count++;
for(i=1;i<=n;i++)
{
nstep[i]=cstep[i];
}
change(nstep);
newvalue=compute(nstep);
if(newvalue {
for(i=1;i<=n;i++)
{
cstep[i]=nstep[i];
}
minvalue=newvalue;
receive++;
}
else
{
double com; //否则按一定的概率接受该解
com=rand();
whil
属性 大小 日期 时间 名称
----------- --------- ---------- ----- ----
文件 149079 2012-12-13 23:46 算法大作业TSP 2105143周萌(TSP问题).pdf
文件 305085 2006-05-08 21:13 算法大作业TSPc++TSP--传统算法.rar
文件 3802 2009-12-14 17:47 算法大作业TSPc++ sp.cpp
文件 88064 2010-12-01 21:45 算法大作业TSPc++TSPkeepTSP.doc
文件 10404 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程DebugBuildLog.htm
文件 67 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程Debugmt.dep
文件 357376 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程DebugTSP.exe
文件 406 2012-12-09 17:51 算法大作业TSPc++TSPkeepTSP工程DebugTSP.exe.em
文件 472 2012-12-09 17:51 算法大作业TSPc++TSPkeepTSP工程DebugTSP.exe.em
文件 381 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程DebugTSP.exe.intermediate.manifest
文件 173384 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程DebugTSP.ilk
文件 15977 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程DebugTSP.obj
文件 1780736 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程DebugTSP.pdb
文件 33792 2010-12-01 21:50 算法大作业TSPc++TSPkeepTSP工程Debugvc60.idb
文件 45056 2010-12-01 21:48 算法大作业TSPc++TSPkeepTSP工程Debugvc60.pdb
文件 44032 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程Debugvc90.idb
文件 61440 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程Debugvc90.pdb
文件 5574 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程TSP.C
文件 3363 2010-12-01 21:49 算法大作业TSPc++TSPkeepTSP工程TSP.DSP
文件 531 2010-12-01 21:50 算法大作业TSPc++TSPkeepTSP工程TSP.DSW
文件 584704 2012-12-09 21:05 算法大作业TSPc++TSPkeepTSP工程TSP.ncb
文件 53760 2010-12-01 21:52 算法大作业TSPc++TSPkeepTSP工程TSP.OPT
文件 240 2010-12-01 21:49 算法大作业TSPc++TSPkeepTSP工程TSP.PLG
文件 876 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程TSP.sln
..A..H. 8704 2012-12-09 21:05 算法大作业TSPc++TSPkeepTSP工程TSP.suo
文件 4803 2012-12-09 20:32 算法大作业TSPc++TSPkeepTSP工程TSP.vcproj
文件 1405 2012-12-09 21:05 算法大作业TSPc++TSPkeepTSP工程TSP.vcproj.c-PC.c.user
文件 33543 2012-12-09 18:04 算法大作业TSPc++TSPkeep图片1.png
文件 6114 2012-12-09 20:21 算法大作业TSPc++TSPkeep新建文件夹TSP工程DebugBuildLog.htm
文件 67 2012-12-09 20:21 算法大作业TSPc++TSPkeep新建文件夹TSP工程Debugmt.dep
............此处省略119个文件信息
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件举报,一经查实,本站将立刻删除。
评论列表(条)