算法分析与设计回溯法.ppt

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