资源描述：
《算法第5章-第4讲-图搜索-优先队列分枝限界法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4讲优先队列分支限界法每节一经典有选择地搜索3654789第4讲分支限界法上节课，我们介绍了3种不同的分支搜索方式：FIFO、LIFO、优先队列，详细分析了FIFO搜索方式。当然用LIFO搜索方式也同样可以设计出对应的算法，请同学们尝试！本节我们将详细分析如何用优先队列分支限界法来解决类似问题。优先队列式分支限界法：3654789搜索算法：分支搜索（例：深度优先，广度优先，均为按深度或宽度顺序，在全部解空间搜索）分支限界搜索（例：与分枝搜索类似，并加入结点限制，对不满足条件的结点为根的分枝子树不再进行
2、搜索）优先队列分支限界搜索例：在分支限界搜索基础上，对搜索结点的顺序按优先队列组织，使每一步搜索向最优解目标靠近，不满足条件的结点为根的分支子树不再进行搜索，遇到叶结点，即可得到一个解）第4讲分支限界法优先队列组织：结点优先级确定后,简单地按结点优先级进行排序,就生成了优先队列.但是,排序算法的时间复杂度较高。考虑到搜索算法每次只扩展一个结点,数据结构中堆排序方法适合这一特点,并且元素比较和交换的次数最少.堆通常有两类：最大堆(根部的数最大,由大到小构造堆)，最小堆(根部的数最小,由小到大构造堆)，第4
3、讲分支限界法定义：堆(heap)是一个满足下列条件的完全二叉数：（1）父结点比其左、右儿子结点都大（或小）。（2）左、右儿子分别是一个堆。即：n个元素的序列{k1,k2,…kn},当且仅当满足：ki≤k2iki≥k2iki≤k2i+1ki≥k2i+1堆定义或(i=1,2,……n/2)第4讲分支限界法例：6，4，7，9构造的大堆（从根到叶子数值减小）647969749674无序序列4筛选后的状态建堆6筛选后建成堆第4讲分支限界法例:3,8,7,4,5,9,1,6构造的小堆(从根到叶子数值增大)初始堆根节点
4、1出队，最后节点6做根节点位后的状态出堆6和3交换后的状态135478696354781913654789第4讲分支限界法例:3,8,7,4,5,9,1,6构造的小堆(从根到叶子数值增大)6和4交换后的状态出堆34567891第4讲分支限界法例:3,8,7,4,5,9,6构造的小堆(从根到叶子数值增大)初始堆进堆1进堆后建成新堆演示过程3468597134685971新堆建成第4讲分支限界法优先队列式搜索通过结点的优先级,可以使搜索尽快朝着解空间树上能到达最优解的分支推进,这样当前最优解一定较接近真正的
5、最优解.其后，我们将当前最优解作为一个“界”,对上界(或下界)不可能达到(大于)这个界的分支则不去进行搜索(结点不入队),这样就能缩小搜索范围，从而提高搜索效率.这种搜索策略称为优先队列分支限界法，简称LC-检索(LeastCostSearch)。优先队列式分支限界法：第4讲分支限界法结点扩展方式：无论那种分支限界法，都需要有一张活结点表。优先队列分支限界法将活结点组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的活结点成为当前扩展结点.结点优先级确定：优先队列中结点优先级通常是一个与该
6、结点相关的数值p,它一般表示其接近最优解的程度，装载问题就可以当前结点的装载上界为该结点的优先级。结点是否入队判定标准：结点装载上界>当前最优方案bestw,并且从该结点到根的装载方案下，装载量不超过船装载量c1优先队列式分支限界法算法设计要点：第4讲分支限界法例如：装载问题W={10，30，50}，c1=60，所构成的子集树如下图所表示：方框中红色数表示该结点的装载上界，作为结点的优先级。装载上界=已装入物品重量+未来可能装入物品的重量注意：已经“处理”过的物品(已判断是否装入)不再计算为未来可能装入
7、物品的重量。AEJBKX1=1DHIGNOFLMCX1=0X2=1X2=1X3=1X3=1X3=1X3=1X2=0X2=0X3=0X3=0X3=0X3=090909090606040108080805050300第4讲分支限界法例4.装载问题:有三个货物，其重量为W={10，30，50}，有2辆货车，其载重量为c1=60，c2=50,问：是否有方案把所有货物运走？关键概念：(1)每个字母表示车当前装货状态。(2)当前状态下剩余装载量(ew)：当前状态下剩余装载量。(3)当前状态下装载量上界：已装入货物和
8、未来可能装入的货物总重量(排除已打算不装入的货物重量)。(4)当前状态最优已装载上界：截至目前状态(包括目前状态)，所有已搜索的局部装载方案中的最大装载量(已装入的最大重量)。装50装10装30装50装50装30装50不装10不装30第4讲分支限界法1）初始队列中只有结点A；2）结点A变为E-结点扩充B入队,bestw=10;结点C的装载上界为30+50=80>bestw，也入队；3）结点B变为E-结点扩充D入队,bestw=40;结点E的
