程序设计中,有一种特殊的程序——递归程序,递归程序是直接调用自己或通过一系列的过程间接调用自己的程序。
递归程序在程序设计中经常出现,因此应该学会使用递归程序求解问题,但递归程序运行的效率一般都比较低,因此应对递归程序进行优化。
下面结合旅行家问题谈谈递归的优化。
一.递归程序的实现
旅行家问题如下:旅行家要旅行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):
方案
问题规模
仅用citiesToured
引入distance改进getLength
引入touredLength,去除getLength
引入shortestDistance
N=10
1850毫秒
390毫秒
100毫秒
不足1毫秒
N=12
220000毫秒
48200毫秒
1000毫秒
100毫秒
从以上数据可以得出结论:递归程序一般都有很大的优化空间,递归程序经过优化后,可以在很大程度上提高程序的效率。经过优化的程序既保留了递归程序简单易读的特点,又在一定程度上弥补了程序时间效率低的不足。
同时,也可以看出递归程序的先天缺陷,在现实中大规模的旅行商问题递归程序是无法解决的(在可以接受的时间内),普遍采用的是遗传算法来解决,因此应事先决定是否采用递归程序来解决自己的问题。即使如此,本文对于可以应用的递归程序来讲也具有一定的参考意义。
分享到:
相关推荐
在给定的资源“Java语言TSP递归程序的优化.rar”中,我们关注的是如何使用Java优化TSP的递归解决方案。 递归方法通常用于解决TSP问题的一个子问题,即寻找最小生成树(Minimum Spanning Tree, MST)。例如,可以...
《旅行商问题(TSP)的递归Java实现解析》 旅行商问题(Traveling Salesman Problem,简称TSP)是图论中的一个经典问题,它描述了一个旅行商需要访问多个城市,每个城市只能访问一次,并且最后返回出发城市,求解...
压缩包内的文件"Java语言TSP递归程序的优化.doc"很可能是详细的程序实现和优化策略的文档,可能包括算法描述、伪代码、时间复杂度分析等内容。而"www.pudn.com.txt"可能是一个链接或引用信息,指向更多相关资源或...
TSP递归程序可能会使用深度优先搜索(DFS)或广度优先搜索(BFS)等算法,通过递归地探索所有可能的路径组合,来找出最小总距离的路径。 文件"yKtsp递归程序实现(Java).txt"很可能是Java代码的文本文件,包含了实现...
旅行商问题 (Traveling Salesman Problem, TSP) 是一个经典的组合优化问题,主要关注的是寻找一条访问一系列地点并返回出发地的最短路径。在这个问题中,旅行商需要访问的所有地点被称为“城市”,而连接这些城市的...
在文件名“tsp.java”中,我们可以推测这是一个Java程序,它实现了遗传算法来解决旅行商问题。Java是一种广泛使用的面向对象的编程语言,具有跨平台的特性,适合开发这样的算法应用。 在详细说明这个Java程序时,...
根据提供的文件信息,本文将重点解析旅行商问题(Traveling Salesman Problem,简称TSP)与Java中的解决方案,同时简要介绍最大子段和问题及其解决方法。 ### 一、最大子段和问题 #### 1.1 问题定义 最大子段和...
8. **组合优化**:如旅行商问题(TSP)和背包问题,这些都是在计算网络中常见的优化问题,可以应用遗传算法、动态规划等方法求解。 通过深入学习这门课程,学生不仅可以掌握离散数学的基本概念,还能理解如何将这些...
程序中定义了一个城市间的距离矩阵,并使用递归方式遍历所有可能的路径组合,通过 `tsp` 方法来计算和打印出每个可能路径及其总距离。 #### 七、结论 旅行商问题不仅是计算机科学和运筹学领域的一个重要问题,而且...
同时,也可以学习到如何在C语言环境中实现这种复杂的算法,包括数据结构的设计和递归函数的编写技巧。 总的来说,回溯法在解决旅行商问题时,虽然不能保证找到全局最优解,但能够在有限的时间内找到相当接近最优解...
实验报告应包括问题描述、系统总体设计、算法和数据结构设计、C语言程序实现、程序测试及结果分析和复杂度分析。报告格式需遵循学校要求,如使用A4纸张、Times New Roman字体等,且需提交纸质版和电子版(光盘)。
旅行推销员问题(Travelling Salesman Problem,TSP)是一个经典的组合优化问题,它在图论和运筹学领域有着广泛的研究。该问题描述了一个旅行推销员需要访问多个城市,每个城市只访问一次,并在最后返回出发城市,...
- **最优化问题**:寻找最优解决方案,如旅行商问题(TSP)、背包问题等。 综上所述,算法设计与分析不仅涉及到基本概念的理解,还需要掌握多种设计方法和分析技术,以便能够针对不同类型的实际问题提出高效、可靠的...
例如,一个常见的问题可能是要求你在限制时间内找到数组中的最大值或最小值,或者要求你解决旅行商问题(TSP)这样的经典组合优化问题。 对于BaekJoon中的Java解题,开发者需要熟悉以下关键概念和技巧: 1. **基础...
同时,对于Java程序,还可以通过多线程、并行计算等方式提高计算效率。 总的来说,这个项目为理解和解决旅行推销员问题提供了一个实践平台,通过Java实现,让读者能够深入理解这两种算法的原理和应用。对于希望在...