Java语言TSP递归程序的优化

1/5/2008来源:Java教程人气:4537


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

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

  一.递归程序的实现

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

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

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

  在java中定义一个类

Class Cities

{

PRivate int[][] cities; //各城市表示为(X,Y)X,Y为0到99之间的值
private int[] shortestPath; //保存最短路程对应的经历顺序
private int num; //保存N(城市个数)
private long shortestLength = 100000000;//N个城市遍历时可能最大路程
private long getLength(int[] tPath) {...} //计算以tPath为经历顺序的路程
public Cities(int n) //构造n个城市的坐标,假设为0到99之间的随机数
{
...
}
public int[] getShortestPath() //获得最短路径
{
int[] tempPath = new int[num];
shortestPath = new int[num];
int[] citiesToured = new int[num]; //保存第I个城市是否已经经历
int citiesNum = 0; //已经经历城市的个数
for(int i=0; i<num; i++)
citiesToured[i] = 0;
goThrough(tempPath, citiesNum, citiesToured);//遍历各城市
for(int i=0; i<num; i++)
tempPath[i] = shortestPath[i]; //得到遍历顺序
return tempPath; //返回结果
}

private void goThrough(int[] tPath, int cNum, int[] cToured) //遍历N个城市
{
if (cNum == 0) //无经历城市时,选择第1个城市
{
cNum++;
tPath[0] = 0;
cToured[0] = 1;
goThrough(tPath, cNum, cToured);
}
else if (cNum == num) //各个城市已经经历,结束
{
long tempLength = getLength(tPath);//计算此经历顺序所走的路程
if (tempLength < shortestLength) //比较路程
{
shortestLength = tempLength; //更新最短路程及其经历顺序
for(int i=0; i<num; i++)
shortestPath[i] = tPath[i];
}
}
else
{
for(int i=0; i<num; i++)
if (cToured[i] != 1) //选择未经历的城市
{
cToured[i] = 1; //加入已经历城市
tPath[cNum]= i;
cNum++; //已经历城市个数+1
goThrough(tPath, cNum, cToured);//调用下一层
cToured[i] = 0; //恢复本层的状态:
cNum--; //已经历城市及个数
} //End if in for(i)
} //End else
}

private long getLength(int[] tPath) //以指定顺序计算遍历路程
{
long length = 0; //路程
int nowPoint = 0; //当前城市,第一次取0
for(int i=1; i<num; i++)
{
int j = 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]));//加上首尾城市间的距离
return length;
}
} // Cities类定义结束
  在这里使用递归,实现了对N可变时问题的求解。
  二.递归程序的优化

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