分享
 
 
 

TSP递归程序的优化

王朝other·作者佚名  2008-05-31
窄屏简体版  字體: |||超大  

程序设计中,有一种非凡的程序??递归程序,递归程序是直接调用自己或通过一系列的过程间接调用自己的程序。递归程序在程序设计中经常出现,因此应该学会使用递归程序求解问题,但递归程序运行的效率一般都比较低,因此应对递归程序进行优化。

下面结合旅行家问题谈谈递归的优化。

一.递归程序的实现

旅行家问题如下:旅行家要旅行N个城市,要求各个城市经历且仅经历一次,并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题,是有名的N?P难题之一。在N很大时,并不采用本文所用的递归遍历方法,而是采用其他方法,如神经网络、遗传算法等,得到问题的解。

要得到N个城市依次经历的最短路径,应把各个对N个城市的经历所经过的路程相比较,选出其中的最小值作为返回结果。

用递归程序解决旅行家问题时,思路与循环方法一样:找出各种可能的经历顺序,比较在各个顺序下所走的路程,从中找出最短路程所对应的经历顺序。该问题中如何通过递归得到对所有可能路径的经历应作为重点,而对路程的计算、比较、更新与循环方法类似。在该问题的递归调用中,第n对第n-1层传递过来的已经经历的城市进行判定,以决定是否已经遍历,假如N个城市已经遍历,则计算、比较、更新路程,然后向上一层返回;假如没有遍历,则选择一个未经历的城市加入已经历的城市并一同传递给第n+1层。在这里,第n层调用传入的参数可以看成已经经历的城市和已确定的最短路程,返回的结果可以看成经更新的最短路程与经历顺序。

在Java中定义一个类

ClassCities

{

privateint[][]cities;//各城市表示为(X,Y)X,Y为0到99之间的值

privateint[]shortestPath;//保存最短路程对应的经历顺序

privateintnum;//保存N(城市个数)

privatelongshortestLength=100000000;//N个城市遍历时可能最大路程

privatelonggetLength(int[]tPath){...}//计算以tPath为经历顺序的路程

publicCities(intn)//构造n个城市的坐标,假设为0到99之间的随机数

{

...

}

publicint[]getShortestPath()//获得最短路径

{

int[]tempPath=newint[num];

shortestPath=newint[num];

int[]citiesToured=newint[num];//保存第I个城市是否已经经历

intcitiesNum=0;//已经经历城市的个数

for(inti=0;i<num;i++)

citiesToured[i]=0;

goThrough(tempPath,citiesNum,citiesToured);//遍历各城市

for(inti=0;i<num;i++)

tempPath[i]=shortestPath[i];//得到遍历顺序

returntempPath;//返回结果

}

privatevoidgoThrough(int[]tPath,intcNum,int[]cToured)//遍历N个城市

{

if(cNum==0)//无经历城市时,选择第1个城市

{

cNum++;

tPath[0]=0;

cToured[0]=1;

goThrough(tPath,cNum,cToured);

}

elseif(cNum==num)//各个城市已经经历,结束

{

longtempLength=getLength(tPath);//计算此经历顺序所走的路程

if(tempLength<shortestLength)//比较路程

{

shortestLength=tempLength;//更新最短路程及其经历顺序

for(inti=0;i<num;i++)

shortestPath[i]=tPath[i];

}

}

else

{

for(inti=0;i<num;i++)

if(cToured[i]!=1)//选择未经历的城市

{

cToured[i]=1;//加入已经历城市

tPath[cNum]=i;

cNum++;//已经历城市个数+1

goThrough(tPath,cNum,cToured);//调用下一层

cToured[i]=0;//恢复本层的状态:

cNum--;//已经历城市及个数

}//Endifinfor(i)

}//Endelse

}

privatelonggetLength(int[]tPath)//以指定顺序计算遍历路程

{

longlength=0;//路程

intnowPoint=0;//当前城市,第一次取0

for(inti=1;i<num;i++)

{

intj=tPath[i];

length+=(long)Math.sqrt((cities[j][0]-cities[nowPoint][0])*(cities[j][0]-cities[nowPoint][0])+(cities[j][1]-cities[nowPoint][1])*(cities[j][1]-cities[nowPoint][1]));//加上当前、下一城市间的距离

nowPoint=j;//更新当前城市

}

length+=(long)Math.sqrt((cities[0][0]-cities[nowPoint][0])*(cities[0][0]-cities[nowPoint][0])+(cities[0][1]-cities[nowPoint][1])*(cities[0][1]-cities[nowPoint][1]));//加上首尾城市间的距离

returnlength;

}

}//Cities类定义结束

在这里使用递归,实现了对N可变时问题的求解。

三.递归程序的优化

递归程序的优化是程序优化的一种,具有程序优化的一般性,同时更应考虑它的非凡性。递归程序优化中应主要着眼尽快结束递归,避免无谓的调用,因为结束得越早,程序所付出的代价就越小。

在旅行家问题中,对城市的遍历goThrough函数是递归程序,下面讨论对它的优化。

Ⅰ.该问题的第一次优化:各个城市之间的距离在Cities类构造时就已经确定,而每一次遍历各个城市后,getLength函数都要计算一次相邻两城市及首尾城市间的距离,显然城市间距离的计算只要进行一次就可以了。因此可以定义一个函数InitDistance,在构造函数Cities()中调用,并重新定义getLength函数,直接对相邻及首尾城市的距离取和。如下:

1.类中增加属性privatelong[]distance;//在InitDistance方法中构造

2.定义私有方法privatevoidInitDistance()//计算各个城市之间的距离(由于仅计算一次,故未优化)

privatevoidInitDistance()

{

distance=newlong[num][num];

for(inti=0;i<num;i++)

for(intj=0;j<num;j++)

{

if(i==j)

distance[i][j]=0L;

else

distance[i][j]=(long)Math.sqrt(

(cities[i][0]-cities[j][0])*(cities[i][0]-cities[j][0])+(cities[i][1]-cities[j][1])*(cities[i][1]-cities[j][1]));

}

}

3.重新定义getLength

privatelonggetLength(int[]tPath)

{

longlength=0L;

for(inti=1;i<num;i++)

length+=distance[tPath[i-1]][tPath[i]];

length+=distance[tPath[0]][tPath[num-1]];

returnlength;

}

4.重新定义构造函数Cities(intr)

publicCities(intr)

{...

InitDistance();//计算各个城市间的距离

}

Ⅱ.该问题的第二次优化:考虑下面的情况,经历顺序为1?2?3?4?5?6?与1?2?3?4?6?5?二者中前四个城市经历顺序相同,可以定义一个变量来保存已经历的路程,只有在经历顺序改变的时候才对已经历的路程进行更新。进行如下优化:

1.增加privatelongtouredLength属性并初始化为0,用来记录到“目前”为止所经历的路程。

2.重新定义goThrough

privatevoidgoThrough(int[]tPath,intcNum,int[]cToured)

{

...//同上

elseif(cNum==num)

{

longtL=touredLength+distance[tPath[num-1]][tPath[0]];▲//tL记录已经历的路程

(用▲标志改进点,下同)

if(tL<shortestLength)

{

shortestLength=tL;

for(inti=0;i<num;i++)

shortestPath[i]=tPath[i];

}

}

else//0<citiesNum<N

{

for(inti=0;i<num;i++)

if(cToured[i]!=1)//NotToured

{

tPath[cNum]=I;

cToured[i]=1;

touredLength+=distance[tPath[cNum-1]][i];▲

cNum++;

goThrough(tPath,cNum,cToured);

cNum--;

touredLength-=distance[tPath[cNum-1]][i];▲

cToured[i]=0;

}

}

}

3.去除getLength。

Ⅲ.该问题的第二次优化:进一步考虑对路程的计算,设想下面的情况:N=5,已经历了2个城市,且旅行路程为200,目前已知的最短路程为260,而其他三个城市的任意两个城市之间的距离大于30。在这种情况下,再继续遍历只是徒劳,此时就可以结束调用返回。针对这种情况,如下优化:

1.增加属性privatelongshortestDistance[],来保存城市之间的最短距离,次最短距离,次次最短距离,...,并在InitDistance中得到各距离的值。

privatevoidInitDistance()

{

...

shortestDistance=newlong[num+1];

shortestDistance[0]=0;

for(inti=0;i<num;i++)

{

longdis=10000L;

for(intj=i+1;j<num;j++)

if(distance[i][j]<dis)

dis=distance[i][j];

shortestDistance[i+1]=shortestDistance[i]+dis;

}

}

2.更新goThrough

privatevoidgoThrough(int[]tPath,intcNum,int[]cToured)

{

...

elseif(cNum==num)

{

longtL=touredLength+distance[tPath[num-1]][tPath[0]];

if(tL<shortestLength)

{

shortestLength=tL;

for(inti=0;i<num;i++)

shortestPath[i]=tPath[i];

}

}

else//0<citiesNum<num

{

if(touredLength+shortestDistance[num-cNum]<shortestLength)▲

//假如已经历的路程+可能的最短路程>已知的最短路程,则不再继续走下去

{

for(inti=0;i<num;i++)

if(cToured[i]!=1)//NotToured

{

tPath[cNum]=i;

cToured[i]=1;

touredLength+=distance[tPath[cNum-1]][i];

cNum++;

goThrough(tPath,cNum,cToured);

cNum--;

touredLength-=distance[tPath[cNum-1]][i];

cToured[i]=0;

}

}

}

}

比较各种优化方法的求解时间,得到下表的数据(Windows98,PIII550,128M):

方案 问题规模 N=10 N=12

仅用citiesToured 1850毫秒 220000毫秒

引入distance改进getLength 390毫秒 48200毫秒

引入touredLength,去除getLength 100毫秒 1000毫秒

引入shortestDistance 不足1毫秒 100毫秒

从以上数据可以得出结论:递归程序一般都有很大的优化空间,递归程序经过优化后,可以在很大程度上提高程序的效率。经过优化的程序既保留了递归程序简单易读的特点,又在一定程度上弥补了程序时间效率低的不足。

同时,也可以看出递归程序的先天缺陷,在现实中大规模的旅行商问题递归程序是无法解决的(在可以接受的时间内),普遍采用的是遗传算法来解决,因此应事先决定是否采用递归程序来解决自己的问题。即使如此,本文对于可以应用的递归程序来讲也具有一定的参考意义。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有