第5章 算法设计基本方法2.ppt

《第5章 算法设计基本方法2.ppt》由会员分享，可在线阅读，更多相关《第5章 算法设计基本方法2.ppt（80页珍藏版）》请在优知文库上搜索。

1、2023-11-15第5 章算法设计基本方法22023-11-15例：0-1背包问题n设有3种物品，背包容量40公斤。物品1的重量30公斤，价值150元；物品2的重量20公斤，价值80元；物品3的重量10公斤，价值70元。2023-11-15000030150301502080005023000402205023060300301503015020801070101111110000000-1背包问题的解空间（状态树）背包问题的解空间（状态树）能优化能优化吗？吗？2023-11-15n“通用解题法”，是带优化的穷举法。n按深度优先策略，从根结点出发搜索解空间树。n对任意结点，先判断该结点是否包

2、含问题的解。n若肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；n否则，进入该子树，继续按深度优先搜索策略搜索。n解为叶子结点n这种以深度优先方式系统搜索问题解的算法称为回溯法，它适用于求解组合数较大的问题2023-11-15n在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造；n回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都被搜索遍才结束。n在它求问题的一个解时，只要搜索到问题的一个解就结束。2023-11-15回溯法n回溯法的使用1、确定问题状态结构；2、分析问题状态空间树；3、确定深度搜索与回溯规则；

3、4、确定解状态判别规则；2023-11-15回溯法的算法框架回溯法的算法框架5.2.1 问题的解空间问题的解空间5.2.2 回溯法的基本思想回溯法的基本思想5.2.3 递归回溯递归回溯5.2.4 迭代回溯迭代回溯5.2.5 示例示例2023-11-15 复杂问题常常有很多的可能解，这些可能解复杂问题常常有很多的可能解，这些可能解构成了问题的解空间。解空间也就是进行穷举的构成了问题的解空间。解空间也就是进行穷举的搜索空间，所以，搜索空间，所以，解空间中应该包括所有的可能解空间中应该包括所有的可能解解。确定正确的解空间很重要，如果没有确定正。确定正确的解空间很重要，如果没有确定正确的解空间就开始搜

4、索，可能会增加很多重复解，确的解空间就开始搜索，可能会增加很多重复解，或者根本就搜索不到正确的解。或者根本就搜索不到正确的解。5.2.1 问题的解空间问题的解空间 2023-11-15 对于任何一个问题，可能解的对于任何一个问题，可能解的表示方式表示方式和它相应的和它相应的解释解释隐隐含了解空间及其大小。含了解空间及其大小。例如，对于有例如，对于有n个物品的个物品的0/1背包问题，其可能解的表示方背包问题，其可能解的表示方式可以有以下两种：式可以有以下两种：（1）可能解由一个不等长向量组成，当物品）可能解由一个不等长向量组成，当物品i(1in)装入背包装入背包时，解向量中包含分量时，解向量中包

5、含分量i，否则，解向量中不包含分量，否则，解向量中不包含分量i，当，当n=3时，其解空间是：时，其解空间是：(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)（2）可能解由一个等长向量）可能解由一个等长向量x1,x2,xn组成，其中组成，其中xi=1(1in)表示物品表示物品i装入背包，装入背包，xi=0表示物品表示物品i没有装入背包，没有装入背包，当当n=3时，其解空间是：时，其解空间是：(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)2023-11-15 为了用回溯法求解一个具有为了

6、用回溯法求解一个具有n个输入的问题，个输入的问题，一般情况下，将其可能解表示为满足某个约束条件一般情况下，将其可能解表示为满足某个约束条件的等长向量的等长向量X=(x1,x2,xn)，其中分量，其中分量xi(1in)的的取值范围是某个有限集合取值范围是某个有限集合Si=ai1,ai2,airi，所有，所有可能的解向量构成了问题的可能的解向量构成了问题的解空间解空间。2023-11-15 问题的解空间一般用问题的解空间一般用解空间树解空间树（Solution Space Trees,也称状态空间树）的方式组织，也称状态空间树）的方式组织，树的根结点位于第树的根结点位于第1层，表示搜索的初始状态，

7、层，表示搜索的初始状态，第第2层的结点表示对解向量的第一个分量做出层的结点表示对解向量的第一个分量做出选择后到达的状态，第选择后到达的状态，第1层到第层到第2层的边上标出层的边上标出对第一个分量选择的结果，依此类推，从树的对第一个分量选择的结果，依此类推，从树的根结点到叶子结点的路径就构成了解空间的一根结点到叶子结点的路径就构成了解空间的一个可能解。个可能解。2023-11-15对于对于n=3的的0/1背包问题，其解空间树如下图所示，背包问题，其解空间树如下图所示，树中的树中的8个叶子结点分别代表该问题的个叶子结点分别代表该问题的8个可能解。个可能解。（依编号顺序搜索）对物品对物品1的选择的选

8、择对物品对物品3的选择的选择对物品对物品2的选择的选择11111100000001123457811121415310692023-11-155.2.2 回溯法的基本思想回溯法的基本思想n从根结点出发，按照深度优先策略遍历解从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。空间树，搜索满足约束条件的解。n先判断结点对应的部分解是否满足先判断结点对应的部分解是否满足约束条约束条件件，或者是否超出，或者是否超出目标函数目标函数的界，即判断的界，即判断该结点是否该结点是否包含包含问题的（最优）解。问题的（最优）解。n如果肯定不包含，则跳过对以该结点为根如果肯定不包含，则跳过对以该结点

9、为根的子树的搜索，即所谓的子树的搜索，即所谓剪枝剪枝（Pruning）；）；n否则，进入以该结点为根的子树，继续按否则，进入以该结点为根的子树，继续按照深度优先策略搜索。照深度优先策略搜索。2023-11-15例如，对于n=3的0/1背包问题，三个物品的重量为20,15,10，价值为20,30,25，背包容量为25，从下图所示的解空间树的根结点开始搜索，搜索过程如下（依编号顺序）：1不可行解不可行解价值价值=20价值价值=55 价值价值=30 价值价值=25价值价值=01111000000112811121415131069不可行解不可行解2023-11-15 回溯法的搜索过程涉及的结点（称为

10、搜索空间）回溯法的搜索过程涉及的结点（称为搜索空间）只是整个解空间树的一部分，在搜索过程中，通常只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索：采用两种策略避免无效搜索：（1）用）用约束条件约束条件剪去得不到可行解的子树；剪去得不到可行解的子树；（2）用）用目标函数目标函数剪去得不到最优解的子树。剪去得不到最优解的子树。这两类函数统称为这两类函数统称为剪枝函数剪枝函数（Pruning Function）。）。v 需要注意的是，问题的解空间树是虚拟的，并不需要注意的是，问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构，只需要需要在算法运行时构造一棵真正的树结

11、构，只需要存储从根结点到当前结点的路径。存储从根结点到当前结点的路径。2023-11-15回溯法的求解过程回溯法的求解过程 由于问题的解向量由于问题的解向量X=(x1,x2,xn)中的每个分量中的每个分量xi(1in)都属于一个有限集合都属于一个有限集合Si=ai1,ai2,airi，因此，因此，回溯法可以按某种顺序（例如字典序）依次考察。回溯法可以按某种顺序（例如字典序）依次考察。初始时，令解向量初始时，令解向量X为空，从根结点出发，选择为空，从根结点出发，选择S1的第的第一个元素作为解向量一个元素作为解向量X的第一个分量，即的第一个分量，即x1=a11;如果如果X=(x1)是问题的部分解，

12、则继续扩展解向量是问题的部分解，则继续扩展解向量X，选，选择择S2的第一个元素作为解向量的第一个元素作为解向量X的第的第2个分量个分量;否则，选择否则，选择S1的下一个元素作为解向量的下一个元素作为解向量X的第一个分量，的第一个分量，即即x1=a12。依此类推，一般情况下，如果依此类推，一般情况下，如果X=(x1,x2,xi)是问题的部是问题的部分解，则选择分解，则选择Si+1的第一个元素作为解向量的第一个元素作为解向量X的第的第i+1个分个分量时，有下面三种情况：量时，有下面三种情况：2023-11-15（1）如果是最终解，则输出这个解。如果问题只希望得到一个）如果是最终解，则输出这个解。如

13、果问题只希望得到一个解，则结束搜索，否则继续搜索其他解；解，则结束搜索，否则继续搜索其他解；（2）如果是问题的部分解，则继续构造解向量的下一个分量；）如果是问题的部分解，则继续构造解向量的下一个分量；（3）如果既不是问题的部分解也不是问题的最终解，则存在下）如果既不是问题的部分解也不是问题的最终解，则存在下面面两种情况两种情况：如果如果xi+1=ai1,k不是集合不是集合Si1的最后一个元素，则令的最后一个元素，则令xi+1=ai1,k1，即选择，即选择Si+1的下一个元素作为解向量的下一个元素作为解向量X的第的第i+1个分量；个分量；如果如果xi+1=ai1,k是集合是集合Si1的最后一个元

14、素，就回溯到的最后一个元素，就回溯到X=(x1,x2,xi)，选择，选择Si的下一个元素作为解向量的下一个元素作为解向量X的第的第i个分量，假设个分量，假设xi=aik，如果，如果aik不是集合不是集合Si的最后一个元素，则令的最后一个元素，则令xi=ai,k1；否则，；否则，就继续回溯到就继续回溯到X=(x1,x2,xi1)；2023-11-15n回溯法的三个基本步骤n1）定义问题的解空间n2）确定易于搜索的解空间结构n3）深度优先搜索解空间，并在搜索过程中用剪枝函数避免无效搜索2023-11-15回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。void backtra

15、ck(int t)if(tn)output(x);else for(int i=f(n,t);i0)if(f(n,t)=g(n,t)for(int i=f(n,t);iM，则可停止对该结点的搜索；若A+(wiwn)M，则也可停止对该结点的搜索；2023-11-15子集和数问题n算法如下：设置辅助向量Ai，记录wi是否被选入；SW表示W的剩余和，SA表示选入项的总和；初始化Ai=-1，表示未被处理过，SW=Wi，SA=0；从w0开始，进行深度优先搜索：检查是否得解以及是否需要继续对该结点进行搜索，如果需要，则 如果Ai为-1（未被处理过），则尝试不选入wi：置Ai=0，即：不选入wi；SW-=w

16、i;A+i=-1;如果Ai为0（未被选入），则尝试选入wi：置Ai=1，即：选入wi；SA+=wi;A+i=-1;如果Ai为1（已被选入），则退回上一项：Ai=-1;SW+=wi;SA-=wi;-i;2023-11-15回溯法分析n约束集D性质：若(x1xi)满足D中所有约束(条件)，则其子集(x1xj)jj也不能满足D中，不必再继续搜索问题的解。n回溯求解的效率在很大程度上依赖于：产生局部解(x1xk)的时间；计算约束所需的时间；满足局部约束的解的个数；n通常可以应用重排原理，先搜索分支较少的局部解，在约束不满足时，可以裁剪去较多的搜索分支，从而提高搜索效率。2023-11-15示例2：0-1背包问题n给定n个物品和一个背包。设物品i（1in）的重量为wi，其价值为vi，背包最大承重量为Max。问，应该如何选择物品装入背包，才能使背包内物品的总价值最大？选择物品i时，要么全部装入，要么不装入，不能只装入物品i的一部分。2023-11-15算法基本思想n如果到达叶子，返回最优解opt；否则，n试探左子树：选取物品i，计算tw，tv；递归，取下一个物品；n回溯，舍去物品i，重新计算tw，