目录

回溯

基本介绍

回溯可以理解成一个人在前进的过程中有无数个岔路口,经过一个岔路口,又有一个岔路口。每在一个岔路口选择一个道都会影响这个人之后的人生。有的人在每一个岔路口都能做出十分正确的选择,所以这个人的生活和事业都达到了人生巅峰。而有的人一步,步步错,可能就是它最初的选择的那个岔路口就是错的,导致这个人就一致生活坎坷。 经典的回溯算法解决的问题很多,如八皇后、0-1背包问题、图的着色、旅行商问题、全排列问题。

下面挑几个例子来

八皇后

https://gitee.com/lienhui68/picStore/raw/master/null/20200701155231.png 一共有8个岔路口,每个岔路口就是一行,每行随便选择一列放置棋子。但是每放一个棋子,就需要检查当前的状态还满足不满足八皇后规则。不满足直接pass,满足接着放下一行。 这是简化版的三皇后问题,其实感觉有点像穷举,但是不满足的提前被pass掉了。 https://gitee.com/lienhui68/picStore/raw/master/null/20200701155418.png

0-1 背包

0-1 背包的经典解法是动态规划,但是这里还是以回溯来说。

  1. 问题: 假设有一个背包,背包的总承载重量是w kg。现在假设有n个物品,每个物品的重量不等,并且不可分割,现在期望选择几个物品,装载到背包中,在不超过背包所能装载重量的前提下,实现背包中的总重量最大。
  2. 分析: 对于每个物品来说,都有两种不同的选择,装进背包或者不装进背包。对于n个物品来说,总的装法就 2^n 种。去掉总重量超过 w kg的。从剩下的装法中选择重量最接近w kg的。不过,如何才能不重复的穷举出这 2^n 种装法呢。 有没有发现,这和八皇后问题十分相似,就是先穷尽,并及时pass掉不符合规定的。
  3. 图解 https://gitee.com/lienhui68/picStore/raw/master/null/20200701155614.png

小结

回溯是通过不同的尝试来生成问题的解,有点类似于穷举,但是和穷举不同的是回溯会"剪枝",意思是对已经知道的错误结果不会再枚举接下来的答案。

参考

回溯