《分枝搜索算法》由会员分享,可在线阅读,更多相关《分枝搜索算法(21页珍藏版)》请在金锄头文库上搜索。
1、第五章 图的搜索算法 55 分支限界法551 分枝搜索算法552 分枝-限界搜索算法553 算法框架 56 图的搜索算法小结 551 分枝搜索算法 1基本思想分支搜索法也是一种在问题解空间上进行尝试搜索算法。所谓 “分支”是采用广度优先的策略,依次生成E-结点所有分支,也就 是所有的儿子结点。和回溯法一样,在生成的节点中,抛弃那些不 满足约束条件(或者说不可能导出最优可行解)的结点,其余节点 加入活节点表。然后从表中选择一个节点作为下一个E-节点。选择 下一个E-节点的方式不同导致几种不同的分支搜索方式:1FIFO搜索 2LIFO搜索 3优先队列式搜索 上一页 下一页 返回首页 5.5.2 5
2、.5.3 5.61FIFO搜索一开始,根结点是唯一的活结点,根结点入队。从活结点 队中取出根结点后,作为当前扩展结点。对当前扩展结点,先 从左到右地产生它的所有儿子,用约束条件检查,把所有满足 约束函数的儿子加入活结点队列中。再从活结点表中取出队首 结点(队中最先进来的结点)为当前扩展结点,直到找 到一个解或活结点队列为空为止。返回 上一页 下一页 返回首页 LIFO搜索 优先队列式搜索 5.5.2 5.5.3 5.62LIFO搜索一开始,根结点入栈。从栈中弹出一个结点为当前扩展结点。对当前扩展结点,先从左到右地产生它 的所有儿子,用约束条件检查,把所有满足约束函数 的儿子入栈,再从栈中弹出一
3、个结点(栈中最后进来 的结点)为当前扩展结点,直到找到一个解或 栈为空为止。返回 上一页 下一页 返回首页 FIFO搜索 优先队列式搜索 5.5.2 5.5.3 5.63优先队列式搜索为了加速搜索的进程,应采用有效地方式选择 E-结点进行扩展。优先队列式搜索,对每一活结点计算一个优先级(某些信息的函数值),并根据这 些优先级,从当前活结点表中优先选择一个优先级 最高(最有利)的结点作为扩展结点,使搜索朝着 解空间树上有最优解的分支推进,以便尽快地找出 一个最优解。这种扩展方式要到下一节才用的到。返回 上一页 下一页 返回首页 FIFO搜索 LIFO搜索 5.5.2 5.5.3 5.6552 分
4、枝-限界搜索算法【例2】有两艘船,n 个货箱。第一艘船的载重量是c1,第二艘船的载重量是c2,wi 是货箱i 的重量,且w 1+w2+wnc1+c2。我们希望确定是否有一种可将所有n 个货箱全部装船的方法。若有 的话,找出该方法 FIFO限界搜索算法优先队列式分支限界法上一页 下一页 返回首页 5.5.1 5.5.3 5.6算法1的缺点有:1)在可解的情况下,没有给出每艘装载物品的方案。而要 想记录第一艘船最大装载的方案,象回溯法中用n个元素的数组 是不能实现的,可以象5.2.2小节中的例子用数组队列下标记录 解方案。这里采用构造二叉树的方法,和5.2.2小节中的例题一样只需 要记录最优解的叶
5、结点,这样二叉树就必需有指向父结点的指 针,以便从叶结点回溯找解的方案。又为了方便知道当前结点 对物品的取舍情况,还必须记录当前结点是父结点的哪一个儿 子。 数据结构:由此,树中结点的信息包括:weight;parent; LChild;。同时这些结点的地址就是抽象队列的元素,队列操作 与算法1相同 .上一页 下一页 返回首页 优先队列式分支限界法 5.5.1 5.5.3 5.62)算法1是在对子集树进行盲目搜索,我们虽然不能将搜索 算法改进为多项式复杂度,但在算法中加入了“限界”技巧,还 是能降低算法的复杂度。一个简单的现象,若当前分支的“装载上界”,比现有的最 大装载小,则该分支就无需继续
6、搜索。而一个分支的“装载上界 ”,也是容易求解的,就是假设装载当前物品以后的所有物品。 举一个简单的例子,W=50,10,10,C1=60,所构成的子集树就 无需搜索结点2的分支,因为扩展结点1后,就知道最大装载量不 会小于50;而扩展结点2时,发现此分支的“装载上界”为 w2+w3=20c1+c2) print(“no solution”); return;上一页 下一页 返回首页 优先队列式分支限界法 5.5.1 5.5.3 5.6MaxLoading(c1); if (s- bestw bestw) / 目前的最优解/ bestE = E;bestxn = ch; /bestxn取值为c
7、hreturn; b = new QNode; / 不是叶子, 添加到队列中 b-weight = wt; b-parent = E; b-LChild = ch; /新节点是左孩子时 add (Q,b) ; 上一页 下一页 返回首页 优先队列式分支限界法 5.5.1 5.5.3 5.63MaxLoading(int n, int bestx) Qnode *E; int i = 1; E= new QNode;add (Q,0) ; / 0 代表本层的尾部 E-weight=0; E-parent =null; E-Lchild=0; add (Q,E) ; bestw = 0; r = 0
8、; / E-节点中余下的重量 Ew=E-weight; for (int j =2; j weight + wi; / 检查E-节点的左孩子if (wt bestw) bestw = wt;AddLiveNode(wt,i, E ,1);if (Ew+r bestw) / 检查右孩子AddLiveNode(Ew,i,E,0); Delete (Q,E ) ; / 下一个E-节点上一页 下一页 返回首页 优先队列式分支限界法 5.5.1 5.5.3 5.64if (!E) / 层的尾部if (Empty(Q ) break;add (Q 0 ) ; / 层尾指针Delete(Q,E ) ; /
9、下一个E-节点i + + ; / E-节点的层次r = r - wi; / E-节点中余下的重量Ew = E- w e i g h t ; / 新的E-节点的重量 / 沿着从b e s t E到根的路径构造x ,x n由AddLiveNode来设置 for (j = n - 1; j 0; j-) bestxj = bestE-LChild; / 从b o o l转换为i n tbestE = bestE-parent; return bestw; 上一页 下一页 返回首页 优先队列式分支限界法 5.5.1 5.5.3 5.6上一节介绍的优先队列式扩展方式,若不加入限界策略其实是无意义的。因为
10、要说明解的最优性,不搜索完所有问题空间是不能下结论的,而要对问题空间进行完全搜索,考虑优先级也就没有意义了。优先队列式搜索通过结点的优先级,可以使搜索尽快朝着解空间树上有最优解的分支推进,这样当前最优解一定较接近真正的最优解。其后我们将当前最优解作为一个“界”,对上界(或下界)不可能达到(大于)这个界的分支则不去进行搜索,这样就缩小搜索范围,提高了搜索效率。这种搜索策略称为优先队列式分支限界法LC-检索。上一页 下一页 返回首页 FIFO限界搜索算法 5.5.1 5.5.3 5.6算法设计3:用优先队列式分支限界法解决【例2】的问题1)结点扩展方式:无论那种分支限界法,都需要有一张活 结点表。
11、优先队列的分支限界法将活结点组织成一个优先队列 ,并按优先队列中规定的结点优先级选取优先级最高的下一个 结点成为当前扩展结点。2)结点优先级确定:优先队列中结点优先级常规定为一个 与该结点相关的数值p,它一般表示其接近最优解的程度,本例 题就以当前结点的所在分支的装载上界为优先值。 3)优先队列组织:结点优先级确定后,简单地按结点优先级进行排序,就生成了优先队列。排序算法的时间复杂度较高,考虑 到搜索算法每次只扩展一个结点,回忆数据结构中堆排序,适合这 一特点且比较交换的次数最少。此题应该采用最大堆来实现优先队 列。 数据结构设计: 1)要输出解的方案,在搜索过程中仍需要生成解结构树,其结点信
12、息包括指向父结点的指针和标识物品取舍(或是父结点的左、右孩子)。 2)堆结点首先应该包括结点优先级信息:结点的所在分支的装载上界uweight;堆中无法体现结点的层次信息(level), 只能存储在结点中; AddLiveNode用于把bbnode类型的活节点加到子树中,并把 HeapNode类型的活节点插入最大堆。3)不同与算法2,由于扩展结点不是按层进行的计算结点的所在分支的装载上界时,要用数组变量r记录当前层以下的最 大重量,这样可以随时方便使用各层结点的装载上界。 算 发 设 计 3 ( 3 ) :算法3如下: HeapNode H1000; struct bbnode bbnode
13、*parent; / 父节点指针 int LChild; ; / 当且仅当是父节点的左孩子时 ,取值为1 struct HeapNodebbnode *ptr; / 活节点指针float uweight; / 活节点的重量上限int level; ; / 活节点所在层 同样为了突出算法本身的思想,对堆操作也只进行抽象的描述 : 用HeapNode代表队列类型,则HeapNode H;定义了一个堆H,相关操作有: Insert (Q,)表示入堆; DeleteMax (Q,);表示出堆。 算发设计3(4)AddLiveNode(float wt, int lev,bbnode *E, int c
14、h) bbnode *b = new bbnode;b -parent = E;b-LChild = ch;HeapNode N;N.uweight = wt;N.level=lev;N.ptr=b;Insert(H,N) ; 上一页 下一页 返回首页 FIFO限界搜索算法 5.5.1 5.5.3 5.6算发设计3(5)MaxLoading(float c, int n, int bestx) froat r100,Ew,bestw=0; rn = 0; for (int j = n-1; j 0; j-) rj=rj+1 + wj+1; int i = 1; bbnode *E = 0; Ew = 0; / 搜索子集空间树 while (i != n+1) / 不在叶子上 if (Ew + wi 0; j-) bestxj = E-LChild; E = E-parent; return Ew; 算法说明 : 算法的复杂度仍为O(2n),但通过限界策略,并没有搜索 子集