算法设计与分析第5章回溯法

1、2022-3-3计算机算法设计与分析1第五章回溯法2022-3-3计算机算法设计与分析2用计算机求解问题问题空间现实求解过程实际解状态空间对象的定义机器求解过程算法与程序的设计机内解2022-3-3计算机算法设计与分析3计算机求解的过程n在状态空间寻找机内解可以看成是从初始状态出发搜索目标状态(解所在的状态)的过程。状态空间初始状态目标状态搜索n搜索的过程可描述为：S0S1Sn，其中S0为初态，Sn为终态。或者说(S0)且(Sn)，这里称为初始条件，称为终止条件。2022-3-3计算机算法设计与分析4求解是状态空间的搜索n求解的过程可以描述为对状态空间的搜索S0S11S12S1k Sn1Sni

2、Snm其中S0为初始状态，不妨设Sni为终止状态S0Snin于是问题的求解就是通过搜索寻找出一条从初始状态S0到终止状态Sni的路径。2022-3-3计算机算法设计与分析5几种搜索方法状态空间的搜索实际上是一种树的搜索，常用的方法有：n广度优先的搜索n深度优先的搜索n启发式的搜索从初始状态开始，逐层地进行搜索。从初始状态开始，逐个分枝地进行搜索。从初始状态开始，每次选择最有可能达到终止状态的结点进行搜索。2022-3-3计算机算法设计与分析6三种搜索的优劣之处n一般来说，三种搜索方法各有优劣之处：n广度优先搜索的优点是一定能找到解；缺点是空间复杂性和时间复杂性都大。n深度优先搜索的优点是空间复

3、杂性和时间复杂性较小；缺点是不一定能找到解。n启发式搜索是最好优先的搜索，优点是一般来说能较快地找到解，即其时间复杂性更小；缺点是需要设计一个评价函数，并且评价函数的优劣决定了启发式搜索的优劣。2022-3-3计算机算法设计与分析7树搜索的一般形式nSearchTree(Space T)/表L用来存放待考察的结点nunfinish = true; L = T.initial; n/ unfinish表示搜索未结束，先将初始状态放入Lnwhile (unfinish & L) n a = L.first; /从L中取出第一个元素n if (a is goal) unfinish = fa

4、lse /若a是终态则结束n else Control-put-in(L, Sons(a);n /否则，将a的儿子们以某种控制方式放入L中2022-3-3计算机算法设计与分析8三种搜索的不同之处 树的三种搜索方法的不同就在于它们对表L使用了不同控制方式：nL是一个队列nL是一个栈nL的元素按照某方式排序n广度优先搜索n深度优先搜索n启发式搜索n其中，深度优先搜索就是回溯法。2022-3-3计算机算法设计与分析9回溯法的形式化描述n假设能够用n元组（x1,x2,xn）表示一个给定的问题P的解，其中xi集合Si；nn元组的子组（ x1,x2,xi ）（in），如果它满足一定的约束条件，则称为部分解

5、。n如果它已经是满足约束条件的部分解，则添加xi+1Si+1形成新的子组（ x1,x2,xi ,xi+1 ）并检查它是否满足约束条件，若满足则继续添加xi+2Si+2，并以此类推。如果所有的xi+1Si+1都不满足约束条件，那么去掉xi+1，回溯到xi的位置，并去掉当前的xi，另选一个xiSi，组成新的子组（ x1,x2,xi ）并判断其是否满足约束条件。n如此反复下去，直到得到解或者证明无解为止。 回溯法的适用情形n有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。n回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法

6、。这种方法适用于解一些组合数相当大的问题。n回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。102022年3月3日11回溯法的基本思想n 回溯法从根结点出发，按照深度优先策略搜索（遍历）解空间树，搜索满足约束条件的解。n初始时，根结点成为一个活结点，同时也称为当前的扩展结点。在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为一个新的活结点，并成为当前的扩展结点。如果在当前的扩展结点处不能再向

7、纵深方向移动，则当前的扩展结点就成为一个死结点（即不再是一个活节点）。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。2022年3月3日12回溯法的基本思想n在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出限界函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。n在搜索过程中，通常采用两种策略避免无效搜索：（1）用约束条件剪去得不到可行解的子树；（2）用限界函数剪去得不到最优解的子树。 这两类函数统称为剪枝函数。20

8、22-3-3计算机算法设计与分析13递归回溯法的一般形式nTry(s)n 做挑选候选者的准备；n while (未成功且还有候选者) n 挑选下一个候选者next； n if (next可接受) n 记录next；n if (满足成功条件) 成功并输出结果n else Try(s+1);n if (不成功) 删去next的记录; n return 成功与否2022-3-3计算机算法设计与分析14迭代回溯法的一般形式n先让我们回顾解空间搜索的一般形式：nSearchTree(Space T)/表L用来存放待考察的结点nunfinish = true; L = T.initial; n/ unfi

9、nish表示搜索未结束，先将初始状态放入Lnwhile (unfinish &L) n a = L.first; /从L中取出第一个元素n if (a is goal) finish = false /若a是终态则结束n else Control-put-in(L, Sons(a);n /否则，将a的儿子们以某种控制方式放入L中回溯法中表L为栈，将初始状态压入栈中。弹出栈顶元素在通常求解问题时，解是由逐个状态构成的。因此，这里还需要判断状态是否可接受，并进行纪录路径等工作。如果a可接收但未终止，则要将a的后继压入栈中。如果要抛弃状态a，当a是最后一个儿子时，还需要消除原有纪录甚至回溯一

10、步。2022-3-3计算机算法设计与分析15如何判断最后一个儿子？n若只要遍历解空间树上的结点，那么将各个结点按栈的方式控制便可实现深度为主的搜索。n但是在求解问题时，需要记录解的路径，在回溯时还需要删除结点和修改相应的信息。n栈中的结点是分层次的，而现在没有区分它们的层次。这就增加了回溯判断和操作的困难。那么怎么办？n采用一个简洁有效的方法：设计一个末采用一个简洁有效的方法：设计一个末尾标记，每次压栈时，先压入末尾标记。尾标记，每次压栈时，先压入末尾标记。2022-3-3计算机算法设计与分析16用末尾标记的迭代回溯nBacktrack(Tree T) n unfinish = true; L

11、.Push(T.root); n while (unfinish & L) n a = L.Pop( ); n if (a is the last mark) backastep( );n else if (a is good) record(a);n if (a is goal) unfinish = false; output( );n else if (a has sons) L.Push-Sons(a) n else move-off(a);若栈顶元素是末尾标记，说明这个路径已经到头了，需要回溯一步。若a是可以接受的，则将a加入求解的路径中。若a是目标节点，则结束搜索并输出求解

12、的路径。若a不是目标节点且a有后即，则将a的后继压入栈中。这里的L.Push-Sons(a)要先压入末尾标记，然后再压入后继结点。若a不是目标节点又没有后继，则将a从解的路径中删除。2022-3-3计算机算法设计与分析17不可接受的结点n破坏了解的相容条件的结点n超出了状态空间的范围，或者说不满足约束条件的结点；n评价值很差的结点，即已经知道不可能获得解的结点；n已经存在于被考察的路径之中的结点，这种结点会造成搜索的死循环。2022-3-3计算机算法设计与分析18数的全排列问题n对于指定的n个数字，输出它所有可能的排列。n容易知道n个数字恰有n!个排列。n它有一个隐含的约束条件：每个数字用且只

13、能用一次。 2022-3-3计算机算法设计与分析19全排列问题的解空间树n设n=4，而需要排列的4个数字分别为：1，2，3，4。回顾我们手工对这四个数字的排列过程： （1 2 3 4）（1 2 4 3）（1 3 2 4）（）（4 3 2 1）2022-3-3计算机算法设计与分析20全排列问题中的数据表示n数组recn+1记录当前搜索路径上的每个结点所放置的数字；n数组usedn+1记录当前搜索路径上已经被使用过的数字；2022-3-3计算机算法设计与分析21用递归回溯法求N数全排列问题nTry(s)n 做挑选候选者的准备；n while (未成功且还有候选者) n 挑选下一个候选者next；

14、n if (next可接受) n 记录next；n if (满足成功条件) 成功并输出结果n else Try(s+1);n if (不成功) 删去next的记录; n return 成功与否先回顾递归回溯法的一般形式： 2022-3-3计算机算法设计与分析22用递归回溯法求N数全排列问题nTry(s)n 做挑选候选者的准备；n while (未成功且还有候选者) n 挑选下一个候选者next； n if (next可接受) n 记录next；n if (满足成功条件) 成功并输出结果n else Try(s+1);n if (不成功) 删去next的记录; n return 成功与否s为准备

15、放置数字的位数候选者为数字1到n。j = 0; q = 0; 令数字从j = 0开始；q=0表示未成功数字不到n就还有候选者(!q & j n ) 数字加1j+;若数字没有使用过，便可接受(Safe(j) Record (s,j);(s = = n) q = 1; output( rec ); 不成功，清掉该数字。(!q) Move-Off(s, j); q recs=j; usedj=1;(usedj=0) (!q) recs=0; usedj=0; n个位置都放完就成功了记下该位置的数字2022-3-3计算机算法设计与分析23递归求全排列的主程序nN-Arrange( ) nint

16、 recn + 1, usedn + 1;nfor (i = 1, i= n; i+) n reci=0;n usedi=0;ntry(1); 从第一行开始递归2022-3-3计算机算法设计与分析24N数全排列问题的迭代程序先看看迭代回溯法的一般形式：nBacktrack(Tree T) n unfinish = true; L.Push(T.root); n while (unfinish&L) n a = L.Pop( ); n if (a is the last mark) backastep( );n else if (a is good) record(a);n if (a

17、is goal) unfinish = false; output( );n else if (a has sons) L.Push-Sons(a) n else move-off(a);迭代从第一个位置开始，将数字1n和-1压入栈中，这里-1作为末尾标记。s = 1; L.Push(1, 2, , n, -1);a是末尾标记则回溯(a = = -1) backastep; 回溯需要回溯需要做什么？做什么？回溯需要退回一个位置，即s ；同时删除该位置的原纪录。usedrecs=0;s ; a = recs; Move-Off(s, a); 如果safe(a)则放下数字a。(Safe(a) Re

18、cord(s, a);如果到了第n位，则成功。(s = = n) 当s n时，则必定有后继。无需考虑此情况。s+; L.Push(1, 2, , n, -1); 2022-3-3计算机算法设计与分析25N数全排列问题的迭代程序nBacktrack(Tree T) n unfinish = true; s = 1; L.Push(1, 2, , n,-1);n while (unfinish & L) n a = L.Pop( ); n if (a = = -1) usedrecs=0;s ; a = recs; recs=0;useda=0;n else if (useda=0) n

19、recs=a; useda=1;n if (s = = n) unfinish = false; output(rec);n else s+; L.Push(1, 2, , n, -1); n2022-3-3计算机算法设计与分析26迭代求全排列主程序nN-Queens(n) nint recn + 1, usedn + 1;nfor (j = 1, j n + 1; j+) n recj = 0; usedj =0; nBacktrack(n, rec);n2022-3-3计算机算法设计与分析27N数全排列问题的时间复杂性n对于规模为n的全排列而言,该算法的时间复杂度也就是搜索的结点总数。n为

20、简单起见，只考虑访问可扩展结点的时间。n将根结点所在层次标为0层，其余依次为1,2,n层。则每层的可扩展结点数目依次为：n, n(n-1), n(n-1)(n-2), n(n-1)2, n!，设总的结点数目为S(n)，则有 S(n)= n!/(k!)，故 2n!S(n)3n!故时间复杂度为O(n!)。 2022-3-3计算机算法设计与分析28N后问题n要求在一个nn的棋盘上放置n个皇后，使得她们彼此不受攻击。n按照国际象棋的规则，一个皇后可以攻击与之同一行或同一列或同一斜线上的任何棋子。n因此，N后问题等价于：要求在一个nn的棋盘上放置n个皇后，使得任意两个皇后不得在同一行或同一列或同一斜线上

21、。N皇后问题的实例2022年3月3日292022-3-3计算机算法设计与分析30八皇后问题n先建立一个8*8格的棋盘，在棋盘的第一行的任意位置安放第一只皇后。n紧接着，我们就来放第二行，第二行的安放就要受一些限制了，因为与第一行的皇后在同一列或同一对角线的位置上是不能安放皇后的，接下来是第三行，n或许我们会遇到这种情况：在摆到某一行的时候，无论皇后摆放在什么位置，她都会被其它行的皇后吃掉，这时就必须要回溯，将前面的皇后重新摆放， 2022-3-3计算机算法设计与分析31八皇后的一个可行解第1列第2列第3列第4列第5列第6列第7列第8列记录数组rec第1行 1第2行 7第3行 5第4行 8第5行

22、 2第6行 4第7行 6第8行 32022-3-3计算机算法设计与分析32用递归回溯法求N后问题nTry(s)n 做挑选候选者的准备；n while (未成功且还有候选者) n 挑选下一个候选者next； n if (next可接受) n 记录next；n if (满足成功条件) 成功并输出结果n else Try(s+1);n if (不成功) 删去next的记录; n return 成功与否先回顾递归回溯法的一般形式： 2022-3-3计算机算法设计与分析33用递归回溯法求N后问题nTry(s)n 做挑选候选者的准备；n while (未成功且还有候选者) n 挑选下一个候选者next；

23、n if (next可接受) n 记录next；n if (满足成功条件) 成功并输出结果n else Try(s+1);n if (不成功) 删去next的记录; n return 成功与否s为准备放置后的行数候选者为1到n列。j = 0; q = 0; 令列标记j = 0；q表示未成功列数不到n就还有候选者(!q & j n ) 列数加1j+;各后都安全，便可接受(Safe(s, j) 记下该行后的位置(列数)Record(s, j);n行后都放完就成功了(s = = n) q = 1; output( ); 不成功，删去后在该行的位置。(!q) Move-Off(s, j); q

24、 2022-3-3计算机算法设计与分析34求解N后问题中的数据表示n数组recn表示棋盘。若reci=j，1i, jn，表示棋盘的第i行第j列上有皇后。n数组Cj=1表示第j列上无皇后，1jn。n数组Dk=1表示第k条下行( )对角线上无皇后。6543211 2 3 4 5 6k = i j ， n+1kn1 。这里，2022-3-3计算机算法设计与分析35求解N后问题中的数据表示n数组recn表示棋盘。若reci = j，1i, jn，表示棋盘的第i行第j列上有皇后。n数组Cj = 1表示第j列上无皇后，1jn。n数组Dk = 1表示第k条下行( )对角线上无皇后。k = i j ， n+1

25、kn1 。这里，n数组Uk = 1表示第k条上行( )对角线上无皇后。6543211 2 3 4 5 6k = i + j ，2k2n 。 这里，2022-3-3计算机算法设计与分析36求解N后问题中的子程序nRecord(s, j) k = s j + n; recs = j; Cj = 0; Us + j 1 = 0; Dk = 0; nMove-Off(s, j) k = s j + n; recs = 0; Cj = 1; Us + j 1 = 1; Dk = 1; nSafe(s, j) k = s j + n; if (Cj & Dk & Us + j 1) ret

26、urn true else return false; 2022-3-3计算机算法设计与分析37求解N后问题的主程序nN-Queens( ) nint recn + 1, Cn + 1, D2n, U2n;nfor (j = 1, j n + 1; j+) n recj = 0; Cj = 1; n U2j = 1; U2j 1 = 1;n D2j = 1; D2j 1 = 1;ntry(1);将数组recn, Cn, U2n和D2n都赋予初值。从第一行开始递归2022-3-3计算机算法设计与分析38N后问题的迭代程序n先看看迭代回溯法的一般形式：nBacktrack(Tree T) n un

27、finish = true; L.Push(T.root); n while (unfinish & L) n a = L.Pop( ); n if (a is the last mark) backastep( );n else if (a is good) record(a);n if (a is goal) unfinish = false; output( );n else if (a has sons) L.Push-Sons(a) n else move-off(a);迭代从第一行开始，将第一行的1n列和0压入栈中，这里0作为末尾标记。s = 1; L.Push(1, 2,

28、 , n, 0);a是末尾标记则回溯(a = = 0) backastep; 回溯需要回溯需要做什么？做什么？回溯需要退回一行，即s ；同时删除该行的原纪录s ; a = recs; Move-Off(s, a); 如果safe(s,a)，则放下后(Safe(s, a) Record(s, a);如果到了第n行，则成功(s = = n) 当行s n时，则必定有后继。无需考虑此情况。s+; L.Push(1, 2, , n, 0); 2022-3-3计算机算法设计与分析39N后问题的迭代程序nBacktrack(Tree T) n unfinish = true; s = 1; L.Push(1

29、, 2, , n);n while (unfinish & L) n a = L.Pop( ); n if (a = = 0) s ; a = Bs; Move-Off(s, a);n else if (Safe(s, a) Record(s, a);n if (s = = n) unfinish = false; output(B);n else s+; L.Push(1, 2, , n, 0); n2022-3-3计算机算法设计与分析40迭代回溯解N后问题的主程序nN-Queens(n) nint recn + 1, Cn + 1, D2n, U2n;nfor (j = 1, j

30、n + 1; j+) n recj = 0; Cj = 1; n U2j = 1; U2j 1 = 1;n D2j = 1; D2j 1 = 1;nBacktrack(n, rec);n2022-3-3计算机算法设计与分析41N后问题的时间复杂性n要精确估计N后问题的时间复杂度是一件很困难的事，但至少可以知道：它的约束条件比N个数的全排列更为严格，所有搜索的节点数肯定更少。n故时间上界为O(N!)2022-3-3计算机算法设计与分析42旅行售货员问题nTSP：某售货员到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条路线，经过每个城市一遍最后回到驻地的路线，使得总的路程(或总旅

31、费)最小。n设G=(V, E)是一个带权图。图中各边的费用(权值)为正。图中一条周游路线是包括V中所有顶点的回路。一条周游路线的费用是该路线上所有边的费用之和。所谓旅行售货员问题就是要在图G中找出一条最小费用的周游路线。2022-3-3计算机算法设计与分析43nTry(s)n 做挑选候选者的准备；n while (未成功且还有候选者)n 挑选下一个候选者next； n if (next可接受) n 记录next；n if (满足成功条件) 成功并输出结果n else Try(s+1);n if (不成功) 删去next的记录; n return 成功与否线路上的第线路上的第s个结点个结点这里只

32、需依次考这里只需依次考察察n1个结点，即个结点，即for (i=2; i=n; i+)下一个候选就是下一个候选就是i结点结点i尚未在路线中尚未在路线中且总耗费值不大。且总耗费值不大。考虑TSP的递归回溯算法就是将结点就是将结点i放入路放入路线中并修改耗费值线中并修改耗费值s +1= = n若新线路更好，就用若新线路更好，就用新线路取代老线路。新线路取代老线路。这里无所谓成功与否，这里无所谓成功与否，因为每一条周游路线因为每一条周游路线都要进行比较。都要进行比较。2022-3-3计算机算法设计与分析44TSP的递归回溯算法nTry(s)n for (i = 2; i = n; i+)n if (

33、Accept(i) n Record(s, i)；n if (s+1 = = n) n if (better) TakeNewPath( ) ; n else Try(s+1);n Move-off(s, i)n return 2022-3-3计算机算法设计与分析45求解TSP的数据结构n用数组Cnn存放n个城市间的费用值。n用数组Pn记录已经找到的费用最小的周游路线，C为其相应的费用， C初值为。n用数组Nn记录目前正在寻找的周游路线，NC为其相应的费用；n如果结点next不是N中已有的结点，且NC+CNsnext小于C，则结点next是可接受的。n如果NC+CNn1小于C，则路线N更佳，于

34、是P = N，C = NC+CNn1。2022-3-3计算机算法设计与分析46TSP的递归程序TrynTry(s)n for (i = 2; i = n; i+)n if (Accept(i)n Record(s, i)；n if (s +1= n) n if (better) TakeNewPath( ) ; n else Try(s+1);n Move-off(s, i)n return (NC+CNsi C &Ti) 数组T表示结点i尚未被选(NC+CNn1) C) TakeNewPath( ); 2022-3-3计算机算法设计与分析47Try中的子程序nRecord(s, i)

35、; NC = NC + CNsi; Ti = 0; Ns+1 = i; nMove-off(s, i); NC = NC CNsi; Ti = 1; Ns+1 = 0;nTakeNewPath( ) for (i=1; i=n; i+) Pi = Ni; C = NC + CNn1;2022-3-3计算机算法设计与分析48递归回溯求TSP的主程序nTSP(n, Cnn) n for (i = 1; i = n; i+) n Ni=0; Pi = 0; Ti = 1 n NC = 0；C = ; N1=1; T1 = 0; n Try(1); n Output(P)；n 2022-3-3计算机算

36、法设计与分析49考虑TSP的迭代程序n为了便于迭代程序中回溯的判断，我们将城市结点编号为1 n，用编号0作为末尾的标记。n先回顾一下采用末尾标记的迭代回溯法：2022-3-3计算机算法设计与分析50考虑TSP的迭代程序nBacktrack(Tree T) n unfinish = true; L.Push(T.root); n while (unfinish | L) n a = L.Pop( ); n if (a is the last mark) backastep( );nelse if (a is good) Record(a);n if (a is goal) unfinish =

37、false; output( );n else if (a has sons) L.Push-Sons(a) n else Move-off(a);要比较所有路径，无需此句 L ) 初始化后压入n-1个结点和尾标0j = 1; Nj = 1; L.Push(2,n,0); 末尾标记为0(a = = 0) backastep( ); 删除第j个结点，然后j a=Nj;j-;Move-off(Nj,a);a不在路线中且新增后的费用仍低。(Ta&NC+CNja NC+Ca1) TakeNewPath( ); Move-off(Nj, a);else j+; L.Push (2,n,0)202

38、2-3-3计算机算法设计与分析51TSP的迭代回溯nBacktrack(n, C) n j = 1; Nj = 1; L.Push (2,n,0);n while (L) a = L.Pop( ); n if (a = = 0) a=Nj;j ;Move-off(Nj, a); n else if (Ta & C NC CNja) n Record(Nj, a)；n if (j +1= = n ) n if (C NC+Ca1) n TakeNewPath( ); Move-off(Nj, a);n else j+; L.Push (2,n,0)2022-3-3计算机算法设计与分析52

39、Backtrack中的子程序nRecord(Nj,a); NC = NC + CNja; Ta = 0; Nj+1 = a; nMove-off(Nj,a); NC = NC CNja; Ta = 1; Nj+1 = 0;nTakeNewPath( ) n for (i=1; i=n; i+) Pi = Ni;n C = NC + CNn1;2022-3-3计算机算法设计与分析53迭代回溯求TSP的主程序nTSP(n, Cn+1n+1) n for (i = 1; i = n; i+) n Ni=0; Pi = 0; Ti = 1 n NC = 0；C = ; N1=1; T1 = 0; n

40、Backtrack(n, C); n Output(P)；n 2022-3-3计算机算法设计与分析54求解TSP的时间复杂性n显然TSP是一个求排列的问题。n求排列：确定n个元素的满足某种性质的排列。其搜索树称为排列树，通常有n!个叶结点，因此遍历排列树需要时间为O(n!)。n所以TSP问题的时间复杂性为O(n!)2022-3-3计算机算法设计与分析550-1背包问题n给定n个物品和一个背包。物品i的重量为wi，价值为vi，背包容量为c。问如何选择装入背包中的物品，使得装入背包的物品的价值最大？n在装入背包时，每种物品i只有两种选择，装入或者不装入，既不能装入多次，也不能只装入一部分。因此，此

41、问题称为0-1背包问题。n如果在装入背包时，物品可以切割，即可以只装入一部分，这种情况下的问题称为背包问题。2022年3月3日560-1背包问题的实例 例如，对于n=3的0/1背包问题，三个物品的重量为16, 15, 15，价值为45, 25, 25，背包容量为30，从其解空间树的根结点开始搜索，搜索过程如下：ACr=C=30，V=0HIw1=16，v1=45Cr=14，V=45B1DCrw2不可行解1JCr45x=(0,1,1)1KCr=14V=45x=(1,0,0)0M 2550不是最优解0NOGV=25不包含最优解02022-3-3计算机算法设计与分析57用回溯法解0-1背包问题n类似于

42、旅行售货员问题，用一个数组Pn存放目前取得的最优解，用变量V表示其价值；再用一个数组Nn来产生新的解，用变量NV表示其价值，用变量W表示其重量。如果新解更优，则替代原来的最优解，否则就丢弃新解。然后回溯寻找下一个新解。n为此，我们先回顾一下回溯法的一般递归算法：2022-3-3计算机算法设计与分析58用回溯法解0-1背包问题nTry(s)n 做挑选候选者的准备；n while (未成功且还有候选者)n 挑选下一个候选者next； n if (next可接受) n 记录next；n if (满足成功条件) 成功并输出结果n else Try(s+1);n if (不成功) 删去next的记录;

43、n return 成功与否考察的第s个物品只需考两种情况,选或不选,即for (i=0; i2; i+)下个候选就是i物体s可放入背包中将s放入背包中并修改权重与容量s = = n这里无论成功与否都要继续考察“记录”的逆操作2022-3-3计算机算法设计与分析59用回溯法解0-1背包问题nTry(s)n for (i = 0; i 2; i+)n if (Accept(i) n Record(s, i)；n if (s = = n) if ( better ) TakeNewChoice( ); n else Try(s+1);n Move-off(s, i);n return (W+ws*i

44、 V)2022-3-3计算机算法设计与分析600-1背包问题中的几个子程序nRecord(s, i)W=W + ws*i; NV = NV + vs*i ;Ns = i;nMove-off(s, i)W = W ws*i; NV = NV vs*i ;Ns = 0;nTakeNewChoice( ) n for (i=1; i=n; i+) n Pi = Ni; V = NV;2022-3-3计算机算法设计与分析610-1背包问题的主程序nBag(n, C, wn, vn) n for (i=1; i=n; i+) n Ni=0; Pi = 0;n NV = 0, W = 0; V = 0; n Try(1); n Output(P); 2022-3-3计算机算法设计与分析62考虑0-1