1、第六章第六章 回溯法回溯法什么是回溯法什么是回溯法n例：迷宫游戏例：迷宫游戏可用回溯法求解的问题n问题的解可以用一个解可以用一个n元组元组(x1,xn)来表来表示示，其中的xi取自于某个有穷集Si，并且这些解必须使得某一规范函数解必须使得某一规范函数P(x1,xn)（也称限界函数）取极值或满足该规范（也称限界函数）取极值或满足该规范函数条件。函数条件。n例子：A(1:n)个元素的分类问题 问题的解为n元组；xi取自有穷集；规范函数P：A(xi)A(xi+1)问题求解的方法n硬性处理法 列出所有候选解，逐个检查是否为所需要的解 理论上，候选解数量有限，并且通过检查所有或部分候选解能够得到所需解时
2、，上述方法可行 实际中则很少使用，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模较小的问题。n回溯或分枝限界法 避免对很大的候选解集合进行完全检查 大大减少问题的求解时间 通常用来求解规模较大的问题回溯法概述n回溯法可以系统的搜索一个问题的所有解或任一个解n它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索到某一结点时，如果断定该结点肯定不包含问题的解，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯n这种以深度优先方式搜索问题的解的方法称为回溯法回溯法思想n第一步：为问题定义一个状态空间第一步：为问题定
3、义一个状态空间(state space)。这个空间必须至少包含问题的一个解n第二步：组织状态空间以便它能被容易地搜索第二步：组织状态空间以便它能被容易地搜索。典型的组织方法是图或树n第三步：按深度优先的方法从开始结点进行搜索第三步：按深度优先的方法从开始结点进行搜索 开始结点是一个活结点（也是 E-结点：expansion node）如果能从当前的E-结点移动到一个新结点，那么这个新结点将变成一个活结点和新的E-结点，旧的E-结点仍是一个活结点。如果不能移到一个新结点，当前的E-结点就“死”了（即不再是一个活结点），那么便只能返回到最近被考察的活结点（回溯），这个活结点变成了新的E-结点。当我
4、们已经找到了答案或者回溯尽了所有的活结点时，搜索过程结束。回溯法如何提高效率？n由开始结点到当前E-结点构成解向量(x1,xi)；其中的xi取自于某个有穷集Si，假设集合Si的大小是mi。n如果判定(x1,xi)不能导致最优解，那么就将可能要测试的mi+1mn个向量略去。n因此回溯法的测试次数比硬性处理作的测试次数要少得多。如何判定如何判定(x1,xi)能否导致最优解？能否导致最优解？约束条件n回溯法的解需要满足一组综合的约束条件，通常分为：显式约束和隐式约束显式约束和隐式约束n显式约束条件限定每个xi只从一个给定的集合上取值，例如：Xi0 即si=所有非负实数 xi=0或xi=1 即 si=
5、0,1 lxiu即si=a:laun满足显式约束的所有元组确定一个可能的解空间n隐式约束描述了xi必须彼此相关的情况，如0/1背包问题中的背包重量M回溯法求解的经典问题（1）8-皇后问题n在一个8*8棋盘上放置8个皇后，且使得每两个之间都不能互相“攻击”，也就是使得每两个都不能在同一行、同一列及同一条斜角线上。n8皇后问题的解可以表示为8-元组(x1,x8)，其中其中xi是第i行皇后所在的列号。n显式约束条件是si=1,2,3,4,5,6,7,8,1i8n隐式约束条件是，没有两个xi可以相同且没有两个皇后可以在同一条斜角线上。QQQQQQQQ 1 2 3 4 5 6 7 812345678由于
6、解向量之间不能相同，所以解空间的大小由由于解向量之间不能相同，所以解空间的大小由88个个元组减少到元组减少到8!个元组。上图中的解表示为一个个元组。上图中的解表示为一个8-元组元组即（即（4，6，8，2，7，1，3，5）。）。回溯法求解的经典问题（2）子集和数问题n已知(w1,w2,wn)和M，均为正数。要求找出wi的和数等于M的所有子集。例如：若n=4,(w1,w2,w3,w4)=(11,13,24,7),M=31，则满足要求的子集是(11,13,7)和(24,7).子集和数问题解的一种表示方法n若用Wi的下标表示下标表示解向量，这两个解向量为(1,2,4)和(3,4)。n子集和数问题的解可
7、以表示为k-元组(x1,x2,xk),1kn并且不同的解可以是大小不同的元组。n显式约束条件是xi j|j为整数且1jn。n隐式约束条件是1)没有两个xi是相同的;2)wxi的和为M;3)xixi1,1in（避免产生同一个子集的重复情况）子集和数问题解的另一种表达n解由n-元组(x1,x2,xn)表示n显式约束条件xi0,1，1in，如果没有选择Wi，则xi=0；如果选择了Wi，则xi=1。于是上面的解可以表示为(1，1，0，1)和(0，0，1，1)n隐式约束条件(xi wi)的和数为Mn解空间的大小为2n个元组解空间的树结构n回溯算法通过系统地检索给定问题的解空间来确定问题的解。这检索可以用
8、这个解空间的树结构来简化。为了便于讨论，引进一些关于解空间树结构的术语。n问题状态问题状态(problem state)(problem state)：树中的每一个结点确定所求解问题的一个问题状态。n状态空间状态空间(state space)(state space)：由根结点到其它节点的所有路径则确定了这个问题的状态空间。n解状态解状态(solution states)(solution states)：解状态是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组。n答案状态答案状态(answer states)(answer states)：对于这些解状态而言
9、，由根到S的这条路径确定了这问题的一个解(即，它满足隐它满足隐式约束条件式约束条件)。n状态空间树状态空间树(state space tree)(state space tree)：解空间的树结构。组织解空间（1）n4-皇后问题解空间的树结构(解空间由从根结点到叶结点的所有路径所定义)n-皇后问题的状态空间树？皇后问题的状态空间树？组织解空间（2）n子集和数问题解空间由树中的根结点到任何结点的所有路径所确定，这些可能解空间由树中的根结点到任何结点的所有路径所确定，这些可能的路径是的路径是()(这对应于由根结点到他自身的那条路径这对应于由根结点到他自身的那条路径)；(1)；(1,2)；(1,2,
10、3)；(1,2,3,4)；(1,2,4)；(1,3,4)；(1,4)；(2)；(2,3)等等等等组织解空间（3）n子集和数问题解空间由根结点到叶结点的所有路径确定解空间由根结点到叶结点的所有路径确定状态空间树状态空间树 对于任何一个问题，一旦设想出一种状态空间树，那么就可以先系统地生成问题状态，接着确定这些问题状态中的哪些是解状态，最后确定哪些解状态是答案状态从而将问题解出 生成问题状态的两种方法 便于问题的描述，给出以下概念：活结点：活结点：自己已经生成而其所有的儿子结点还没有全部生成的结点。E-结点（正在扩展的结点）：结点（正在扩展的结点）：当前正在生成其儿子结点的活结点。死结点：死结点：
11、不再进一步扩展或者其儿子结点已全部生成的生成结点。生成问题状态的两种方法生成问题状态的两种方法n第一种方法：当前的E-结点R一旦生成一个新的儿子C，这个儿子结点就变成一个新的E-结点，当完全检测了子树C之后，R结点就再次成为E-结点。这相当于问题状态的深度优先生成。n第二种方法：一个E-结点一直保持到变成死结点为止。n在这两种方法中，将用限界函数杀死部分还没有全部生成其儿子结点的那些活结点。n回溯法：回溯法：使用限界函数的深度优先结点生成方法。n分枝分枝-限界方法：限界方法：E-结点一直保持到死为止的状态生成方法。4-皇后问题-回溯解 1 2 3 412344-皇后问题回溯期间生成的树回溯法的
12、算法回溯法的算法n算法的三个步骤：算法的三个步骤：针对所给问题，定义问题的解空间针对所给问题，定义问题的解空间；应用回溯法解问题时，首先应明确定义问题的应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个解空间。问题的解空间应至少包含问题的一个（最优）解。（最优）解。确定易于搜索的解空间结构确定易于搜索的解空间结构；以深度优先的方式搜索解空间，并且在搜以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索索过程中用剪枝函数避免无效搜索；回溯算法的形式描述 假设回溯算法要找出所有的答案结点而不是仅仅只找出一个。设(x1,x2,xi-1)是状态空间树中由根到
13、一个结点(问题状态)的路径。T(x1,x2,xi-1)是下述所有结点的xi的集合，它使得对于每一个xi,(x1,x2,xi)是一条由根到结点xi的路径存在一些限界函数Bi(可以表示成一些谓词)，如果路径(x1,x2,xi)不可能延伸到一个答案结点，则Bi(x1,x2,xi)取假值，否则取真值。因此，解向量X(1:n)中的第i个分量就是那些选自集合T(x1,x2,xi-1)且使Bi为真的xi。回溯的一般方法算法procedure BACKTRACK(n)integer k,n;local X(1:n)k1 while k0 do if 还剩有没检验过的X(k)使得 X(k)T(X(1),X(k-
14、1)and B(X(1),X(k)=true then if(X(1),X(k)是一条已抵达一答案结点的路径 then print(X(1),X(k)endif k k+1 else k k-1 endif repeatend BACKTRACK回溯算法的递归表示procedure RBACKTRACK(k)global n,X(1:n)for 满足下式的每个X(k)X(k)T(X(1),X(k-1)and B(X(1),X(k)=true do if(X(1),X(k)是一条已抵达一答案结点的路径 then print(X(1),X(k)endif call RBACKTRACK(k+1)r
15、epeatend RBACKTRACK算法说明：算法说明：基本上是一棵树的后根次序周游。这个递基本上是一棵树的后根次序周游。这个递归模型最初由归模型最初由call RABCKTRACK(1)调用。调用。效率分析应考虑的因素（1）生成下一个X(k)的时间（2）满足显式约束条件的X(k)的数目（3）限界函数Bi的计算时间（4）对于所有的i，满足Bi的X(k)的数目n权衡：限界函数生成结点数和限界函数本身所需的计算时间效率分析n效率分析中应考虑的因素（1）（3）与实例无关（4）与实例相关n有可能只生成O(n)个结点，有可能生成几乎全部结点n最坏情况时间 O(p(n)2n)，p(n)为为n的多项式的多
16、项式 O(q(n)n!)，q(n)为为n的多项式的多项式Monte Carlo效率估计（1）n一般思想 在状态空间中生成一条随机路径 X为该路径上的一个结点，且X在第i级 mi为X没受限界的儿子结点数目 从mi随机选择一个结点作为下一个结点 路径生成的结束条件：1）叶子结点；或者2）所有儿子结点都已被限界 所有这些mi可估算出状态空间树中不受限界结点的总数mMonte Carlo效率估计（2）使用蒙特卡罗方法的假设条件限界函数是固定的，即在算法执行期间当其信息逐渐增加时限界函数不变。同一个函数正好用于这棵状态空间数同一级的所有结点。使用蒙特卡罗方法估算应用举例 设第二级没受限结点数为m1。如果
17、这棵检索数是同一级上结点有相同的度的数，那么就可以预计到每一个2级结点平均有m2个没界限的儿子，从而得出在第3级上有m1m2个结点。第4级预计没受限的结点数是m1m2m3。一般在i+1级上预计的结点数是m1m2mi。于是，在求解给定问题的实例中所要生成的不受限界结点的估计数 m=1+m1+m1m2+m1m2m3+Monte Carlo效率估计算法procedure ESTIMATE m1;r 1;k 1 loop TkX(k):X(k)T(X(1),X(k-1)and B(X(1),X(k)if SIZE(Tk)=0 then exit endif rr*SIZE(Tk)mm+r X(k)CH
18、OOSE(Tk)KK+1 repeat return(m)end ESTIMATEESTIMATE是一个确定m值的算法6.2 8-皇后问题皇后问题n8-皇后问题实际上很容易一般化为皇后问题实际上很容易一般化为n-皇后皇后问题，即要求找出一个问题，即要求找出一个n*n棋盘上放置棋盘上放置n个皇后并使其不能互相攻击的所有方案。个皇后并使其不能互相攻击的所有方案。n令令(x1,x2,xn)表示一个解，由于没有两表示一个解，由于没有两个皇后可以放入同一列，因此所有的个皇后可以放入同一列，因此所有的xi将将是互不相同的。是互不相同的。n那么关键是应如何去测试两个皇后是否在那么关键是应如何去测试两个皇后是
19、否在同一条斜角线上呢？同一条斜角线上呢？6.2 8-皇后问题皇后问题n如果用二维数组如果用二维数组A(1:n,1:n)的下标来标记每个皇后的位置，那么可的下标来标记每个皇后的位置，那么可以看到，以看到，对于在同一条斜角线上的由左上方到右下方的每一个元对于在同一条斜角线上的由左上方到右下方的每一个元素有相同的素有相同的“行行-列列”值，值，同样，同样，在同一条斜角线上的由右上方到在同一条斜角线上的由右上方到左下方的每一个元素则有相同的左下方的每一个元素则有相同的“行行+列列”值。值。a11a12a13a14a15a16a17a18a21a22a23a24a25a26a27a28a31a32a33
20、a34a35a36a37a38a41a42a43a44a45a46a47a48a51a52a53a54a55a56a57a58a61A62a63a64a65a66a67a68a71a72a73a74a75a76a77a78a81a82a83a84a85a86a87a886.2 8-皇后问题皇后问题n假设有两个皇后被放置在假设有两个皇后被放置在(i，j)和和(k，l)位置上，那么根据以上所述，仅当位置上，那么根据以上所述，仅当i j=k-l 或或 i+j=k+l时，它们才在同一条斜角线上。时，它们才在同一条斜角线上。n将这两个等式分别变换成将这两个等式分别变换成 j-l=i-k 或或 j-l=k
21、-in因此，当且仅当因此，当且仅当|j-l|=|i-k|时（即两个时（即两个皇后所在位置的行差距等于列差距时），皇后所在位置的行差距等于列差距时），两个皇后在同一条斜角线上。两个皇后在同一条斜角线上。算法算法6.4：可以放置一个新皇后吗？：可以放置一个新皇后吗？Procedure PLACE(k)/如果一个皇后能放在第如果一个皇后能放在第k行和行和X(k)列，则返回列，则返回true，否则返回，否则返回false。X是一个全程数组，进入此过程时已置入了是一个全程数组，进入此过程时已置入了k个值。个值。ABS(r)过程返回过程返回r的绝对值的绝对值/global X(1:k);integer i
22、,k;i1while i0 do /对所有的行，执行以下语句对所有的行，执行以下语句/X(k)X(k)+1 /移到下一列移到下一列/while X(k)n and Not PLACE(k)do /此处能放这个皇后吗此处能放这个皇后吗/X(k)X(k)+1 /不能放则转到下一列不能放则转到下一列/repeatif X(k)n then /找到一个位置找到一个位置/if k=n then print(X)/是一个完整的解则打印这个数组是一个完整的解则打印这个数组/else kk+1;X(k)0 /否则转到下一行否则转到下一行/end if else kk-1 /回溯回溯/end ifrepeatE
23、nd NQUEENS6.3 子集和数问题子集和数问题n假定有假定有n个不同的正数，要求找出这些数中所个不同的正数，要求找出这些数中所有使得某和数为有使得某和数为M的组合。的组合。n前面已经说明了如何用大小固定或变化的元前面已经说明了如何用大小固定或变化的元组来表示这个问题。组来表示这个问题。本节将利用大小固定的本节将利用大小固定的元组来研究一种回溯解法，解决这一问题。元组来研究一种回溯解法，解决这一问题。n对于对于i级上的一个结点，其左儿子对应于级上的一个结点，其左儿子对应于X(i)=1，右儿子对应于，右儿子对应于X(i)=0。6.3 子集和数问题子集和数问题n限界函数限界函数 当且仅当当且仅
24、当W(i)X(i)(i=1 to k)+W(i)(i=k+1 to n)M 时，时，B(X(1),X(2),X(k)=True 当当W(i)以递增次序排列以递增次序排列，则界限函数可强化：，则界限函数可强化：若若W(i)X(i)(i=1 to k)+W(k+1)M，则，则X(1),X(2),X(k)就不能导致一个答案结点。就不能导致一个答案结点。n因此将要使用的界限函数是因此将要使用的界限函数是：Bk(X(1),X(2),X(k)=True当且仅当当且仅当 W(i)X(i)(i=1 to k)+W(i)(i=k+1 to n)M 并且并且 W(i)X(i)(i=1 to k)+W(k+1)M算
25、法算法6.6：子集和数问题的递归算法：子集和数问题的递归算法Procedure SUMOFSUB(s,k,r)/找找W(1:n)中的和数为中的和数为M的所有子集。进入此过程时的所有子集。进入此过程时X(1),X(2),X(k-1)的值已确定。的值已确定。S=W(j)X(j)(j=1 to k-1)且且r=W(j)(j=k to n)。这些。这些W(j)按非降次序排列按非降次序排列。假定假定W(1)M，W(i)M(i=1 to n)/global integer M,n;global real W(1:n);global boolean X(1:n)real r,s;integer k,j;/生
26、成左儿子。注意由于生成左儿子。注意由于Bk-1=true,因此因此s+W(k)M/X(k)=1if s+W(k)=M then /子集找到子集找到/print(X(j),j=1 to k)/此处由于此处由于W(j)0,1 j n,因此不存在递归调用因此不存在递归调用/算法算法6.6：子集和数问题的递归算法：子集和数问题的递归算法else if s+W(k)+W(k+1)M then /Bk=true/call SUMOFSUB(s+W(k),k+1,r-W(k)endifendif/生成右儿子和计算生成右儿子和计算Bk的值的值/If s+r-W(k)M and s+W(k+1)M /Bk=tr
27、ue/then X(k)=0 call SUMOFSUB(s,k+1,r-W(k)endifEnd SUMOFSUB例例6.6n若若n=6,M=30n=6,M=30，(w(w1 1:w:w6 6)=(5,10,12,13,15,18),)=(5,10,12,13,15,18),找出找出wi的和数等于的和数等于M的所有子集。的所有子集。6.4 图的着色图的着色n已知一个图已知一个图G和和m0种颜色，在只准使种颜色，在只准使用这用这m种颜色对种颜色对G的结点着色的情况下，的结点着色的情况下，是否能使图中任何相邻的两个结点都具是否能使图中任何相邻的两个结点都具有不同的颜色呢？有不同的颜色呢？n这个问
28、题称为这个问题称为m-着色判定问题着色判定问题。n在在m着色最优化问题则是求可对图着色最优化问题则是求可对图G着着色的色的最小整数最小整数m。这个整数称为图。这个整数称为图G的的色数。色数。6.4 图的着色图的着色 对于图着色的研究是从对于图着色的研究是从m-可着色性问题的著可着色性问题的著名特例名特例四色问题四色问题开始的。四色问题要求开始的。四色问题要求证明平面或球面上的任何地图的所有区域都证明平面或球面上的任何地图的所有区域都至多可用四种颜色来着色，并使任何两个有至多可用四种颜色来着色，并使任何两个有一段公共边界的相邻区域没有相同的颜色。一段公共边界的相邻区域没有相同的颜色。四色问题可以
29、转换成对一平面图的四色问题可以转换成对一平面图的4-着色判着色判定问题。定问题。将地图的每一个区域变成一个结点，若两个将地图的每一个区域变成一个结点，若两个区域相邻，则相应的结点用一条边连接起来。区域相邻，则相应的结点用一条边连接起来。下面的图显示了一幅有下面的图显示了一幅有5个区域的地图以及与个区域的地图以及与该地图相应的平面图。该地图相应的平面图。一幅地图和它的平面表示一幅地图和它的平面表示多年来虽然已经证明用多年来虽然已经证明用5种颜色足以对任一幅地图着色，种颜色足以对任一幅地图着色，但是一直找不到一定要求多于但是一直找不到一定要求多于4种颜色的地图。种颜色的地图。直到直到1976年这个
30、问题才由科学家利用电子计算机的帮年这个问题才由科学家利用电子计算机的帮助得以解决。他们证明了助得以解决。他们证明了4种颜色足以对任何地图着色种颜色足以对任何地图着色。我们所考虑的不只是由地图产生的图，而是所有的图。我们所考虑的不只是由地图产生的图，而是所有的图。讨论在至多使用讨论在至多使用m种颜色的情况下，可对一给定的图着种颜色的情况下，可对一给定的图着色的所有不同的方法。色的所有不同的方法。6.4 图的着色图的着色n假定用图的邻接矩阵假定用图的邻接矩阵GRAPH(1:n,1:n)来来表示一个图表示一个图G，其中若，其中若(i,j)是是G的一条边，的一条边，则则GRAPH(i,j)=true，
31、否则，否则GRAPH(i,j)=false。n因为要拟制的算法只关心一条边是否存在，因为要拟制的算法只关心一条边是否存在，所以使用布尔值。颜色用整数所以使用布尔值。颜色用整数1,2,m表表示，解用示，解用n-元组元组X(1),X(2),X(n)来给出。来给出。其中其中X(i)是结点是结点i 的颜色。的颜色。6.4 图的着色图的着色n算法算法MCOLORING使用的基本状态空间使用的基本状态空间树是一棵度数为树是一棵度数为m，高为，高为n+1的树。在的树。在i 级上的每一个结点有级上的每一个结点有m个儿子，它们与个儿子，它们与X(i)的的m种可能的赋值相对应，种可能的赋值相对应，1i n。在在n
32、+1级上的结点都是叶结点。级上的结点都是叶结点。n下面的图给出了下面的图给出了n=3,m=3时的状态空间时的状态空间树。树。6.4 图的着色图的着色算法算法6.7 找一个图的所有找一个图的所有m-着色方案着色方案Procedure MCOLORING(k)/这是图着色的一个递归这是图着色的一个递归回溯算法。图回溯算法。图G用它的布尔邻接矩阵用它的布尔邻接矩阵GRAPH(1:n,1:n)表示。表示。/它计算并打印出符合以下要求的全部解，把整数它计算并打印出符合以下要求的全部解，把整数1,2,m分配给图中分配给图中/各个结点且使相邻近的结点的有不同的整数。各个结点且使相邻近的结点的有不同的整数。K
33、是下一个要着色结点的下标是下一个要着色结点的下标Global integer m,n,X(1:n)boolean GRAPH(1:n,1:n)Integer kLoop /产生对产生对X(k)所有的合法赋值。所有的合法赋值。/call NEXTVALUE(k)/将一种合法的颜色分配给将一种合法的颜色分配给X(k)/if X(k)=0 then exit endif /没有可用的颜色了没有可用的颜色了/if k=n then print(X)/至多用了至多用了m种颜色分配给种颜色分配给n个结点个结点/else call MCOLORING(k+1)/所有所有m-着色方案均在此反复递归着色方案均在
34、此反复递归调用中产生调用中产生/endifrepeatEnd MCOLORING算法算法6.8 生成下一种颜色生成下一种颜色Procedure NEXTVALURE(k)/进入此过程前进入此过程前X(1),X(2),X(k-1)已分得了区域已分得了区域1,m中的整数且相邻近的结点中的整数且相邻近的结点有不同的整数。本过程在区域有不同的整数。本过程在区域0,m中给中给X(k)确定一个值：确定一个值：如果还剩下一些颜色，如果还剩下一些颜色，它们与结点它们与结点k邻接的结点分配的颜色不同，那么就将其中最高标值的颜色分配给邻接的结点分配的颜色不同，那么就将其中最高标值的颜色分配给结点结点k;如果没剩下
35、可用的颜色，则置如果没剩下可用的颜色，则置X(k)为为0/global integer m,n,X(1:n)boolean GRAPH(1:n,1:n)integer j,kloop X(k)=(X(k)+1)mod(m+1)/试验下一个最高标值的颜色试验下一个最高标值的颜色/if X(k)=0 then return endif /全部颜色用完全部颜色用完/for j=1 to n do /检查此颜色是否与邻近结点的那些颜色不同检查此颜色是否与邻近结点的那些颜色不同/if GRAPH(k,j)and X(k)=X(j)/如果如果(k,j)是一条边是一条边,并且邻近的结点有相并且邻近的结点有相
36、同的颜色同的颜色/then exit endif repeat if j=n+1 then return endif /找到一种新颜色找到一种新颜色/repeat /否则试着找另一种颜色否则试着找另一种颜色/end NEXTVALUREX1X2X3X4右图显示了一个包含四个结点的右图显示了一个包含四个结点的简单图。下面是一棵由过程简单图。下面是一棵由过程MCOLORING生成的树。到叶子生成的树。到叶子结点的每一条路径表示一种至多结点的每一条路径表示一种至多使用使用3种颜色的着色法。种颜色的着色法。6.5 哈密顿环n设G=(V,E)是一个n结点的连通图。n一个哈密顿环哈密顿环是一条沿着图G的n
37、条边环行的路径，它访问每个结点一次并且返回到它的开始位置。n用向量（x1,x2,xn）表示回溯法求得的解，其中，xi是找到的环中第i个被访问的结点。n为了避免将同一个环重复打印，可事先指定x1=1。算法算法:生成下一个结点生成下一个结点procedure NEXTVALUE(k)/X(1),.,X(k-1)是一条有k-1个不同结点的路径。若X(k)=0，则表示再无结点可分配给X(k)。若还有与X(1),.,X(k-1)不同且与X(k-1)有边相连接的结点，则将其中标数最高的结点置于X(k)。若k=n，则还需与X(1)相连接/global integer n,X(1:n),boolean GRA
38、PH(1:n,1:n)interger k,j loop X(k)=(X(k)+1)mod(n+1)/下一个结点 if X(k)=0 then return endif if GRAPH(X(K-1),X(K)/有边相连吗 then for j=1 to k-1 do if X(j)=X(k)then exit endif repeat if j=k /若为真，则是一个不同结点 then if kn or(k=n and GRAPH(X(n),1)then return endif endif endif repeatend NEXTVALUE算法算法:找所有的哈密顿环找所有的哈密顿环proc
39、edure HAMILTONIAN(k)/这是找出图G中所有哈密顿环的递归算法。图G用它的布尔邻接矩阵GRAPH(1:n,1:n)表示。每个环都从结点1开始/global interger X(1:n)local interger k,n loop /生成X(k)的值 call NEXTVALUE(k)/下一个合法结点分配给X(k)if X(k)=0 then return endif if k=n then print(X,1)/打印一个环 else call HAMILTONIAN(k+1)endif repeatend HAMILTONIAN6.6 0/1背包问题n这个问题的解空间由各分
40、量xi分别取0或1值的2n个不同的n元向量组成。n无论使用哪种限界函数，都应有助于杀死某些结点，使这些活结点实际上不再扩展。n本节使用大小固定的元组表示。如果在结点Z处已确定了xi的值，1ik，则Z的上界由下法获得：对k+1 i n，将xi=0或1的要求放宽为0 xi 1算法算法:限界函数限界函数procedure BOUND(p,w,k,M)/p为当前效益总量；w为当前背包重量；k为上次去掉的物品；M为背包容量；返回一个新效益值/global n,P(1:n),W(1:n)interger k,i;real b,c,p,w,M b=p;c=w;for i=k+1 to n do c=c+W(
41、i)if c=p(i+1)/w(i+1)。fw是背包的最后重量，fp是背包取得的最大效益。X(1:n)中每个元素取0或1值。若物品k没放入背包，则X(k)=0；否则X(k)=1/interger n,k,Y(1:n),i,X(1:n);real M,W(1:n),P(1:n),fw,fp,cw,cp;cw=cp=0;k=1;fp=-1 /cw是背包当前重量；cp是背包当前取得的效益值 loop while k=n and cw+W(k)n then fp=cp;fw=cw;k=n;X=Y /修改解 else Y(k)=0 /超出M，物品质K不适合 endif while BOUND(cp,cw
42、,k,M)=fp do/上面置了fp后，BOUND=fp while k0 and Y(k)1 do k=k-1 /找最后放入背包的物品 repeat if k=0 then return endif /算法在此处结束 Y(k)=0;cw=cw-W(k);cp=cp-P(k)/移掉第k项 repeat k=k+1 repeatend BKNAP1例6.7考虑以下情况的背包问题：考虑以下情况的背包问题：n=8 1 2 3 4 5 6 7 8P=(11,21,31,33,43,53,55,65)W=(1,11,21,23,33,43,45,55)M=110执行过程见执行过程见P212的生成树。的生
43、成树。0 1 2 3 4 5 6 7 8P=(11,21,31,33,43,53,55,65)W=(1,11,21,23,33,43,45,55)M=110算法说明n以上算法的变量fp在结点A、B、C和D的每一处被修改。每次修改fp时也修改X。n终止时，fp159和X(1，1，1，0，1，1，0，0)。n在状态空间树的29-1511个结点中只生成了其中的35个结点。注意到由于所有的P(i)都是整数而且所有可行解的值也是整数，因此BOUND(p,w,k,M)是一个更好的限界函数，使用此限界函数结点E和F就不必再扩展，从而生成的结点数可减少到28。算法说明n每次在第10行调用BOUND时，在过程B
44、OUND中基本上重复了第46行的循环，因此可对算法BKNAPl作进一步的改进。n为了取消BKNAPl第46行所做的工作，需要把BOUND改变成一个具有边界效应的函数。n两个新算法为BOUNDl和BKNAP2算法。算法 有边界效应的限界函数procedure BOUND1(P,W,k,M,pp,ww,i)/新近移到的左儿子所对应的效益为pp，重量为ww。i是上一个不适合的物品。如果所有物口都试验过了，则i的值是n+1/global n,P(1:n),W(1:n),Y(1:n)integer k,i;real p,w,pp,ww,M,bppp;www;for ik+1 to n do if ww+
45、W(i)M then wwww+W(i);pppp+P(i);Y(i)1;else return(pp+(M-ww)*P(i)/W(i)endifrepeatreturn(pp)end BOUND1算法 改进的背包算法procedure BKNAP2(M,n,W,P,fw,fp,X)/与BKNAP1同/integer n,k,Y(1:n),i,j,X(1:n)real W(1:n),P(1:n),M,fw,fp,pp,ww,cw,cpcwcpk0;fp-1loop while BOUND1(cp,cw,k,M,pp,ww,j)fp do while k0 and Y(k)1 do kk-1 r
46、epeat if k0 then return endif Y(k)0;cwcw-W(k);cpcp-P(k)repeat cppp;cwww,kj/等价于BKNAP1中46行的循环/if kn then fpcp;fwcw;kn;XY else Y(k)0endif repeatend BKNAP2 用动态状态空间树解0/1背包问题n到目前为止，所讨论的都是在静态状态空间树环境下工作的回溯算法，现在讨论如何利用动态状态空间树来设计背包问题的回溯算法。n下面介绍的一种回溯算法的核心思想是以贪心算法所得的贪心解为基础来动态地划分解空间，并且力图去得到01背包问题的最优解。首先用约束条件0 x1来
47、代换Xi0或1的整数约束条件，于是得到一个放宽了条件的背包问题。用动态状态空间树解0/1背包问题n用贪心方法解式这个背包问题，如果所得贪心解的所有Xi都等于0或1，显然这个解也是相应01背包问题的最优解。n如若不然，则必有某Xi使得0Xi1。利用这个Xi解空间划分成两个子空间，使Xi0在一个子空间，Xi1在另一于空间。于是，表示此解空间的状态空间树的左子树是以Xi0为根的左分枝的于树，右子树是以Xi1为右分枝的于树。n一般说来，在状态空间树的每个结点Z处用贪心方法求解是在有附加限制的情况下进行的，这附加限制是已对由根到结点Z的那条路径进行了赋值。用动态状态空间树解0/1背包问题n换言之，是在给
48、出了根到结点Z那条路径各边所对应的那些Xi的值（它们各自取0或1值）之后，再用贪心法求解。n如果贪心解全是0或1，则找到了此情况下的最优解。n若不然，则必有一个Xi,使得0Xi1。那么取Xi=0为结点Z的左分枝，Xi=1为结点Z的右分枝。用动态状态空间状态空间树解0/1背包问题考虑以下情况的背包问题：考虑以下情况的背包问题：n=8 1 2 3 4 5 6 7 8P=(11,21,31,33,43,53,55,65)W=(1,11,21,23,33,43,45,55)M=110动态状态空间树见动态状态空间树见P214实例 1 2 3 4 5 6 7 8P=(11,21,31,33,43,53,5
49、5,65)W=(1,11,21,23,33,43,45,55)M=110用动态状态空间树解0/1背包问题nX=(1,1,1,1,1,21/43,0,0)n令令X6=0 (和和 X6=1)nX=(1,1,1,1,1,0,21/45,0)n令令X7=0 (和和 X7=1)nX=(1,1,1,1,1,0,0,21/55)n令令X8=0 (和和 X8=1)nX=(1,1,1,1,1,0,0,0)n此时解全是整数，此时找到的最好解是此时解全是整数，此时找到的最好解是xX=(1,1,1,1,1,0,0,0)，效益值为效益值为139n令令X8=1nX=(1,1,1,22/23,0,0,0,1)n令令X4=0（和（和X4=1）nX=(1,1,1,0,2/3,0,0,1)n Thank you
