上一页 1 2 3 4 5 下一页

　
　　Ⅱ．该问题的第二次优化：考虑下面的情况，经历顺序为1—2—3—4—5—6—与1—2—3—4—6—5—二者中前四个城市经历顺序相同，可以定义一个变量来保存已经历的路程，只有在经历顺序改变的时候才对已经历的路程进行更新。进行如下优化：
　　
　　1．增加privatelongtouredLength属性并初始化为0，用来记录到“目前”为止所经历的路程。
　　
　　2．重新定义goThrough
　　
　　privatevoidgoThrough(int[]tPath,intcNum,int[]cToured)
　　
　　{
　　
　　．．．//同上

　　elseif(cNum==num)
　　
　　{
　　
　　longtL=touredLength+distance[tPath[num-1]][tPath[0]]；▲//tL记录已经历的路程
　　
　　（用▲标志改进点，下同）
　　
　　if(tL<shortestLength)
　　
　　{
　　
　　shortestLength=tL；
　　
　　for(inti=0;i<num;i++)
　　
　　shortestPath[i]=tPath[i]；
　　
　　}

　　}
　　
　　else//0<citiesNum<N
　　
　　{
　　
　　for(inti=0；i<num；i++)
　　
　　if(cToured[i]!=1)//NotToured
　　
　　{
　　　　
　　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．增加属性privatelongshortestDistance[]，来保存城市之间的最短距离，次最短距离，次次最短距离，．．．，并在InitDistance中得到各距离的值。
　　
　　privatevoidInitDistance()
　　
　　{
　　
　　．．．
　　
　　shortestDistance=newlong[num+1]；
　　　　
　　shortestDistance[0]=0；

　　for(inti=0；i<num；i++)

　　{

　　longdis=10000L；
　　
　　for(intj=i+1；j<num；j++)
　　
　　if(distance[i][j]<dis)
　　
　　dis=distance[i][j]；
　　
　　shortestDistance[i+1]=shortestDistance[i]+dis；
　　
　　}
　　
　　}
　　
　　2．更新goThrough
　　
　　privatevoidgoThrough(int[]tPath,intcNum,int[]cToured)
　　
　　{
　　
　　．．．
　　
　　elseif(cNum==num)
　　
　　{
　　
　　longtL=touredLength+distance[tPath[num-1]][tPath[0]]；
　　
　　if(tL<shortestLength)
　　
　　{
　　

上一篇： Java学习:再探弥补java与com的间隙
下一篇： Java学习:一个基础的代理服务器类

上一页 1 2 3 4 5 下一页