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

-。所谓“分支”是采用广度优先的策略,依次生成E-结点所有分支,也就是所有的儿子结点。和回溯法一样,在生成的节点中,抛弃那些不满足约束条件(或者说不可能导出最优可行解)的结点,其余节点加入活节点表。然后从表中选择一个节点作为下一个E-节点。选择下一个E-节点的方式不同导致几种不同的分支搜索方式:·下一页·返回首页···,根结点是唯一的活结点,根结点入队。从活结点队中取出根结点后,作为当前扩展结点。对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点(队中最先进来的结点)为当前扩展结点,……,直到找到一个解或活结点队列为空为止。返回上一页·下一页·返回首页·LIFO搜索优先队列式搜索···,根结点入栈。从栈中弹出一个结点为当前扩展结点。对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子入栈,再从栈中弹出一个结点(栈中最后进来的结点)为当前扩展结点,……,直到找到一个解或栈为空为止。返回上一页·下一页·返回首页·FIFO搜索·优先队列式搜索···,应采用有效地方式选择E-结点进行扩展。优先队列式搜索,对每一活结点计算一个优先级(某些信息的函数值),并根据这些优先级,从当前活结点表中优先选择一个优先级最高(最有利)的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支推进,以便尽快地找出一个最优解。这种扩展方式要到下一节才用的到。返回上一页·下一页·返回首页·FIFO搜索·LIFO搜索···-限界搜索算法【例2】有两艘船,n个货箱。第一艘船的载重量是c1,第二艘船的载重量是c2,wi是货箱i的重量,且w1+w2+……+wn≤c1+c2。我们希望确定是否有一种可将所有n个货箱全部装船的方法。若有的话,找出该方法FIFO限界搜索算法优先队列式分支限界法上一页·下一页·返回首页···:1)在可解的情况下,没有给出每艘装载物品的方案。而要想记录第一艘船最大装载的方案,象回溯法中用n个元素的数组是不能实现的,。这里采用构造二叉树的方法,,这样二叉树就必需有指向父结点的指针,以便从叶结点回溯找解的方案。又为了方便知道当前结点对物品的取舍情况,还必须记录当前结点是父结点的哪一个儿子。数据结构:由此,树中结点的信息包括:weight;parent;LChild;。同时这些结点的地址就是抽象队列的元素,·下一页·返回首页·优先队列式分支限界法···)算法1是在对子集树进行盲目搜索,我们虽然不能将搜索算法改进为多项式复杂度,但在算法中加入了“限界”技巧,还是能降低算法的复杂度。一个简单的现象,若当前分支的“装载上界”,比现有的最大装载小,则该分支就无需继续搜索。而一个分支的“装载上界”,也是容易求解的,就是假设装载当前物品以后的所有物品。举一个简单的例子,W={50,10,10},C1=60,所构成的子集树就无需搜索结点2的分支,因为扩展结点1后,就知道最大装载量不会小于50;而扩展结点2时,发现此分支的“装载上界”为w2+w3=20<50,无需搜索此分支,结点2不必入队。上一页·