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

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

  程序设计中,有一种非凡的程序——递归程序,递归程序是直接调用自己或通过一系列的过程间接调用自己的程序。

递归程序在程序设计中经常出现,因此应该学会使用递归程序求解问题,但递归程序运行的效率一般都比较低,因此应对递归程序进行优化。

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

  一.递归程序的实现

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