Backtrack
Backtrack
后悔药,时光机…没有什么最优解,只是遍历了所有时空才确定了你。
概述
递归和非递归
回溯法可由递归和非递归方式实现,根据问题性质是排列还是集合,也可以抽象出对应的模板。
非递归回溯需要设计额外的数据结构来保存节点。
排列与子集
问题的解空间树有两种类型。若问题为从含n个元素的集合S中找出符合某约束的元素的集合,此为子集树,比如求子集问题;若问题为从含n个元素的集合S从,找出满足约束的n个元素的排列,此为排列树,比如求全排列问题。
幂集问题
分析:设定一个数组bool choose[n]表示这n个对应的元素是否被选了,因此对于n个元素,从第一个元素开始,若选中了,则置choose[i]=1;直到处理完最后一个元素,输出这组结果,然后回溯上一层…
建模:
代码:
1 |
|
全排列问题
分析:从数组首元素开始处理,让他与自己交换位置,然后处理交换位置后的元素,让他与自己交换…最终处理到最后一个元素,由于是与自身交换位置,此时的序列不会有任何改变,因为没有后继元素了,则输出该序列然后回溯到上一层,处理倒数第二的元素,这次让他与倒数第一的元素交换位置(而非自身),此时进入下一层,处理末元素,又得到一组结果,然后再回溯到上上层…
建模:
代码:
1 |
|
比较:
排列树的决策是交换,恢复是换回,子集树的决策是选择是否,恢复是做出另一选择。另外,问题也有维度之分,多维问题,除了dfs本身的层数外,在主要决策处也会有循环试探:N皇后,任务分配。
剪枝
为了提高回溯法的时间效率,常常要考虑剪枝,进一步涉及到左子树的剪枝和右子树的剪枝:
对于右子树的剪枝,一般还要额外设置一个函数参数rightIndex。
左子树:一般是无法满足的条件:比如背包问题中剩余重量不够用。
右子树:一般是不用判断,一定满足的条件:比如背包问题中即使后续全选也不会超重。
对于复杂问题,还要专门写出一个剪枝函数prune:比如活动安排问题中的剪枝函数:
回溯和深度遍历
可以简略地认为backtrace=dfs with pruning.
他们本来就很暧昧~
子集树
01背包
可以抽象为子集问题,回溯于:是否选择某物品。
分析:约束在于总重,优化在于价值。决策将会影响重量和价值,只需要遍历所有的决策组合,约束和优化在最后一层判断。将决策与约束和优化分离后就会清晰很多。感觉不如dp…效率。但是思想也很美~
1 |
|
装载和复杂装载
一般装载问题:n个集装箱要装入载重为W的轮船,每个箱子重量:wi 求最佳装载方案。
分析:每个货物选或不选。不如背包问题。。。
1 |
|
复杂装载问题:若有两艘船,找出方案使得所有货物能被运走。在一般装载问题的基础上,先只考虑承重大的那艘船,记为船A,尽可能多地装载,对于没有选中的货物默认装载在第二艘船,记为船B,最终再判断船B能否承受剩余的货物,若能则方案可行,否则没有任何方案能够做到带走这些货物。难点在于证明这个思路的正确性:
反证法:假如能够运走所有货物,但船A却不是最佳方案(承重尽可能最大)。
货物总重不变,记最终方案中:船A装载货物总重为La,船B为Lb,La+Lb===Sum(Wi) ,如果方案行得通,说明船B能承受Lb,那对于比Lb更小的它自然也能承受,而此时完全可以把货物调度到船A上。
有了思路后实现就很简单了,在原来的基础上修饰一下就好了。我就不写了,欣赏下书上的写法吧!(#^_^#)
1 |
|
N皇后
典中典。抽象为子集问题。回溯在于某坐标是否放置了皇后,难点在于建模,这个问题只有在第一次见的时候会觉得无从下手。
分析:问题建模,用一维数组就可以描述棋盘,下标是行,元素值为列,下标+元素值确定一个坐标。用二维数组也可以,但是不简洁而且浪费空间。
1 |
|
Sum100
设计一个算法在1,2,3..9(顺序不能变)数字之间插入 + 或 - 或什么也不插,使得计算结果为100,并输出所有方案。
分析:输出时机:处理完9且所得结果为100。决策:+ - 空。回溯点:处理完9但结果不为100.
三选一的子集问题抽象。
1 |
|
子集和
经典子集问题,比01背包还简单
1 |
|
任务分配
n个任务n个人,人和任务的分配只能是1对1的,每个人处理每个任务花费不同,求出最优分配方案。
分析:可抽象为子集型问题。用二维数组存储任务对应的处理人的开销,再设1个一维bool数组存储任务是否分配了,1个一维数组people,下标为人员编号,元素值为任务编号。
1 |
|
涂色
排列树
活动安排
n个活动,每个活动有各自的开始时间和结束时间,活动串行,求最优安排方案——使得能安排最多数量的活动。即求出活动的排列。约束是排列合理(满足串行),优化是排列的数量尽可能多。感觉不如贪心…
分析:在主要决策体中,考虑活动layer—N,分别将layer与其后的活动交换位置,然后判断是否兼容,若兼容则选取更新兼容时间,进入下一层…当回溯到本层,换回位置,执行恢复。
慢到爆炸!对于活动安排问题还是去考虑贪心吧!!!
1 |
|
流水线作业调度
n个作业,都要先在机器M1再在M2上进行加工,不同任务在不同机器上加工时间有所不同,确定最佳加工顺序,使得从第一个任务在M1上开始到最后一个任务在M2上结束之间的时间间隔最短。
分析:可抽象为排列类的问题,求一种作业的排列,使得按这样的排列顺序得到的时间间隔最短。作业在M1上是连续的,只要上一个作业执行完毕后,下一个作业就可以去M1上执行了,但是M2的执行可能需要等待,当作业A在M1执行后,进入M2,作业B接着进入M1执行,可能会有作业B在M1上执行完了,作业A在M2上还在执行,因此M2上的时间不连续,存在等待时间.因此花在M2上的总时间需要利用数组,而M1不用。重点在于处理等待时间。若要等待,则当前作业i在m2上执行结束的时间time2[i]为:time2[i]=time2[i-1]+m2[i];若不需要等待,则为:time2[i]=time1[i]+m2[i];而真正执行结束的时间应该取二者最大值。即:**time2[i]=max{ time2[i-1]+m2[i] , time1[i]+m2[i] }**。稍微剪枝一下:若当前方案下的作业i的time2已经超过了之前记录的较优解,则可以直接剪掉了。进一步剪枝:记当前处理的作业为i,已知作业i的time2,则time2就是前i个作业全部执行完毕的时间,再记录他们在m2上花费的总时间iSum和所有作业在m2上的总时间allSum,则确定一个值:time2[i]+allSum-iSum.从i往后确定的每一种方案(叶节点)的最终完成时间一定大于等于该值。因此当确定出该值>目前的bestTime就可以知道,接下来的所有叶子节点对应的值都不可能为打破当前的bestTime,因此可以直接剪掉。
1 |
|
见解
在设计dfs时关于回溯恢复的考虑:如果将数据作为函数参数,则可以自动恢复,若不作为参数,而是全局变量,则要手动恢复。