回溯法 | 旅行商问题(TSP问题)

摘要:
然而,回溯方法可用于确定当前路径是否连接,以及当前路径是否小于已找到的最短路径。如果两个判断中的任何一个不一致,则应执行“修剪操作”。可以看出,回溯法比穷举法要好得多。这种回顾性方法与八皇后问题之间也存在一些差异。回溯方法需要对图进行DFS操作,即深度优先搜索。

学习链接:

回溯法解旅行商问题(TSP)贪心算法:旅行商问题(TSP)


今天早上做了无数个梦,然后被紧紧地吸附在床上。挣扎一番后爬起来,已经是9点了。然后我开始研究旅行商问题。

在一个无向图中找到一个可以遍历所有节点的一个最短回路。理论上说可以用全排列列出所有解的下标,然后一个一个试,时间复杂度o(n!)。但是可以用回溯法,用【约束函数】(constraint)判断当前路径是否连通,用【界限函数】(bound)判断当前路径是否比已经求得的最短路径小。这两个判断任意一个不符,则做“剪枝操作”(不再对后续节点进行遍历)。

可以看出回溯法比穷举要高明的多。这个回溯法和八皇后问题也有一些区别。TSP问题需要构造一棵排列树:

根节点为{0}

第一层{0,1}

第二层{0,1,2},{0,2,1}

第三层{0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},{0,3,1,2},{0,3,2,1}

……

并且回溯法要求对图进行DFS操作,即深度优先搜索。因为需要首先首次找到最深处的节点,才能设置当前最优解,好让后续问题能有参考。

Java代码:

 1 public class Main {
 2 
 3     public static void main(String[] args) {
 4         int[][] adjMatrix={
 5                 {0,20,6,4},
 6                 {20,0,5,10},
 7                 {6,5,0,15},
 8                 {4,10,15,0},
 9         };
10         TSP problem=new TSP(adjMatrix);
11         
12         
13     }
14 }
15 
16 class TSP{
17     int vexnum=0;//顶点数目
18     int adjMatrix[][];
19     TSP(int[][] adjMat){
20         adjMatrix=adjMat;
21         vexnum=adjMatrix.length;
22         int init[]={0};
23         Backtrack(1,init);
24         int a;
25         a=0;
26     }
27     int bestCost=0;
28     int[] bestX;//最优解向量
29     boolean isTraverseDeep=false;
30     //回溯法递归
31     //初始x:[0]
32     void Backtrack(int t,int[] x){//对顶点t进行操作,父结点的解向量是x,
33         if(t>=vexnum){//解向量的第一个元素应该是初始顶点,如0,最后一个元素也是0
34             x[t]=0;//最后一个节点赋值:0。
35             constraint(x,t);
36             
37         }else{//所有顶点都解完
38             int i,j;
39             int cx[]=new int[vexnum+1];
40             for(j=0;j<t;j++) cx[j]=x[j];//拷贝父结点
41             cx[t]=t;
42             if(constraint(cx,t)) Backtrack(t+1,cx);//不交换的情况下进行递归
43             //不断递归调用【Backtrack】,进行DFS
44             for(i=1;i<t;i++){
45                 cx=new int[vexnum+1];
46                 for(j=0;j<t;j++) cx[j]=x[j];//拷贝父结点
47                 cx[t]=t;
48                 swap(cx,i,t);
49                 if(constraint(cx,t)) Backtrack(t+1,cx);//交换的情况下进行递归
50             }
51         }
52     }
53     boolean constraint(int[] x,int len){//对解进行约束
54         int cost=0;
55         int i;
56         int pre=x[0];
57         for(i=1;i<=len;i++){
58             int dist=adjMatrix[pre][x[i]];
59             if(dist<=0) return false;//不连通,则为否。约束(constraint)函数
60             cost+=dist;
61             pre=x[i];
62         }
63         if(isTraverseDeep){//如果已经进行了最底部的遍历,则对这个当前花费进行判别。界限(bound)函数
64             if(cost<bestCost){//比最优解要小
65                 if(len==vexnum){//已经遍历完
66                     bestCost=cost;
67                     bestX=x;//设置最优解向量
68                 }
69                 return true;
70             }else return false;
71         }else if(len==vexnum){//首次遍历到底部
72             bestCost=cost;
73             bestX=x;//设置最优解向量
74             isTraverseDeep=true;
75             return true;
76         }
77         return true;
78     }
79     private void swap(int[] nums,int a,int b){
80         int tmp=nums[a];
81         nums[a]=nums[b];
82         nums[b]=tmp;
83     }
84 }

免责声明:文章转载自《回溯法 | 旅行商问题(TSP问题)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇微信小程序插件开发C++动态数组中的C6385, C6386警告下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

解空间树(回溯算法,分支界限法)

  解空间树:是依据待解决问题的特性,用树结构表示问题的解结构、用叶子表示问题的解的一颗树。   一、回溯法:采取深度遍历策略搜索解空间树,若当前结点不满足问题的求解要求,则回溯到树的上一层继续搜索另一棵子树,这种解决问题的方法称为回溯法;   1、用回溯法求解问题,重点是设计问题的解空间树,解题过程就是搜索解空间树的过程;   2、构造解空间树,就是将...

TCP输入 之 tcp_queue_rcv

tcp_queue_rcv用于将接收到的skb加入到接收队列receive_queue中,首先会调用tcp_try_coalesce进行分段合并到队列中最后一个skb的尝试,若失败则调用__skb_queue_tail添加该skb到队列尾部; 1 static int __must_check tcp_queue_rcv(struct sock *sk,...

(转)Oracle存储过程

Oracle存储过程基本语法 存储过程   1 CREATE OR REPLACE PROCEDURE 存储过程名   2 IS   3 BEGIN   4 NULL;   5 END; 行1:   CREATE OR REPLACE PROCEDURE 是一个SQL语句通知Oracle数据库去创建一个叫做skeleton存储过程, 如果存在就覆盖它; 行...

PowerQuery清理非文件名字符(清除指定列表中的所有字符)

今天我讲的这个案例的场景是:我在Excel表格里保存了一些列信息,如下左图所示。这些列将会在我的程序中用于自动生成文件。我们都知道能作为文件名的字符是有限制的,Windows中不予许在文件名出现部分字符,这些字符如下右图所示。 为了防止我的程序在运行过程中不会因为文件名混入以上的非法字符而中途退出,我需要预先处理那些我需要作为文件名的列。我的文件...

JQUERY基础2 效果 遍历 内置遍历函数

效果 隐藏与显示       hide() 和 show() <body> <button>点击</button> <div class="fi"> 今天周六 </div> </body> </html> <script> var bs =...

logic:iterate 遍历

1. 遍历集合 <logic:iterate> 的 name 属性指定需要进行遍历的集合对象, 它每次从集合中检索出一个元素, 然后把它放在page 范围内, 并以id 属性指定的字符串来命名这个元素, 例如: <% Vector animals = new Vector(); animals.addElement("Dog"); ani...