第10章-搜索策略.pptx

《第10章-搜索策略.pptx》由会员分享，可在线阅读，更多相关《第10章-搜索策略.pptx（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 1第十章第十章 搜索策略搜索策略搜索策略是从问题的解空间中搜索问题解的方法，本章将介绍两种常见的搜索算法：回溯法和分支界限法。p回溯法p回溯法的应用p分支界限法p分支界限法的应用2 2一种既带有系统性又带有跳跃性的搜索算法，它在包含问题所有解的空间树中按照深度优先的策略从根结点出发搜索解空间树。回溯法u回溯法n回溯法在求问题所有的解时，需要回溯到树根，且在解空间树中的所有结点全部搜索完成后结束。当仅求问题的任意一个解时，只需要搜索到问题的一个解就可以结束。u算法思想n对解空间中任意一个结点，判断该结点是否不包含问题的解：不包含，则跳过以该结点为根的子树系统搜索，逐层向其祖先结点回溯；包含，

2、则进入该子树并继续按深度优先的策略进行搜索。3 3问题的解空间u问题的解空间与解空间树n解空间由长度为n的0-1向量组成，该解空间包含了对变量的所有可能的0-1赋值。树根代表了在查找解之前的初始状态。树的第一层节点代表了对解的第二个分量所做的选择，以此类推。n如果一个部分构造树（子树）仍然有可能导致一个完全解，我们说这个部分分解在树中的相应节点是有希望的，否则说是没希望的。n叶子要么代表没希望的，要么代表算法找到完全解。4 4问题的解空间u0-1背包问题（n种物品）【例1】当n=3时，其解空间是：(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(

3、1,1,0),(1,1,1)0-10-1背包问题的解空间树背包问题的解空间树从根到叶路从根到叶路径上编码即径上编码即解空间元素解空间元素若取W=（16,15,15），P=（40,25,25），C=30 时间复杂度：O(2n)5 5回溯策略的基本思想u基本思想n(1)当前结点成为活结点及扩展结点；n(2)从当前扩展结点向纵深方向搜索并移至一个新结点，这个新结点就成为一个新的活结点及当前的扩展结点；n(3)若当前扩展结点不能向纵深移动则成死结点，回溯至最近的活结点成为当前扩展结点；n(4)递归搜索，直至找到所要求的解或解空间中已无活结点时为止。从开始结点(根结点)出发，以深度优先的方式搜索整个解空

4、间：6 6回溯策略的基本思想(1)从根结点A开始搜索（唯一的活结点及当前扩展结点）。(2)从结点A沿纵深方向先移至结点B或结点C(以先选结点B为例)，此时A和B是活结点，结点B成为当前的扩展结点。由于选取了w0，因此在结点B处剩余背包容量r=14，获取的价值为45。(3)从结点B可移至结点D或结点E，由于移至结点D至少需要的背包容量为w1=15，而当前仅有的剩余容量r=14，因此移到结点D将导致一个不可行解；而移到结点E不需要背包容量，因而是可行的，此时结点E成为新的扩展结点，在结点E处，r=14，获取的价值为45。(4)这时结点A、B和E是活结点。从结点E可移到结点J或结点K，类似地，移到结

5、点J导致一个不可行的解，而移到结点K是可行的，于是结点K成为新的扩展结点。(5)由于K是叶子结点，因此得到一个可行的解，即x=(1,0,0)，获得的价值为45。同理可获得其他可行解，从其中选择一个最优解作为问题最终解。【例2】n=3的0-1背包问题。设w=16,15,15，v=45,25,25，c=30分析：7 7回溯策略的基本思想u运用回溯法解题的关键要素有以下三点n(1)针对给定的问题，定义问题的解空间；n(2)确定易于搜索的解空间结构；n(3)以深度优先方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。8 8递归和迭代回溯void BackTrace(int t)if(tn)Out

6、put(x);else for(int i=f(n,t);i 0)if(f(n,t)=g(n,t)for(int i=f(n,t);i n)Output(x);else for(int i=0;i n)Output(x);else for(int i=0;i n)for(int j=1;j=n;j+)bestxj=xj;bestn=cn;return;/检查顶点检查顶点i与当前团是否连接与当前团是否连接./见下页见下页1616回溯法的应用/检查顶点检查顶点i与当前团是否连接与当前团是否连接 int OK=1;for(int j=1;j bestn)xi=0;BackTrace(i+1);int

7、 MaxClique(int*a,int v,int n)cn=0;bestn=0;bestx=v;BackTrace(1);return bestn;1717回溯法的应用n问题描述给定一个无向连通图G和m种不同的颜色，用这些颜色为图G的各顶点着色，每个顶点染一种颜色，那么是否存在一种着色方案使得相邻顶点不重色。若一个图至少需要m种颜色才能使图中任何相邻顶点不重色，则m称为该图的色数。注：如果一个图的所有顶点和边都能用某种方式画在一个平面上且没有任何两条边相交，则称这个图为平面图。u图的m着色问题求一个图的色数m的问题称为图的m可着色优化问题。1818回溯法的应用邻接矩阵a表示无向连通图G=(

8、V,E)，若(i,j)E，则aij=1；否则aij=0。用整数1m表示m种不同颜色，顶点i所染的颜色用xi表示，因此该问题的解向量可表示为x1:n。问题的解空间可表示为一棵高度为n+1的完全m叉树，解空间树的第i(1in)层中的每一个结点都有m个孩子，其中每个孩子对应于xi的m种可能的着色之一；第n+1层结点均为叶子结点。n算法设计n n=3 3和和m=3m=3时问题的解空间时问题的解空间树树1919回溯法的应用求解图的m可着色问题的过程就是遍历解空间树的过程，并在遍历过程中记录所有可行的着色方案，遍历过程是向前搜索和回溯两个过程的综合，以期望获得所有可能的解(着色方案)。/N-图的顶点数图的

9、顶点数/M-可用的颜色数可用的颜色数/a-图的邻接矩阵图的邻接矩阵/x-当前的解当前的解/sum-可可m着色的方案数着色的方案数#define N 20#define M 5int sum,pN+1,*x,*aN+1N+1;sum=0;x=p;2020回溯法的应用void mColoring()for(int i=0;i N)sum+;for(int i=1;i=N;i+)printf(%d ,xi);printf(n);else for(int i=1;i=N;i+)t=i;if(OK(t)BackTrace(t+1);时间复杂度时间复杂度O(nmO(nmn n)2121回溯法的应用int

10、OK(int t)for(int i=1;i=N;i+)if(ati=1)&(xi=xt)return 0;return 1;(1)递归函数BackTrace(1)实现整个解空间回溯搜索，BackTrace(i)搜索解空间中的第i层子树。说明：(3)in时当前扩展结点Z是解空间中的一个内部结点，该结点有xi=1,2,3,m共m个孩子结点，由函数OK检查其可行性，并以深度优先的方式递归地对可行子树进行搜索，或剪去不可行子树。(2)in时表示该算法已搜索到一个叶子结点，得到新的m着色方案。2222回溯法的应用设某旅行售货员要到多个城市推销商品，已知各城市之间的路程(旅费)，现在为其设计一条售货路线

11、，要求从某驻地出发经过每个城市一遍，最后又回到驻地，且使总的路程(旅费)最小。u旅行售货员问题n问题描述设G=(V,E)是一个带权图，其中，各条边的权(费用)为正整数；每一条周游路线是包含V中所有顶点的一条回路；一条周游路线的费用是该回路上所有边的权之和。所谓旅行售货员问题就是要在图G中找出一条有最小费用的周游路线。问题形式描述：2323回溯法的应用n算法设计旅行售货员问题的解空间树是一棵排列树，根据排列树的递归算法模板，可得到如下算法：/n-图的顶点数；图的顶点数；/an+1n+1-图的邻接矩阵；图的邻接矩阵；/xn-当前解；当前解；/bestxn+1-当前最优解；当前最优解；/cc-当前费

12、用；当前费用；/bestc-当前最优值；当前最优值；/NoEdge-无边标记；无边标记；void BackTrace(int i)if(i=n)if(axn1xn!=NoEdge)&(axn1!=NoEdge)&(cc+axn1xn+axn1)bestc)|(bestc=NoEdge)for(int j=1;j=n;j+)bestxj=xj;2424回溯法的应用 else for(int j=i;j=n;j+)/是否可以进入是否可以进入xj子树子树 if(axi1xj!=NoEdge)&(cc+axi1xi)bestc)|(bestc=NoEdge)/搜索子树搜索子树Swap(xi,xj);c

13、c+=axi1xi;BackTrace(i+1);cc=axi1xi;Swap(xi,xj);void TravelRoute()for(int i=1;i=n;i+)xi=i;/初始化初始化 bestc=NoEdge;cc=0;BackTrace(2);2525回溯法的应用(1)递归函数BackTrace中，当i=n时，当前扩展结点是排列树的叶子结点的双亲结点，此时算法检测图G是否存在两条边：一条从顶点xn-1到xn的边和一条从顶点xn到顶点x1的边。如果这两条边都存在，则找到了一条旅行售货员回路，此时算法还需要判断这条回路的费用是否优于已经找到的当前最优回路的费用bestc，如果是，则必须

14、更新当前最优值bestc和当前最优解bestx。说明：(2)当in时，当前扩展结点位于排列树的第i-1层，图G中存在从顶点xi-1到顶点xi的边时，x1:i构成图G的一条路径，且当x1:i的费用小于当前最优值时算法进入排列树的第i层；否则将剪去相应的子树。算法中的变量cc记录当前路径x1:i的费用。上述整个算法的时间复杂度为O(n!)2626分支界限法解题目标不同：分支界限法的解题目标是找出解空间树T中满足约束条件的一个解，或是在满足约束条件的解中找一个使目标函数值极大或极小的解，即某种意义下的最优解；而回溯法的解题目标是找出T中满足约束条件的所有解。在解空间树T上的搜索方式不同：回溯法以深度

15、优先方式搜索T；而分支界限法以广度优先或最小耗费优先的方式搜索T。n分支界限法是一种在问题的解空间树T上搜索问题解的算法n分支界限法与回溯法的区别2727分支界限法n在每一个活结点处计算函数值(限界)，并根据已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间中有最优解的分支推进，以便尽快找出一个最优解。u搜索策略n在扩展结点处生成其所有的孩子结点(分支)，然后再从当前的活结点表中选择下一个扩展结点；n分支界限法以广度优先或最小耗费(最大效益)优先的方式搜索问题的解空间树2828分支界限法u常见解空间树n(1)每一个活结点只有一次机会成为扩展结点，一次性产生其所

16、有孩子结点；孩子结点中导致不可行解或导致非最优解的结点被舍弃，其余结点被加入活结点表。然后从活结点表中取当前扩展结点的下一个结点成为扩展结点。n(2)重复上述结点的扩展过程，直至找到所需的解或活结点表空时为止。子集树和排列树u基本思想2929分支界限法u活结点表中选择下一个扩展结点作为当前扩展结点的方法n(1)一般队列方法。一般队列方法是将活结点表组织成一般队列，并按队列中结点先进先出的原则选取下一个结点作为当前扩展结点。n(2)优先级队列方法。优先级队列方法是将活结点表组织成一个优先级队列，并按优先级队列中规定的结点优先级来选取优先级最高的下一个结点作为当前扩展结点。3030分支界限法【例2

17、】n=3时的0-1背包问题。设w=16,15,15,p=45,25,25,c=30，其解空间树如图：分支界限法搜索解空间树的分支界限法搜索解空间树的方法与解空间树的广度优先方法与解空间树的广度优先遍历算法极为相似，唯一不遍历算法极为相似，唯一不同之处是分支界限法不搜索同之处是分支界限法不搜索以不可行结点为根的子树。以不可行结点为根的子树。3131分支界限法一般队列分支界限法：用队列存放活结点表；算法从根结点开始，初始时活结点队列为空，结点A是当前活结点；结点A的两个孩子B和C都是可行结点，故将结点B和结点C入队，并且舍弃当前扩展结点A；在活结点队列中取出活结点B作为当前扩展结点，扩展结点B有两

18、个孩子D和E，由于结点D是不可行结点故舍弃，结点E是可行结点故入队；再从活结点队列中取出结点C作为当前扩展结点，继续上述计算，直至活结点队列空为止，算法终止。该算法搜索得到的最优值是50。3232分支界限法u分支界限法与回溯法的区别n求解目标不同回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。n搜索方式的不同回法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先（最大效益）的方式搜索解空间树。3333分支界限法的应用分支限界法：每一个活结点只有一次机会成为扩展结点。活

19、结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。回溯法：当探索到某一结点时，要先判断该结点是否包含问题的解。如果包含，就从该结点出发继续探索下去；如果该结点不包含问题的解，则逐层向其祖先结点回溯。n对扩展节点的扩展方式不同n对存储空间的要求不同 分支限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。3434分支界限法的应用u装载问题n问题描述设有n个集装箱，计划将其装上两艘载重量分别为c1和c2的轮船，其

20、中集装箱i的重量为wi，且 。那么是否有一个合理的装载方案，可将n个集装箱装上这两艘轮船。n问题分析当 时，装载问题等价于子集和问题；当c1=c2，且 时，装载问题就等价于划分问题。3535分支界限法的应用采用下面的策略可以得到一个最优装载方案：n算法设计(1)将第一艘轮船尽可能地装满；(2)将剩余的集装箱装到第二艘轮船上。第一艘轮船尽可能地装满等价于选取全体集装箱的一个子集，使该子集中的集装箱重量之和最接近c1。由此可知，装载问题等价于以下特殊的0-1背包问题：装载问题是一个子集选取问题，其解空间树是一棵子集树3636分支界限法的应用n一般队列分支界限法void MaxLoading(int

21、 w,int c,int n)int layer,Ew,bestw,wt;layer=1;Ew=0;bestW=0;/初始化初始化 InitQueue(Q);/初始化队列，解空间树中的根结点入队初始化队列，解空间树中的根结点入队 add(Q,Ew);add(Q,1)；/搜索子集解空间树搜索子集解空间树 while(!QueueIsEmpty(Q)delete(Q,Ew);/此时的此时的Ew为为0if(Ew=1)if(IsEmpty(Q)break;add(Q,1);delete(Q,Ew);layer+;3737分支界限法的应用 /检查左孩子结点检查左孩子结点wt=Ew+wlayer;if(w

22、tbestw)bestw=wt;if(layer bestw)/可行叶子结点可行叶子结点 bestw=wt;else /非叶子结点非叶子结点 add(Q,wt)；说明：函数EnQueue将活结点加入到活结点队列Q中。该函数检查i是否等于n，如果i=n，则表示当前活结点为叶子结点，因叶子结点不会进一步扩展，因此不必将其加入到活结点队列，此时检查该叶子结点所表示的可行解是否优于当前最优解，并适时更新当前最优解；否则当前活结点是内部结点，应加入到活结点队列中。3939分支界限法的应用n算法改进设bestw是当前最优解，Ew是当前扩展结点对应的重量，r是剩余集装箱的重量。若Ew+rbestw，则可以将

23、扩展结点所对应的子树剪去。函数MaxLoading将bestw初始化为0，直至搜索到叶子结点时才更新bestw，因此在算法搜索到第一个叶子结点之前bestw=0，且r0，故Ew+rbestw总成立，即此时右子树测试不起作用。为了使上述右子树测试尽早发挥作用，应提前更新bestw。而我们知道算法最终找到的最优值是所求问题的子树中所有可行结点对应的重量最大值，并且结点所对应的重量仅在搜索进入左子树时增加，因此可以在算法每次进入左子树时更新bestw的值。4040分支界限法的应用void MaxLoading(int w,int c,int n)InitQ();/初始化队列初始化队列 int Ew,

24、bestw,r,layer,wt,i;Ew=0;/扩展结点所对应的载重量扩展结点所对应的载重量 bestw=0;/当前的最优载重量当前的最优载重量 r=0;/剩余集装箱重量剩余集装箱重量 layer=1;/当前扩展结点所处的层当前扩展结点所处的层 for(int j=2;j=n;j+)r+=wj;add(Q,Ew);/起始设置队列起始设置队列 add(Q,1);while(!IsEmpty(Q)delete(Q,Ew);if(Ew=1)if(IsEmpty(Q)break;add(Q,1);delete(Q,Ew);layer+;r=wlayer；4141分支界限法的应用 /检查左孩子结点检查

25、左孩子结点wt=Ew+wlayer;/左孩子结点的重量左孩子结点的重量if(wtbestw)bestw=wt;/更新最优值更新最优值 if(layer bestw)&(layerweight=wt;q-parent=E-parent;q-flagOfChild=flagChild;add(Q,q);将活结点加入到活结点队列中的函数EnQueue如下：4343分支界限法的应用int MaxLoad(int w,int c,int n,int bestx)/返回最优载重量，返回最优载重量，bestx返回最优解返回最优解 struct QNode*aQ;/活结点队列活结点队列 add(aQ,-1);

26、/同层结点尾部标志同层结点尾部标志 int i=1;/当前扩展结点所处的层当前扩展结点所处的层 int Ew=0;/对应扩展结点的载重量对应扩展结点的载重量 int bestw=0;/当前最优载重量当前最优载重量 int r=0;/剩余集装箱重量剩余集装箱重量 for(int j=2;j=n;j+)r+=wj;struct QNode*Eq=0;/当前扩展结点当前扩展结点 struct QNode*bestE;/当前最优扩展结点当前最优扩展结点 4444分支界限法的应用 /搜索子集空间树搜索子集空间树 while(true)/检查左孩子结点检查左孩子结点int wt=Ew+wi;if(wt b

27、estw)bestw=wt;EnQueue(aQ,wt,i,n,bestw,Eq,bestE,bestx,1);/检查右孩子结点检查右孩子结点if(Ew+rbestw)EnQueue(aQ,wt,i,n,bestw,Eq,bestE,bestx,0);delete(aQ,Eq);/取下一个扩展结点取下一个扩展结点if(!Eq)/同层结点尾部同层结点尾部 if(IsEmpty(aQ)break;add(aQ,0);/同层结点尾部标志同层结点尾部标志 delete(aQ,Eq);/取下一个扩展结点取下一个扩展结点 i+;/进入下一层进入下一层 r-=wi;/while4545分支界限法的应用 /构

28、造当前最优解构造当前最优解 for(int j=n-1;j 0;j-)bestxj=bestE-flagOfChild;bestE=bestE-parent;return bestw;4646分支界限法的应用n构造最优解 为了在算法结束后能方便地构造出与最优值相对应的最优解，算法必须记录相应子集树中从活结点到根的路径，为此，必须设置指向其双亲结点的指针，并设置左右孩子标志。活结点队列的数据结构如下：struct QNode struct QNode*parent;int flagOfChild;/0表示左孩子；表示左孩子；1表示右孩子表示右孩子 int weight;4747分支界限法的应用印

29、刷电路板将布线区域划分成nm个方格阵列，如图(a)所示。电路布线问题要求确定连接方格a的中点和方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，并且要求所布线路不能相交，如图(b)所示。为了避免线路相交，已经布线的方格应设置封锁标记，其他线路不允许穿过已经封锁的方格。u布线问题n问题描述4848分支界限法的应用n分析布线问题的解空间是一个图，用队列分支界限法解此问题。从起始位置a开始，将其作为第一个扩展结点，与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。接着从活结点队列中取出队首结点作为下一个扩展结点，

30、并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直持续到算法搜索到目标方格b，或活结点队列空时结束。4949分支界限法的应用首先考虑记录电路板上某方格位置：用结构体表示。结构体有row和col两个成员。其次需要表示布线前进的方向：布线可沿右、下、左、上四个方向移动，分别用0、1、2、3表示。再用offseti.row和offseti.col(i=0,1,2,3)表示沿着四个方向移动一步时对于当前方格的相对位移，如下表所示。移动方向行位移(offseti.row)列位移(offseti.col)0右011下102左0-13上-10用二位数组gridij表示电路板上某方

31、格的布线，gridij=0表示该方格允许布线；gridij=1表示该方格不允许布线。5050分支界限法的应用void FindPath(struct Position beginP,struct Position endP)int finished=0;if(beginP.row=endP.row)&(beginP.col=endP.col)pathLen=0;else for(int i=0;i=m+1;i+)grid0i=1;gridn+1i=1;for(int i=0;i=n+1;i+)gridi0=1;gridim+1=1;n算法5151分支界限法的应用 struct Position

32、 offset4;offset0.row=0;offset0.col=1;offset1.row=1;offset1.col=0;offset2.row=0;offset2.col=-1;offset3.row=-1;offset3.col=0;int numbersOfNeighbor=4;struct Position currentP,currentNeighbor;currentP.row=beginP.row;currentP.col=beginP.col;gridbeginP.rowbeginP.col=MAX;struct ActiveNodeQueue activeQ;5252

33、分支界限法的应用 while(finished=0)for(int i=0;i=0;j-)pathj.row=currentP.row;pathj.col=currentP.col;/找前趋位置找前趋位置 for(int i=0;i numbersOfNeighbor;i+)rentNeighbor.row=currentP.row+offseti.row;currentNeighbor.col=currentP.col+offseti.col;if(gridcurrentNeighbor.rowcurrentNeighbor.col=j)break;currentP.row=currentN

34、eighbor.row;currentP.col=currentNeighbor.col;/for(j=printf(有解n);else printf(无解n);/if(beginP.row=endP.row)&./FindPath5454分支界限法的应用【例3】在一个77方格阵列中布线（如下图所示），其中起始位置a=(3,2)；目标位置b=(4,6)；阴影方格表示被封锁的方格；算法标记过程如图(a)所示；布线路径如图(b)所示。由于每个方格成为活结点并进入活结点队列的次数最由于每个方格成为活结点并进入活结点队列的次数最多一次，因此活结点队列最多处理活结点个数的复杂度为多一次，因此活结点队列最

35、多处理活结点个数的复杂度为O(mn)O(mn)，扩展每个结点需要的时间复杂度为，扩展每个结点需要的时间复杂度为O(1)O(1)，构造相，构造相应的最短距离需要的时间复杂度为应的最短距离需要的时间复杂度为O(pathLen)O(pathLen)，故算法的，故算法的时间复杂度为时间复杂度为O(mn)O(mn)。5555本章小结l搜索策略反映了状态空间或问题空间扩展的方法，也决定了状态或问题的访问顺序。l回溯法可求出解空间树中满足约束条件的所有解。l在具体实际应用中，采用何种搜索策略需根据问题的特点及实际的操作和资源等因素综合考虑。l分支界限法是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解，需要比回溯法大得多的存储空间。