旅行家算法代码 ABCDE 5个点的

问题描述：

谁有旅行家算法 代码告诉我下好么 要c++ 或java 的
最好是C++版本的 最后输出路径 比如输出:ACBDE

问题解答：

我这有递归版的，有兴趣的话自己改下吧。城市多了递归的效率低

Class Cities

{

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]；

}

}

else

{

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

if(cToured[i]!=1)//选择未经历的城市

{

cToured[i]=1；//加入已经历城市

tPath[cNum]=i；

cNum++；//已经历城市个数+1

goThrough(tPath,cNum,cToured)；//调用下一层

cToured[i]=0；//恢复本层的状态：

cNum--；//已经历城市及个数

}//Endifinfor(i)

}//Endelse

}

privatelonggetLength(int[]tPath)//以指定顺序计算遍历路程

{

longlength=0；//路程

intnowPoint=0；//当前城市，第一次取0

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

{

intj=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类定义结束