第五章2 图的搜索算法.ppt

《第五章2 图的搜索算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章图的搜索算法5．5分支限界法5．5．1分枝搜索算法5．5．2分枝-限界搜索算法5．5．3算法框架5．6图的搜索算法小结5．5．1分枝搜索算法1．基本思想分支搜索法也是一种在问题解空间上进行尝试搜索算法。所谓“分支”是采用广度优先的策略，依次生成E-结点所有分支，也就是所有的儿子结点。和回溯法一样，在生成的节点中，抛弃那些不满足约束条件（或者说不可能导出最优可行解）的结点，其余节点加入活节点表。然后从表中选择一个节点作为下一个E-节点。选择下一个E-节点的方式不同导致几种不同的分支搜索方式：1．FIFO搜索2．LIFO搜索3．优先队

2、列式搜索上一页·下一页·返回首页·5.5.2·5.5.3·5.61．FIFO搜索一开始，根结点是唯一的活结点，根结点入队。从活结点队中取出根结点后，作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，……，直到找到一个解或活结点队列为空为止。返回上一页·下一页·返回首页·LIFO搜索优先队列式搜索·5.5.2·5.5.3·5.62．LIFO搜索一开始，根结点入栈。从栈中弹出一个结点为当前扩展结点。对当前扩

3、展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子入栈，再从栈中弹出一个结点（栈中最后进来的结点）为当前扩展结点，……，直到找到一个解或栈为空为止。返回上一页·下一页·返回首页·FIFO搜索·优先队列式搜索·5.5.2·5.5.3·5.63．优先队列式搜索为了加速搜索的进程，应采用有效地方式选择E-结点进行扩展。优先队列式搜索，对每一活结点计算一个优先级（某些信息的函数值），并根据这些优先级，从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地

4、找出一个最优解。这种扩展方式要到下一节才用的到。返回上一页·下一页·返回首页·FIFO搜索·LIFO搜索·5.5.2·5.5.3·5.65．5．2分枝-限界搜索算法【例2】有两艘船，n个货箱。第一艘船的载重量是c1，第二艘船的载重量是c2，wi是货箱i的重量,且w1+w2+……+wn≤c1+c2。我们希望确定是否有一种可将所有n个货箱全部装船的方法。若有的话，找出该方法FIFO限界搜索算法优先队列式分支限界法上一页·下一页·返回首页·5.5.1·5.5.3·5.6算法1的缺点有:1）在可解的情况下，没有给出每艘装载物品的方案。而要想记录

5、第一艘船最大装载的方案，象回溯法中用n个元素的数组是不能实现的，可以象5.2.2小节中的例子用数组队列下标记录解方案。这里采用构造二叉树的方法，和5.2.2小节中的例题一样只需要记录最优解的叶结点，这样二叉树就必需有指向父结点的指针，以便从叶结点回溯找解的方案。又为了方便知道当前结点对物品的取舍情况，还必须记录当前结点是父结点的哪一个儿子。数据结构：由此，树中结点的信息包括：weight;parent;LChild;。同时这些结点的地址就是抽象队列的元素，队列操作与算法1相同.上一页·下一页·返回首页·优先队列式分支限界法·5.5.1·

6、5.5.3·5.62）算法1是在对子集树进行盲目搜索，我们虽然不能将搜索算法改进为多项式复杂度，但在算法中加入了“限界”技巧，还是能降低算法的复杂度。一个简单的现象，若当前分支的“装载上界”，比现有的最大装载小，则该分支就无需继续搜索。而一个分支的“装载上界”，也是容易求解的，就是假设装载当前物品以后的所有物品。举一个简单的例子，W={50，10，10}，C1=60，所构成的子集树就无需搜索结点2的分支，因为扩展结点1后，就知道最大装载量不会小于50；而扩展结点2时，发现此分支的“装载上界”为w2+w3=20<50，无需搜索此分支，结点

7、2不必入队。上一页·下一页·返回首页·优先队列式分支限界法·5.5.1·5.5.3·5.6数据结构：相应地，当前最大装载bestw不仅仅对叶结点计算，每次搜索装载情况（搜索左儿子）时，都重新确定bestw的值。为了方便计算一个分支的“装载上界”，用变量r记录当前层以下的最大重量。公共变量的定义：floatbestw,w[100],bestx[100];intn；QueueQ;structQNode{floatweight;QNode*parent;QNodeLChild;}上一页·下一页·返回首页·优先队列式分支限界法·5.5.1·5.

8、5.3·5.6算法如下：main(){intc1,c2,n,s=0,i;input(c1,c2，n);for(i=1;i<=n;i++){input(w[i])；s=s+w[i]；}if(s<=c1ors<