回溯

按照我的惯例还是先把实例放出来撕咬一番。

例1：n皇后问题，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线45度上的皇后都会自动攻击）。

例如4皇后：

说明：图展示了4个皇后依次选择列号放置的不考虑约束条件的所有可能(也叫搜索空间)，节点代表皇后，有4层代表了有4个皇后，分支代表该皇后可选择放置的列号(1,2,3,4)， 我们在这些可能中搜索可行(满足约束条件的)解。我们可以推广到在n皇后的n叉树中搜索其可行解。解是其中一条从根节点到叶节点的路径。

例2  0-1背包问题。此问题有动态规划的解法。

有四件物品，价格V={12,11,9,8},重量W={8,6,4,3},背包载重B=13，求最大价值。

2个可行解：<0,1,1,1,>，选入物品2,3,4，价值28，重量13；<1,0,1,0>，选入物品1,3，价值21，重量12；最优解<0,1,1,1,>。图解如下：

说明 ：图展示了4个物品依次分别决策是否装入背包的所有可能(也叫搜索空间)，节点代表物品，有4层代表了有4个物品，分支代表该物品是否装入(0,1)，我们在这些可能中搜索可行(满足约束条件的)解从而找出最优解。当然此物品也可以推广到n。

例3  所有货郎回路的遍历，找到最短回路。条件是城市之间两两联通。下图是4个城市的所有回路的可能排列：

         说明：货郎选最短回路问题其实是一个排列的问题，可以运用数学中排列组合知识求得所有排列，然后逐一暴力搜索， 但如果排列得当，有章法可寻，那么搜索起解来可以说是得心用手。例如图中展示的排列，节点代表了排列中的城市，分支代表了选择城市，该节点有几个分支就代表了从该城市出发还可以选择几个未经过的城市，发现第三次选择之后就只剩下唯一的选择，因为总共有4个城市嘛，选4次之后没得选。解是其中一条从根节点到叶节点的路径。

以上三种问题分析的总结：

可以看到以上的问题都是在所有可能的排列组合的解里搜索可行解或者最优解，而且所有可能组合起来是树型的结构，我们知道，无论是数组，链表，还是树，都可看做图，那么图的搜索方式同样适用于树了，即图的深广遍历也适用于树。所谓的跳跃式遍历就是在深广遍历的基础上约束一些搜索条件，从而把不满足条件的节点以及以该节点为根的子树越过不考虑遍历。后面我们会看到并不是所有的树都可以跳跃式遍历，只有满足多米诺性质的树才可以跳跃式遍历。

深广优先遍历复习举例：从1开始

深度优先有：1-2-3-5-8-9-6-7-4，广度优先有：1-2-3-4-5-6-7-8-9

发现没有？竟然还没提到回溯！！！回溯到底是什么？操了，我看了一大半，还没看到回溯，是有点生气哦。

我们先感性认识一下回溯，其实那个跳跃式遍历就是回溯遍历！！！回溯首先有一点是它适用于搜索问题，其次回溯字面解释就是逆流而上。当我们组织好问题的所有可能的排列组合后，解就是其中的一些排列组合，我们开始从这些可能中搜索其解，搜索往往使用的是深广搜索技术，当碰到不满足条件的节点后，跳跃回退到父节点继续搜索下一个子节点，等等。下面我们真正和回溯算法打一下招呼。

回溯算法的基本内容

• 适用：求解搜索问题，优化问题
• 搜索空间组织形式：树，n叉树，子集树，排列树，树的节点对应于部分向量，可行解或者说解向量在叶子节点上
• 解空间组织形式：可以看成是节点组合起来的向量
• 搜索过程：采用系统(搜索方法)的方法隐含(并不是每个节点都会遍历)遍历搜索树
• 搜索方法：深度，广度遍历，函数优先(例如广二度遍历)，深广结合，跳跃式(可以跳过遍历不满足解的条件的节点)遍历搜索树从而找到解
• 节点分支的判断条件：满足约束条件则扩展部分向量直至解向量，不满足回溯至节点的父节点，是否可以回溯搜索需要解向量满足下面讲的多米诺性质
• 节点状态：白色(尚未访问)、灰色(正在访问以该节点为根的子树)、黑色(以该节点为根的子树遍历完成)

节点状态的举例：假设对下里的树使用深度优先遍历，从1节点开始，并假设目前访问到8节点上

访问次序：1-2-3-5-8，则根据状态分类节点，已完成：2,8，已访问但未结束：1,3,5，尚未访问：9,6,7,4

回溯算法的适用条件---多米诺性质

         假设解向量是n维的，则下面的k满足：0<k<nP(x1,x2,x3,…,xk+1)为解的部分向量可以推得P(x1,x2,x3,…,xk)也为解的部分向量

         等价的逆否命题：P(x1,x2,x3,…,xk)不是解的部分向量则推得P(x1,x2,x3,…,xk+1)一定不为解的部分向量P(x1,x2,x3,…,xk)不是解的部分向量的时候才可以回溯搜索

举一个不满足多米诺性质的例子：

         求不等式的解：5x1+4x2-x3<=10,1<=xk<=3,k=1,2,3

         设解的部分向量P(x1,…,xk)，P(x1,x2,x3)可以推得P(x1,x2)吗？即5x1+4x2-x3<=10可以推得5x1+4x2<=10吗？在1<=xk<=3的条件下(最起码都大于0)，显然不成立。所以不满足多米诺性质，回溯搜索也就不可以运用了。

         然而，我们令x3=3-x33，则5x1+4x2+x33 <=13，1<=xk<=3,k=1,2，0<=x3<=2此时，P(x1,x2,x33)却可以推得P(x1,x2)，所以变换变量有了合适的约束条件可以使的满足多米诺性质。

回溯算法的设计步骤：

1. 确定解向量<x1,x2,x3,…xn>和每个分量的原始的取值范围大Xi，i=1,2，…n
2. 在确定<x1,x2,x3,…xk-1>为解的部分向量后，进一步计算xk的取值范围集合Sk，Sk属于原始取值范围集合Xk，例如0-1背包中的虚线路径就不属于Sk了。
3. 确定排列组合的规则，问题不同规则不同
4. 确定判断每个节点的约束条件，不满足回溯父节点
5. 确定搜索算法，例如深还是广度优先遍历
6. 确定解的存储结构，链表或数组

算法实现：分递归实现和迭代实现

递归实现：

BackTrace(k)

1. If  k>n then <x1,x2,…,xn> is answer.
2. else   while Sk ≠  null do
3.          xk = Sk中最小值
4.          Sk = Sk – {xk}
5.          计算 S(k+1)
6.          BackTrace(k+1)

ReBackTrace(n)

1. 计算S1
2. BackTrace(1)

 

迭代实现：

BackTrace(k)

1. 计算S1 //计算初始的取值范围
2. while Sk ≠  null do //满足约束的分支
3.          xk=Sk中最小值;Sk=Sk-{xk}
4.          if k<n then
5.                  k=k+1;计算Sk;
6.          else <x1,x2,…,xn>is answer.
7. if k>1 then k=k+1; goto 2 //回溯

算法中的变量注释：

Sk：解向量的第k个分量的选取值集合，例如：N皇后中的S1={1,2,3,4}表示该皇后四列都可以放置，当x1选第1列放置时，S2={3,4}，x2选第3列放置时，S3=null，也就是此后皇后已经无处安放；0-1背包中S1={0,1}表示第一件物品可以选择装入或者不装入；货郎选路中S1={1,2,3,4}表示货郎选择哪一个城市出发都可以，S2={2,3,4}表示选择从1出发后只能选择走向2,3,4这3个中的一个城市。

k：解向量的分量的序号，分量的取值选取值集合Sk的序号，也是递归中递归的深度的序号

例4：图的着色问题。无相连通图G=<V,E>,用m种颜色给顶点集V着色，每个顶点酌一种颜色，并要求每条边的2顶点不能着同色。现在，V={1,2,3,4,5,6,7}，颜色集{1,2,3}，顶点数n为7，颜色总数m为3.

解：如下图：

搜索结构：m(=3)叉树

解向量：<x1,x2,…,x7>，且xk ε {1,2,3}

约束条件：在<x1,x2,…,xk>处，顶点k+1的领接表中的顶点已经着过的颜色不能再着。可以得到：若领接表中的顶点着过的颜色还没用完，则k+1顶点可以着色，若k+1顶点可以着色，则<x1,x2,…,xk+1>为部分的解向量，而且<x1,x2,…,xk>一定也为部分的解向量，满足多米诺性质，故可以用回溯算法处理。

图解该问题的部分着色过程如下：

 

例5：九(奇数)宫格。(为了解决数独的算法而引入的一个问题)

填数的一个经典算法：1.把1填入第一行的中间一格；2.然后依次把后面的数字填入前面一个数字的右上格，若右上格是空的，则填入，若右上格有数，则填入当前位置的下面。

代码见我的github

 

例6：八皇后问题。代码见github，代码中有回溯思想的注释。

 

例7：数独。

搜索结构：m(=9)叉树

解向量：<x1,x2,…,xn>，且xk ε {1,2,3,4,5,6,7,8,9}，其中解向量是数独矩阵中的未填数字的位置由上至下、由左至右的向量表示

约束条件：在<x1,x2,…,xk>处，若接下来第k+1个小格子排斥从1到9这些数字，则要回溯至上一个参加填数的小格子让其从1到9重新选择填数。排斥是指，小格子所在行，或者所在列，或者所在的宫已经使用了该数字，所以该小格子不能再用(排斥)该数字。

搜索结构如下图，绿色分支表示该数字（符合约束条件行得通）可以填入小格子内，红色分支表示该数字不符合约束条件（行不通），小蓝点表示解向量中的分量或者未填数字的小格子，在相同层的小蓝点表示同一个分量或同一个未填数字的小格子：

上图中9叉树的层数等于数独中未填数字的小个子的个数，其中在图中我们发现使用约束条件来约束数字的填写之后，图中红色分支显得格外多，从树根至树叶的绿色路径中的节点的层数如果不等于数独中未填数字的小个子的个数，则此路径一定存在着回溯，具体算法见我的github.

例 8 走迷宫

题目：3代表围墙，0代表通路，给出起始坐标(1,1)，终点坐标(6,16)，寻找起点到终点的通路。

搜索结构：m(=4)叉树，上、下、左、右4个方向

解向量：<(x1,y1),……,(xk,yj),……,(xm,yn)>，且xk ε [0-7]，yj ε [0-17]

约束条件：走到<(x1,y1),……,(xk,yj)>处，若接下来的4个方向都没有到终点的通路，则要回溯至(xk,yj)点处，找另一个方向上到终点的通路

搜素图可参考数独的搜索图画出，代码见我的github。