算法设计与分析 课件 第七章 分支限界 .ppt

7.3.2单源最短路径问题给定带权有向图G=(V,E),其中每条边的权是非负实数.另外,还给定V中的一个顶点,称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路径的长度是指路径上各边权之和。这个问题通常称为单源最短路径问题。单源最短路径问题如图所示的有向图G，每一条边都有一个非负权值，求源点S到图中各个结点之间的最短路径。算法分析采用优先队列式分支限界法求解单源最短路径问题，可以构建一个基于结点优先级的小根堆来存放活动结点表：结点的优先级=源点到该结点的当前路径长度初始时源点到其余个结点之间距离长度dist[i]设置为无穷大，当然源点本身的dist[S]=0，并将源点S加入优先队列（小根堆）。图的邻接矩阵存储到二维数组edge内。算法分析从小根堆中取出堆顶元作为当前扩展结点i，并依次检查与结点i相邻结点j是否满足下列条件：dist[i]+edge[i][j]dist[j]则更新结点j的优先级dist[j]=dist[i]+edge[i][j]，并将j结点加入小根堆（优先队列）。否则被舍去处理。重复上述过程，直到小根堆(优先队列)为空为止。Sijdist[i]edge[i][j]dist[j]实例（1）开始时小根堆只有源点S，取堆顶元S作为扩展结点，与S相邻的结点A，B，C，都满足更新其优先级条件，所以更新A、B、C的优先级，将A、B、C结点加入小根堆，结点加入小根堆的过程中会重新调整建堆。dist[A]=dist[S]+edge[S][A]=2dist[B]=dist[S]+edge[S][B]=3dist[C]=dist[S]+edge[S][C]=4此时的解空间树如下图所示。SABC（1）队列式分支限界法队列式（FIFO）式分支限界法的基本思想：（1）首先将初始状态节点放入活结点队列中。（2）若队列非空，则重复下列步骤：①出队，将出队结点作为当前扩展结点。②判断当前扩展结点是否为目标结点，若是目标结点，则有哪些信誉好的足球投注网站到一个可行解而结束。③对当前扩展结点进行扩展。在扩展节点时，一次性产生它的所有子结点，并利用剪枝函数检测，把满足约束和限界条件的的子结点依次加入活结点队列。（3）重复（2），直到队列为空，则有哪些信誉好的足球投注网站失败结束。（2）优先队列式分支限界法将活结点表组成一个优先队列，按照优先队列中指定的结点优先级，选取优先级最高的结点作为当前扩展结点，以优先队列储存活结点。结点的优先级常用一个与该结点相关的限界函数值来表示。也称为最小耗费优先分支限界法(LC)该策略与队列式分支限界法的主要区别是：优先队列式分支限界法的活结点表组成一个优先队列，每个活结点入队时会计算其优先级，优先级最高的活结点位于队首位置。（2）优先队列式分支限界法优先队列通常采用堆数据结构来组织，通过维护堆属性，可以保证优先队列的入队操作时按结点元素优先级重新排序，也即队列中优先级最高的结点元素始终位于队列首部位置。每次出队的队首结点总是当前队列中具有优先级最高（最有利）的结点成为当前扩展结点，使有哪些信誉好的足球投注网站朝着解空间树有最优解的分支方向快速推进，以便快速找到问题的最优解。优先队列式分支限界法基本思想（1）确定合理的限界函数，并根据限界函数确定问题的目标函数的上（下）界，又称耗费函数值或代价值。（2）初始化一个空的优先队列H，并将初始状态加入队列。初始化一个变量best_score用于保存当前找到的最优解（初值=无穷大）。（3）当队列H不为空时，执行以下步骤：优先队列式分支限界法基本思想①出队结点保存为node。②ifnode结点对应更优的解then更新当前最优解best_score的值。③fornode的每一个子结点child：a.计算child结点的目标函数限界值。b.ifchild满足解的约束条件且耗费函数值不超过目标函数的当前限界thenc.将child加入队列H。（4）重复（3）直到队列H为空（5）返回这时的best_score作为最优解。计算机算法设计与分析第7章分支限界法7.3.1装载问题一个农场需要将大量农产品运输到市场上去，假设农场现有n种不同的农产品和一辆载重量为c的车辆，农产品i的重量为wi，价值为vi，每种农产品只有装车和不装车两种选择。如何选择装入车辆的农产品，使得车辆不超重的情况下一次装下的农产品总重量最大。7.3.1装载问题以n=4种农产品为例，车辆载重量c=10，每种农产品的重量W={6,7,2,4}，即w1=6，w2=7,w3=2,w4=4。4种农产品的装载可以表示为一个四元