首页 > 代码库 > 算法笔记_018:旅行商问题（Java）
算法笔记_018:旅行商问题（Java）
目录
1 问题描述
2 解决方案
2.1 蛮力法
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; //定义全局变量，用于计算当前已行走方案次数，初始化为0 public int MinDistance = 100; //定义完成一个行走方案的最短距离，初始化为100（PS：100此处表示比实际要大很多的距离） public int[][] distance = {{0,2,5,7},{2,0,8,3},{5,8,0,1},{7,3,1,0}}; //使用二维数组的那个音图的路径相关距离长度 /* * start为开始进行排序的位置 * step为当前正在行走的位置 * n为需要排序的总位置数 * Max为n!值 */ public void 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); } } } //交换数组中两个位置上的数值 public void swapArray(int[] A,int p,int q){ int temp = A[p]; A[p] = A[q]; A[q] = temp; } //输出数组A的序列，并输出当前行走序列所花距离，并得到已完成的行走方案中最短距离 public void 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); } public static void 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
参考资料：
1. 【算法设计与分析基础】蛮力法解决旅行商问题
算法笔记_018:旅行商问题（Java）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。