Java语言TSP递归程序的优化

类别:Java 点击:0 评论:0 推荐:

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

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

一.递归程序的实现

       旅行家问题如下:旅行家要旅行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可变时问题的求解。

三.递归程序的优化

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

在旅行家问题中,对城市的遍历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<num; i++)

           for(int j=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

private long getLength(int[] tPath)

{

long  length = 0L;

for(int i=1;i<num; 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();                                 //计算各个城市间的距离

  }

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

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<num; i++)

                       shortestPath[i] = tPath[i];

}

}

else                                     // 0< citiesNum <N

{

               for(int i=0; i<num; 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<num; i++)

    {

            long dis = 10000L;

        for(int j=i+1; j<num; 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<num; i++)

                    shortestPath[i] = tPath[i];

         }

}

    else                  // 0< citiesNum <num

    {

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

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

        {

                for(int i=0; i<num; 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=10

1850毫秒

390毫秒

100毫秒

不足1毫秒

N=12

220000毫秒

48200毫秒

1000毫秒

100毫秒

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

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

本文地址:http://com.8s8s.com/it/it17036.htm