首页 / 算法 / 算法笔记_018:旅行商问题（Java）
算法笔记_018:旅行商问题（Java）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法笔记_018:旅行商问题（Java），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2671字，纯文字阅读大概需要4分钟。
内容图文
目录
1 问题描述
何为旅行商问题？按照非专业的说法，这个问题要求找出一条n个给定的城市间的最短路径，使我们在回到触发的城市之前，对每个城市都只访问一次。这样该问题就可以表述为求一个图的最短哈密顿回路的问题。（哈密顿回路：定义为一个对图的每个顶点都只穿越一次的回路）
很容易看出来，哈密顿回路也可以定义为n+1个相邻顶点v1,v2,v3,...,vn,v1的一个序列。其中，序列的第一个顶点和最后一个顶点是相同的，而其它n-1个顶点都是互不相同的。并且，在不失一般性的前提下，可以假设，所有的回路都开始和结束于相同的特定顶点。因此，可以通过生成n-1个中间城市的组合来得到所有的旅行线路，计算这些线路的长度，然后求取最短的线路。下图是该问题的一个小规模实例，并用该方法得到了它的解，具体如下：
图1 使用蛮力法求解旅行商问题
2 解决方案
2.1 蛮力法
此处使用蛮力法解决旅行商问题，取的是4个城市规模，并已经定义好各个城市之间的距离（PS：该距离使用二维数组初始化定义，此处的距离是根据图1中所示距离定义）。此处主要是在体验使用蛮力法解决该问题的思想，如要丰富成普遍规模问题，还请大家自己稍微修改一下哒。对于代码中如碰到不能理解的地方，可以参考文章末尾给出的参考资料链接，以及相关代码注解~
具体代码如下：
package
com.liuzhen.chapterThree;
public
class
TravelingSalesman {
public
int count = 0; //定义全局变量，用于计算当前已行走方案次数，初始化为0publicint MinDistance = 100; //定义完成一个行走方案的最短距离，初始化为100（PS：100此处表示比实际要大很多的距离）publicint[][] distance = {{0,2,5,7},{2,0,8,3},{5,8,0,1},{7,3,1,0}}; //使用二维数组的那个音图的路径相关距离长度/*
* start为开始进行排序的位置
* step为当前正在行走的位置
* n为需要排序的总位置数
* Max为n!值
*/publicvoid Arrange(int[] A,int start,int step,int n,int Max){
if(step == n){ // 当正在行走的位置等于城市总个数时
++count; //每完成一次行走方案，count自增1
printArray(A); //输出行走路线方案及其总距离 }
if(count == Max)
System.out.println("已完成全部行走方案！！！,最短路径距离为:"+MinDistance);
else{
for(int i = start;i < n;i++){
/*第i个数分别与它后面的数字交换就能得到新的排列,从而能够得到n!次不同排序方案
* （PS：此处代码中递归的执行顺序有点抽象，具体解释详见本人另一篇博客：）
*算法笔记_017:递归执行顺序的探讨（Java）
*/
swapArray(A,start,i);
Arrange(A,start+1,step+1,n,Max);
swapArray(A,i,start);
}
}
}
//交换数组中两个位置上的数值publicvoid swapArray(int[] A,int p,int q){
int temp = A[p];
A[p] = A[q];
A[q] = temp;
}
//输出数组A的序列，并输出当前行走序列所花距离，并得到已完成的行走方案中最短距离publicvoid printArray(int[] A){
for(int i = 0;i < A.length;i++) //输出当前行走方案的序列
System.out.print(A[i]+" ");
int tempDistance = distance[A[0]][A[3]]; //此处是因为，最终要返回出发地城市，所以总距离要加上最后到达的城市到出发点城市的距离for(int i = 0;i < (A.length-1);i++) //输出当前行走方案所花距离
tempDistance += distance[A[i]][A[i+1]];
if(MinDistance > tempDistance) //返回当前已完成方案的最短行走距离
MinDistance = tempDistance;
System.out.println(" 行走路程总和："+tempDistance);
}
publicstaticvoid main(String[] args){
int[] A = {0,1,2,3};
TravelingSalesman test = new TravelingSalesman();
test.Arrange(A,0,0,4,24); //此处Max = 4!=24 }
}
运行结果：
0 1 2 3 行走路程总和：18
0 1 3 2 行走路程总和：11
0 2 1 3 行走路程总和：23
0 2 3 1 行走路程总和：11
0 3 2 1 行走路程总和：18
0 3 1 2 行走路程总和：23
1 0 2 3 行走路程总和：11
1 0 3 2 行走路程总和：18
1 2 0 3 行走路程总和：23
1 2 3 0 行走路程总和：18
1 3 2 0 行走路程总和：11
1 3 0 2 行走路程总和：23
2 1 0 3 行走路程总和：18
2 1 3 0 行走路程总和：23
2 0 1 3 行走路程总和：11
2 0 3 1 行走路程总和：23
2 3 0 1 行走路程总和：18
2 3 1 0 行走路程总和：11
3 1 2 0 行走路程总和：23
3 1 0 2 行走路程总和：11
3 2 1 0 行走路程总和：18
3 2 0 1 行走路程总和：11
3 0 2 1 行走路程总和：23
3 0 1 2 行走路程总和：18
已完成全部行走方案！！！,最短路径距离为:11
参考资料：
原文：http://www.cnblogs.com/liuzhen1995/p/6371481.html
内容总结
以上是互联网集市为您收集整理的算法笔记_018:旅行商问题（Java）全部内容，希望文章能够帮你解决算法笔记_018:旅行商问题（Java）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。