回溯法

• 回溯法可以被描述为有组织的穷尽搜索，它可以避免搜索所有的可能性。一般适用于求解那些有潜在的大量解，但有限个数的解已经检查过的问题。

3着色问题

• 给出一个无向图，需要用三种颜色之一为每个顶点着色，三种颜色设为，要求两个相邻的顶点不能有相同的颜色（图的相邻是指有一条边）。

• 一种着色可以用元组表示。一个个顶点的图共有种着色方案（包括合法的和非法的），所有可能的着色可以用一棵完全三叉树（状态空间树）表示。从根节点到每个叶子节点的路径指示着一种着色方案。

  zYZbOs.md.png

• 几个概念：

  • 问题的解向量：问题的解能够表示成一个维向量的形式；
  • 显式约束：对分量的取值限定；
  • 隐式约束：为满足问题的解而对不同分量之间施加的限定；
  • 问题的解空间：对于问题的一个实例，解向量满足显式约束条件的所有维向量，构成了该问题实例的一个解空间。

• 为解决三着色问题，回溯法按深度优先搜索构造解空间树：

  • 算法搜索至解空间树的任一节点时，先判断该节点是否可能包含问题的解（包含即只着色了个顶点）

    • 如果肯定不包含，则跳过该节点；

    • 如果可能包含则进入该子树继续；

    • 如果某节点的所有子节点都不可能包含问题的解，则回溯其父节点，父节点在生成新的子节点搜索；

    • 一个实例：

      zUMM59.png

3-COLORREC

输入：无向图G=(V, E)。

输出：G的顶点的3着色c[1···n]，其中每个c[j]为1，2或3。

for k <- 1 to n
    c[k] <- 0
end for
flag <- false
graphcolor(1) #最多输出一种solution
if flag then output c
else output "no solution"

过程：graphcolor(k)
for color <- 1 to 3
    c[k] <- color
    if c 是合法着色 then set flag <- true exit #合法着色是说每个顶点都上色且合法
    else if c是部分的then graphcolor(k+1) #如果是部分合法则继续向后填色
    end if
end for

• 递归算法的回溯思想通过递归过程体现，每次，即退出当前函数，回溯上一个；下面使用迭代算法实现，可以显式给出回溯过程。

3-COLORITER

输入：无向图G=(V, E)。

输出：G的顶点的3着色c[1···n]，其中每个c[j]为1，2或3。

for k <- 1 to n
    c[k] <- 0
end for
flag <- false
k <- 1
while k >= 1
    while c[k] <= 2
        c[k] = c[k] + 1
        if c为合法着色then set flag <- true并退出两个while
        else if c是部分解then k <- k + 1
    end while
    c[k] <- 0 #回溯
    k <- k - 1
end while
if flag then output c
else output "no solution"

• 易知在最坏的情况下会生成个节点（一棵完全二叉树），对于检测每个节点是否合法需要的时间，时间复杂度为。

8皇后问题

• 在的国际象棋上摆放八个皇后，使其不能相互攻击，即：任意两个皇后不能处于同一行、同一列或者同一条斜线上，应该如何摆放？

  zU1WIe.png
  zU8AnP.png

• 对于8皇后问题，其实跟3着色问题思路十分相似，或者说他们都是回溯法的实际例子。从当前状态出发，顺序进行可能的尝试，然后判断合法性，设置下一个状态或者回溯。

• 状态空间树几个概念：

  • 活节点：正常节点；
  • 扩展节点：当前节点，正在对此节点进行搜索；
  • 死节点：不可行节点，无需对其孩子进行搜索；

• 下面以较简单的四皇后问题为例说明算法，数组是一行中四个格子的序号，皇后问题的思路完全一致。

4-QUEENS

输入：空。

输出：对应与4皇后问题的解向量c[1···4]。

for k <- 1 to 4
    c[k] <- 0
end for
flag <- false
k <- 1
while k >= 1
    while c[k] <= 3
        c[k] <- c[k] + 1
        if c为合法位置then set flag <- true并从两个while中退出
        else if c是部分解then k <- k + 1
        end if
    end while
    c[k] <- 0
    k <- k - 1
end while
if flag then output c
else output "no solution"

N-QUEENS

输入：空。

输出：对应与n皇后问题所有的解向量。

X(1) <- 0; k <- 1 #k指示当前行号，X(k)指示第k行的列号
while k > 0
    X(k) <- X(k) + 1
    while X(k) <= n and not PLACE(k) do #直到找到一个可以放的位置，或者不能放置
        X(k) <- X(k) + 1
    if X(k) <= n then
        if k = n then print(x)
        else k <- k + 1; X(k) <- 0 #寻找下一个位置
        end if
    else X(k) <- 0; k <- k - 1 #回溯
    end if
end while

PLACE(k)
i <- 1
while i < k 
    if X(i) = X(k) or |X(i) - X(k)| = |i - k|
        then return false
    i <- i + 1
end while
return true

一般的回溯方法

• 一般回溯算法，可以作为一种系统的搜索方法应用于一类搜索问题中，这类问题的解由事先定义好的某个约束解向量组成，是的某个整数。这里的解向量通常不是实际问题的直接表现，需要进行规则映射。

  • 例如给定，找到的子集使得的全部元素和等于。

    易得，（这是非定长的向量形式），转化为，布尔值分别指示该元素是否被选中。

回溯法框架BACKTRACK

1. 算法最初从空向量开始，先选择中的最小元素作为；

2. 如果是部分解，那么选择中的最小元素作为；

3. 如果是部分解，则继续考虑中的最小元素作为 ；

4. 否则，考虑中的第二个元素作为。依此类推。

一般说来， 当算法已经检测到部分解， 需要继续考虑 时，有以下几种情形：

1. 若表示问题的最终解，算法记录下它作为一个解。如果只需要一个解，算法结束；否则，继续找其它解。

2. 如果 是一个部分解，那么选择集合中未使用过的最小元素作为。(向前搜索)

3. 如果 既非最终解，也非部分解，那么会有以下两种情况：

   a. 如果集合中还有其它未曾使用过的元素，则选择下一个未曾使用过的元素作为。

   b. 如果集合中没有其它未曾使用过的元素，则回溯，将中未曾使用的下一元素作为，并将进行重置。如果集合中没有未曾使用的元素，那么继续回溯(同样注意要进行重置)。

BACKTRACKREC

输入：集合X1, X2,···, Xn的清楚的或隐含的描述。

输出：解向量v = (x1, x2,..., xi)。

v <- ()
flag <- false
advance(1)
if flag then output v
else output "no solution"

过程：advance(k)
for every x in Xk
    xk <- x;将xk加入v
    if v是最终解 then set flag <- true exit
    else if v是部分解then advance(k+1) #如果是部分合法则继续向后
    end if
end for

BACKTRACKITER

输入：集合X1, X2,···, Xn的清楚的或隐含的描述。

输出：解向量v = (x1, x2,..., xi)。

v <- ()
flag <- false
k <- 1
while k >= 1
    while Xk没有被穷举尽
        xk <- Xk中的下一个元素;将x加入v
        if v是最终解then set flag <- true并退出两个while
        else if v是部分解then k <- k + 1
    end while
    重置Xk，使得下一个元素排在第一位 
    k <- k - 1 #回溯
end while
if flag then output v
else output "no solution"

• 以上回溯算法最多求出一个解，若要得到全部解向量则需要稍加修改。

回溯法解决0/1背包问题

• 物品集合为元组，选中第个物品则，否则为。0/1背包是找到一个最优解，所以需要遍历整个状态树后找最优的。

  zwMkyq.md.png

BACKTRACKING

输入：物品集合U={u1, u2,..., un}，体积分别为s1, s2,..., sn，价值分别为v1, v2,..., vn，容量为C的背包。

输出：在约束条件下最大，。

k <- 1; Pw <- 0; Pv <- 0; X <- 2 #X数组指示背包是否被选中，0/1，初始时赋值为2
                                #Pw，Pv分别指示最优方案的weight和value
while k > 0 
    X[k] <- X[k] - 1 # 每次减1，遍历0/1两种状态
    if X[k] == 1 then #左子树
        if Pw + W[k] <= C then
            Pw <- Pw + W[k]; Pv <- Pv + V[k]
        else
            X[k] <- X[k] - 1
        end if
    else if X[k] == 0 #右子树
        Pw <- Pw - W[k]; Pv <- Pv - V[k]
    end if
    if X[k] >= 0 then
        if k == n then
            if Pv > Ov then
                Ow <- Pw; Ov <- Pv; Y <- X
            end if
            k <- k - 1 #得出一个解后回溯直到找到最优解
        else
            k = k + 1
        end if
    else
        X[k] <- 2
        k <- k - 1
    end if
end while

• 0/1背包回溯法的改进：在搜索左子树时有判断但是右子树没有，所以右子树的遍历每次都会执行。但是如果右子树的最大可能结果的填充都比现有的解决方案小，就可以跳过搜索右子树，利用上界函数判断当前状态下能够得到最优方案的上界。
• 上界函数：按照性价比排列物品，当前遍历第个物品，还剩容量时，依次将放入背包直到装满（注意此时的性价比是个背包排序，而不是的排序，因为此时的状态已经确定不能改变），装不下的采用比例装入（联想小数背包问题），得到的结果就是上界值。

BOUND(p, w, k, M)
#p:当前价值，w:当前重量，k:当前根节点，M:背包容量，物品已经按性价比排序
b <- p; c <- w
for i <- k + 1 to n 
    c <- c + W(i)
    if c < M then b <- b + P(i)
    else return (b+(1-(c-M)/W(i))*P(i))
return b

分支界限法

• 分支界限法类似于回溯法，但是是采用广度优先搜索或者最小耗费算法。
• 在分支界限法中，每个活节点只有一次机会成为扩展节点。活节点一旦成为扩展节点，就一次性产生所有子节点，得到不可行的节点则直接被舍弃。
  • 队列法，依照队列先进先出的原则选取下一个节点作为扩展节点；
  • 堆结构法，按照堆的规定选取优先级最高的节点（堆的根）作为扩展节点。

最短路径问题

• 例，计算节点到节点的最短路径

  zw1ahF.md.png
  • 确定下界：经过某节点到的最短路径的下界为：到的最短路径加上的一条最短出边。例如的下界为，的下界为；（最终的解就是下界）
  zwBzJs.md.png

  • 步骤总结：

    

    • 根节点对应于源点，有个邻接顶点，其下界为，压入堆。

    

    • 堆中下界最小，对于的顶点，也即结点。从顶点继续进行搜索。
    • 顶点的邻接顶点为和，其下界为和，压入堆。

    

    • 堆中下界最小，对应顶点，也即结点，从顶点继续进行搜索。

    • 顶点邻接顶点，对应的下界为，压入堆。

    

    • 堆中最小，对应顶点，也即结点。从顶点进行搜索。

    • 顶点邻接顶点，对应的下界为，压入堆。

    

    • 堆中最小，对应顶点，也即结点。

    • 顶点的邻接顶点为，下界分别为，压入栈中。其中为一个可行解，将bound置为。

    

    • 堆中最小，对应顶点，也即结点。

    • 顶点的邻接顶点为，下界都是。其中为一个可行解，将bound置为。

    

    • 堆中最小，对应顶点，也即结点。

• 顶点只有一个邻接顶点，下界为，从而得到一个可行解，路径长度为，加入堆中。堆中最小的为，且最后一个结点为，因此是最优解。

0/1背包问题

• 考虑，承重为的背包问题（价值/重量即物品的性价比）。

  zcTJJS.png

• 思路：

  • 为每个搜索节点设置一个上界，一个简单的方法是：把已经选择的物品总价值，加上背包剩余承重与剩下可选择物品的最高“价值/重量比”的乘积，即；
  • 比如，已经装了物品，则价值的上界为。
  • 如下图，每次选择的物品是使最大的结点。

zc7s0I.png

旅行商问题TSP

• 问题描述为：一个商人要去个城市推销货物，从某个城市出发，要求找到一条闭合路径，个城市都经历一次，最后回到出发点，使得旅行的花费最小（依据情况的不同，花费可以是距离、时间、金钱等）。与背包问题相反，我们需要估计每个搜索节点的下界。

• 例如，给定图。

  zczCE4.png

• 一个有效的下界：

  • 对于每个顶点，表示与顶点相连顶点的两个最短距离之和，即，下界。

  • 如果必须包含某条边，则。

  • zczGxP.png
    ，对于该图。

  • zczRZF.png
    ，例如必须包含边则。

  • 为什么可以这样设置呢？

    zgSleU.png

    • 给定个顶点的无向图，边的权值已经确定，将符合题意的回路记作；

    • 显然，在中每个顶点只出现一次，记作。每条边记作；

    • 我们可以得到：

      对于顶点，；

      对于顶点，；

      ······

      对于顶点，；

      累加求和解得：，由于是整数所以可以取。

zgSay6.png