当前页面: 开发资料首页 → Java 专题 → Java语言TSP递归程序的优化
Java语言TSP递归程序的优化
摘要: 程序设计中，有一种特殊的程序——递归程序，递归程序是直接调用自己或通过一系列的过程间接调用自己的程序
<body bgcolor="#FFFFFF" text="#000000"> <table width="570" border="0" cellspacing="0" cellpadding="5" bgcolor="FBE392"> <tr> <td> <table width="570" border="0" cellspacing="0" cellpadding="5"> <tr> <td bgcolor="E1B004" width="200" align="center">天极IT资讯短信服务 电脑小技巧
<table width="100%" border="0" cellspacing="0" cellpadding="3" bgcolor="fffcc0"> function check4() { if (dn.mobile.value.length!=11) { alert("手机号码不正确!"); dn.mobile.focus(); return false; } return true; } <form name=dn action="http://www.my5757.com/tj/join.jsp" target=_blank onSubmit="return check4()"> <tr valign=middle> <td>资费：包月5元
手机： <input type=text name=mobile size=11 style="border:1px solid #000000;height=16px"> <input type=image src="http://www.my5757.com/yesky/images/d34.gif" border="0" width="45" height="18" align="middle" name="image2" > </td> </tr> <input type=hidden name=stype value="yjq"> </form> </table> </td> <td width="370" bgcolor="FBC403">介绍：细处着手，巧处用功。高手和菜鸟之间的差别就是：高手什么都知道，菜鸟知道一些。电脑小技巧收集最新奇招高招，让你轻松踏上高手之路。(首月免费) </td> </tr> </table> </td> </tr> </table>
程序设计中，有一种特殊的程序——递归程序，递归程序是直接调用自己或通过一系列的过程间接调用自己的程序。递归程序在程序设计中经常出现，因此应该学会使用递归程序求解问题，但递归程序运行的效率一般都比较低，因此应对递归程序进行优化。
下面结合旅行家问题谈谈递归的优化。
<iframe width="360" height="300" align="right"scrolling="No" frameborder="0" marginheight="0" marginwidth="0" SRC="http://images.chinabyte.com/adjs/iframe-pip/y-software-pip.html"></iframe> 一．递归程序的实现
旅行家问题如下：旅行家要旅行N个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是有名的N—P难题之一。在N很大时，并不采用本文所用的递归遍历方法，而是采用其他方法，如神经网络、遗传算法等，得到问题的解。
要得到N个城市依次经历的最短路径，应把各个对N个城市的经历所经过的路程相比较，选出其中的最小值作为返回结果。
用递归程序解决旅行家问题时，思路与循环方法一样：找出各种可能的经历顺序，比较在各个顺序下所走的路程，从中找出最短路程所对应的经历顺序。该问题中如何通过递归得到对所有可能路径的经历应作为重点，而对路程的计算、比较、更新与循环方法类似。在该问题的递归调用中，第n对第n-1层传递过来的已经经历的城市进行判断，以决定是否已经遍历，如果N个城市已经遍历，则计算、比较、更新路程，然后向上一层返回；如果没有遍历，则选择一个未经历的城市加入已经历的城市并一同传递给第n+1层。在这里，第n层调用传入的参数可以看成已经经历的城市和已确定的最短路程，返回的结果可以看成经更新的最短路程与经历顺序。
在Java中定义一个类
<table width="100%" bgColor=#ffffff> <tr> <td>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； icitiesToured[i] = 0；
goThrough(tempPath, citiesNum, citiesToured)；//遍历各城市
for(int i=0； itempPath[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； ishortestPath[i] = tPath[i]；
}
}
else
{
for(int i=0； iif (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{
int j = tPath[i]；
length+=(long)Math.sqrt((cities[j][0]-cities[nowPoin t][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类定义结束 </td></tr> </table>
在这里使用递归，实现了对N可变时问题的求解。
<table width="100%" border="0" cellspacing="0" cellpadding="3" bgcolor="fffcc0"> function check4() { if (dn.mobile.value.length!=11) { alert("手机号码不正确!"); dn.mobile.focus(); return false; } return true; } <form name=dn action="http://www.my5757.com/tj/join.jsp" target=_blank onSubmit="return check4()"> <tr valign=middle> <td>资费：包月5元
手机： <input type=text name=mobile size=11 style="border:1px solid #000000;height=16px"> <input type=image src="http://www.my5757.com/yesky/images/d34.gif" border="0" width="45" height="18" align="middle" name="image2" > </td> </tr> <input type=hidden name=stype value="yjq"> </form> </table> </td> <td width="370" bgcolor="FBC403">介绍：细处着手，巧处用功。高手和菜鸟之间的差别就是：高手什么都知道，菜鸟知道一些。电脑小技巧收集最新奇招高招，让你轻松踏上高手之路。(首月免费) </td> </tr> </table> </td> </tr> </table>
程序设计中，有一种特殊的程序——递归程序，递归程序是直接调用自己或通过一系列的过程间接调用自己的程序。递归程序在程序设计中经常出现，因此应该学会使用递归程序求解问题，但递归程序运行的效率一般都比较低，因此应对递归程序进行优化。
下面结合旅行家问题谈谈递归的优化。
<iframe width="360" height="300" align="right"scrolling="No" frameborder="0" marginheight="0" marginwidth="0" SRC="http://images.chinabyte.com/adjs/iframe-pip/y-software-pip.html"></iframe> 一．递归程序的实现
旅行家问题如下：旅行家要旅行N个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是有名的N—P难题之一。在N很大时，并不采用本文所用的递归遍历方法，而是采用其他方法，如神经网络、遗传算法等，得到问题的解。
要得到N个城市依次经历的最短路径，应把各个对N个城市的经历所经过的路程相比较，选出其中的最小值作为返回结果。
用递归程序解决旅行家问题时，思路与循环方法一样：找出各种可能的经历顺序，比较在各个顺序下所走的路程，从中找出最短路程所对应的经历顺序。该问题中如何通过递归得到对所有可能路径的经历应作为重点，而对路程的计算、比较、更新与循环方法类似。在该问题的递归调用中，第n对第n-1层传递过来的已经经历的城市进行判断，以决定是否已经遍历，如果N个城市已经遍历，则计算、比较、更新路程，然后向上一层返回；如果没有遍历，则选择一个未经历的城市加入已经历的城市并一同传递给第n+1层。在这里，第n层调用传入的参数可以看成已经经历的城市和已确定的最短路程，返回的结果可以看成经更新的最短路程与经历顺序。
在Java中定义一个类
<table width="100%" bgColor=#ffffff> <tr> <td>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
goThrough(tempPath, citiesNum, citiesToured)；//遍历各城市
for(int i=0； 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
}
}
else
{
for(int i=0； i
{
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
int j = tPath[i]；
length+=(long)Math.sqrt((cities[j][0]-cities[nowPoin t][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类定义结束 </td></tr>
在这里使用递归，实现了对N可变时问题的求解。
↑返回目录
前一篇: 再论Java Swing线程
后一篇: 用Delphi客户端访问EJB组件