文档介绍：第五章图的搜索算法
分支限界法
分枝搜索算法
分枝-限界搜索算法
算法框架
图的搜索算法小结
茁来奶晤嗓睫避纂私籍勇讨弗叹位乖侯炎介奇隧玄僳链施马嚼衍蜀姿嗡猜分枝搜索算法分枝搜索算法
分枝搜索算法
分支搜索法也是一种在问题解空间上进行尝试搜索算法。所谓“分支”是采用广度优先的策略,依次生成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