Java语言TSP递归程序的优化
程序设计中，有一种特殊的程序递归程序，递归程序是直接调用自己或通过一系列的过程间接调用自己的程序。递归程序在程序设计中经常出现，因此应该学会使用递归程序求解问题，但递归程序运行的效率一般都比较低，因此应对递归程序进行优化。
下面结合旅行家问题谈谈递归的优化。
一．递归程序的实现
旅行家问题如下：旅行家要旅行N个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是有名的NP难题之一。在N很大时，并不采用本文所用的递归遍历方法，而是采用其他方法，如神经网络、遗传算法等，得到问题的解。
要得到N个城市依次经历的最短路径，应把各个对N个城市的经历所经过的路程相比较，选出其中的最小值作为返回结果。
用递归程序解决旅行家问题时，思路与循环方法一样：找出各种可能的经历顺序，比较在各个顺序下所走的路程，从中找出最短路程所对应的经历顺序。该问题中如何通过递归得到对所有可能路径的经历应作为重点，而对路程的计算、比较、更新与循环方法类似。在该问题的递归调用中，第n对第n-1层传递过来的已经经历的城市进行判断，以决定是否已经遍历，如果N个城市已经遍历，则计算、比较、更新路程，然后向上一层返回；如果没有遍历，则选择一个未经历的城市加入已经历的城市并一同传递给第n+1层。在这里，第n层调用传入的参数可以看成已经经历的城市和已确定的最短路程，返回的结果可以看成经更新的最短路程与经历顺序。
在Java中定义一个类
在这里使用递归，实现了对N可变时问题的求解。
二．递归程序的优化
递归程序的优化是程序优化的一种，具有程序优化的一般性，同时更应考虑它的特殊性。递归程序优化中应主要着眼尽快结束递归，避免无谓的调用，因为结束得越早，程序所付出的代价就越小。
在旅行家问题中，对城市的遍历goThrough函数是递归程序，下面讨论对它的优化。
Ⅰ．该问题的第一次优化：各个城市之间的距离在Cities类构造时就已经确定，而每一次遍历各个城市后，getLength函数都要计算一次相邻两城市及首尾城市间的距离，显然城市间距离的计算只要进行一次就可以了。因此可以定义一个函数InitDistance，在构造函数Cities()中调用，并重新定义getLength函数，直接对相邻及首尾城市的距离取和。如下：
1．类中增加属性private long[] distance； //在InitDistance方法中构造
2．定义私有方法 private void InitDistance() //计算各个城市之间的距离（由于仅计算一次，故未优化）
private void InitDistance()
{
distance = new long[num][num];
for(int i=0；i for(int j=0；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 private long getLength(int[] tPath) { long length = 0L； for(int i=1；i length += distance[tPath[i-1]][tPath[i]]； length += distance[tPath[0]][tPath[num-1]]； return length； } 4．重新定义构造函数Cities(int r) public Cities(int r) {．．． InitDistance()； //计算各个城市间的距离 } Ⅱ．该问题的第二次优化：考虑下面的情况，经历顺序为123456与123465二者中前四个城市经历顺序相同，可以定义一个变量来保存已经历的路程，只有在经历顺序改变的时候才对已经历的路程进行更新。进行如下优化： 1．增加private long touredLength属性并初始化为0，用来记录到“目前”为止所经历的路程。 2．重新定义goThrough private void goThrough(int[] tPath, int cNum, int[] cToured) { ．．． // 同上 else if (cNum == num) { long tL = touredLength + distance[tPath[num-1]] [tPath[0]]；▲// tL记录已经历的路程 （用▲标志改进点，下同） if (tL < shortestLength) { shortestLength = tL； for(int i=0; i shortestPath[i] = tPath[i]； } } else // 0< citiesNum { for(int i=0； i if (cToured[i] != 1) //Not Toured { 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．增加属性 private long shortestDistance[]，来保存城市之间的最短距离，次最短距离，次次最短距离，．．．，并在InitDistance中得到各距离的值。 private void InitDistance() { ．．． shortestDistance = new long[num +1]； shortestDistance[0] = 0； for(int i=0； i { long dis = 10000L； for(int j=i+1； j if (distance[i][j] < dis) dis = distance[i][j]； shortestDistance[i+1] = shortestDistance[i] + dis； } } 2．更新goThrough private void goThrough(int[] tPath, int cNum, int[] cToured) { ．．． else if (cNum == num) { long tL = touredLength + distance[tPath[num-1]] [tPath[0]]； if (tL < shortestLength) { shortestLength = tL； for(int i=0； i shortestPath[i] = tPath[i]； } } else // 0< citiesNum { if (touredLength + shortestDistance[num - cNum] < shortestLength) ▲ //如果已经历的路程+可能的最短路程>已知的最短路程，则不再继续走下去 { for(int i=0； i if (cToured[i] != 1) //Not Toured { 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； } } } } 比较各种优化方法的求解时间，得到下表的数据（Windows 98，PIII550，128M）： 方案仅用citiesToured引入distance改进getLength引入touredLength,去除getLength引入shortestDistance 问题规模 N=101850毫秒390毫秒100毫秒不足1毫秒 N=12220000毫秒48200毫秒1000毫秒100毫秒 从以上数据可以得出结论：递归程序一般都有很大的优化空间，递归程序经过优化后，可以在很大程度上提高程序的效率。经过优化的程序既保留了递归程序简单易读的特点，又在一定程度上弥补了程序时间效率低的不足。 同时，也可以看出递归程序的先天缺陷，在现实中大规模的旅行商问题递归程序是无法解决的（在可以接受的时间内），普遍采用的是遗传算法来解决，因此应事先决定是否采用递归程序来解决自己的问题。即使如此，本文对于可以应用的递归程序来讲也具有一定的参考意义。
查看评论 回复