理解“回溯算法”
若人生可重来,如何才能在岔路口做出最正确选择,让自己的人生“最优”?
贪心算法,在每次面对岔路口的时候,都做出看起来最优的选择,期望这一组选择可以使得我们的人生达到“最优”。但不一定能得到的是最优解。
如何确保得到最优解?
回溯算法很多时候都应用在“搜索”问题:在一组可能解中,搜索期望解。
处理思想,类似枚举搜索:枚举所有解,找到满足期望的解。
为规律枚举所有可能解,避免遗漏、重复,将问题求解过程分为多个阶段。
每个阶段,都要面对一个岔路口,先随意选一条路走,当发现这条路走不通(不符合期望的解),就回退到上一个岔路口,另选一种走法继续走。
八皇后
8x8的棋盘,往里放8个棋子(皇后),每个棋子所在的行、列、对角线都不能有另一个棋子。
把这个问题划分成8个阶段,依次将8个棋子放到第一行、第二行、第三行……第八行。
放置过程中,不停地检查当前方法,是否满足要求
- 满足
跳到下一行继续放置棋子 - 不满足
换种方法尝试
适合递归实现:
0-1背包
经典解法是动态规划,但还有简单但没那么高效的回溯解法。
- 有一背包,背包总承载重量Wkg
- 有n个物品,每个物品重量不等且不可分割
- 期望选择几件物品,装载到背包中。在不超过背包所能装载重量的前提下,求背包中物品的总重量max?
这个背包问题,物品不可分割,要么装要么不装,所以叫0-1背包,就无法通过贪心解解决了。
- 对于每个物品来说,都有两种选择,装 or 不装
- 对于n个物品,就有 2^n 种装法,去掉总重量超过Wkg的,从剩下的装法中选择总重量最接近Wkg的
- 但如何才能不重复地穷举出这 2^n种装法?
这就能回溯,把物品依次排列,整个问题分解为n个阶段,每个阶段对应一个物品怎么选择;
- 先对第一个物品进行处理,选择装进去 or 不装进去
- 再递归处理剩下物品
搜索剪枝的技巧:当发现 已选择物品重量 > Wkg,就停止探测剩下物品。
正则表达式
假设正表达式中只包含*
、?
通配符且现在规定:
*
匹配任意多个(大于等于0个)任意字符?
匹配0或1个任意字符
如何用回溯算法,判断某给定文本,是否匹配给定的正则表达式?
依次考察正则表达式中的每个字符,当是非通配符时,就直接跟文本的字符进行匹配:
- 相同
继续往下处理 - 不同
回溯
遇到特殊字符时,就有多种处理方式,如*
有多种匹配方案,可匹配任意个文本串中的字符,先随意选择一种匹配方案,然后继续考察剩下字符:
- 若中途发现无法继续匹配,就回到岔路口,重新选择一种匹配方案,再继续匹配剩下字符。
总结
回溯算法思想很简单,大部分都是用来解决广义搜索问题:从一组可能解中,选出一个满足要求的解。
回溯非常适合用递归实现,剪枝是提高回溯效率的一种技巧,无需穷举搜索所有情况。
回溯算法可解决很多问题,如DFS、八皇后、0-1背包、图的着色、旅行商、数独、全排列、正则表达式匹配等。