分析回溯和分支定界在代码上的区别

Liberity
2023-12-11 / 1 评论 / 19 阅读 / 正在检测是否收录...

首先思想上:

简单理解,由于二者都是基于递归树的搜索算法,使用一定的限界条件减少搜索的树的枝干从而简化搜索过程,同时有利于降低时间和空间复杂度。

回溯在于深度优先搜索,分支定界在于宽度优先搜索。

回溯的话:

基本思路是针对每一行可供选择的结点,然后递归是会自动进行深搜的,回溯操作就需要我们主动添加了,一般就是对应的添加数据。

比如代码中常见的

cw+=… ; 
back(i+1);   
cw-=…; 
back(i+1); 

这种一见就是针对选择和不选择写成的状态空间树。

另一种是利用while或者for循环遍历每层的结点,然后循环内会有递归进行自X动深搜。

反应过来一个呼应的知识点,排列树和子集树,排列树多是用循环解决,子集树多是两次回溯解决。

如果但看这一段代码的话,都是递归的方式,如何判断时间复杂度?

子集树就可以是T(n)=2T( n-1)+ O(1);排列树的话,T(n-1)的系数会产生相应的变化,时间复杂度不好判断,那么回溯题的考点在哪里?

一般都是限界函数(两个)伪代码,由于是递归的写法,考虑好递归出口递归过程,同时考虑回溯的特点,数据量的变化回溯时的限界条件

那如果递归的方式是深度搜索的好方式,那分支定界的宽度搜索的代码会是什么样子?

由于分支定界是将活结点当作扩展结点然后变为死结点,结束的标志是找到答案或者将所有节点遍历一遍。

分支定界的代码一般都是循环优先队列,深搜的同时利用限界函数减少搜索次数。如果针对于考试的话,把规约矩阵,旅行商问题,最小罚款额调度,0/1背包问题等几个经典问题的代码理解清楚。
这几个问题其实没什么代码,基础代码的思路就是广搜将结点放入队列,然后取出再放入,重复这个过程。

2

评论 (1)

取消
  1. 头像
    Liberity 作者
    Windows 10 · Google Chrome

    这个分支定界的算法有点不好写,预计会增加一篇文章对分支定界题目伪代码进行讲解分析。

    回复