Java学习:TSP递归程序的优化

核心提示：程序设计中，有一种非凡的程序——递归程序，Java学习:TSP递归程序的优化，递归程序是直接调用自己或通过一系列的过程间接调用自己的程序，

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

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

一．递归程序的实现

旅行家问题如下：旅行家要旅行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]；