图的搜索算法2.ppt

第五章图的搜索算法
分支限界法
分枝搜索算法
分枝-限界搜索算法
算法框架
图的搜索算法小结
分枝搜索算法

分支搜索法也是一种在问题解空间上进行尝试搜索算法。所谓“分支”是采用广度优先的策略,依次生成E-结点所有分支,也就是所有的儿子结点。和回溯法一样,在生成的节点中,抛弃那些不满足约束条件(或者说不可能导出最优可行解)的结点,其余节点加入活节点表。然后从表中选择一个节点作为下一个E-节点。选择下一个E-节点的方式不同导致几种不同的分支搜索方式:



上一页· 下一页· 返回首页· · ·

一开始,根结点是唯一的活结点,根结点入队。从活结点队中取出根结点后,作为当前扩展结点。对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点(队中最先进来的结点)为当前扩展结点,……,直到找到一个解或活结点队列为空为止。

返回
上一页· 下一页· 返回首页· LIFO搜索优先队列式搜索·· ·

一开始,根结点入栈。从栈中弹出一个结点为当前扩展结点。对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子入栈,再从栈中弹出一个结点(栈中最后进来的结点)为当前扩展结点,……,直到找到一个解或栈为空为止。
返回
上一页· 下一页· 返回首页· FIFO搜索· 优先队列式搜索·· ·

为了加速搜索的进程,应采用有效地方式选择E-结点进行扩展。优先队列式搜索,对每一活结点计算一个优先级(某些信息的函数值),并根据这些优先级,从当前活结点表中优先选择一个优先级最高(最有利)的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支推进,以便尽快地找出一个最优解。这种扩展方式要到下一节才用的到。
返回
上一页· 下一页· 返回首页· FIFO搜索· LIFO搜索· · ·
分枝-限界搜索算法
【例2】有两艘船,n 个货箱。第一艘船的载重量是c1,第二艘船的载重量是c2,wi 是货箱i 的重量,且
w 1+w2+……+wn≤c1+c2。
我们希望确定是否有一种可将所有n 个货箱全部装船的方法。若有的话,找出该方法
FIFO限界搜索算法
优先队列式分支限界法
上一页· 下一页· 返回首页· · ·
算法1的缺点有:
1)在可解的情况下,没有给出每艘装载物品的方案。而要想记录第一艘船最大装载的方案,象回溯法中用n个元素的数组是不能实现的,。
这里采用构造二叉树的方法,,这样二叉树就必需有指向父结点的指针,以便从叶结点回溯找解的方案。又为了方便知道当前结点对物品的取舍情况,还必须记录当前结点是父结点的哪一个儿子。
数据结构:由此,树中结点的信息包括:weight;parent; LChild;。同时这些结点的地址就是抽象队列的元素,队列操作与算法1相同.
上一页· 下一页· 返回首页· 优先队列式分支限界法· · ·
2)算法1是在对子集树进行盲目搜索,我们虽然不能将搜索算法改进为多项式复杂度,但在算法中加入了“限界”技巧,还是能降低算法的复杂度。
一个简单的现象,若当前分支的“装载上界”,比现有的最大装载小,则该分支就无需继续搜索。而一个分支的“装载上界”,也是容易求解的,就是假设装载当前物品以后的所有物品。
举一个简单的例子,W={50,10,10},C1=60,所构成的子集树就无需搜索结点2的分支,因为扩展结点1后,就知道最大装载量不会小于50;而扩展结点2时,发现此分支的“装载上界”为w2+w3=20<50,无需搜索此分支,结点2不必入队。
上一页· 下一页· 返回首页· 优先队列式分支限界法· · ·
数据结构:相应地,当前最大装载bestw不仅仅对叶结点计算,每次搜索装载情况(搜索左儿子)时,都重新确定bestw的值。为了方便计算一个分支的“装载上界”,用变量r记录当前层以下的最大重量。公共变量的定义:
float bestw,w[100],bestx[100];
int n;
Queue Q;
struct QNode
{ float weight;
QNode *pare