算法设计与分析耿国华第六章.ppt

第六章 分支限界法 6.1 分支限界法基础—基本思想 6.1.1 基本思想 对有约束条件的最优化问题的所有可行解的空间进行有哪些信誉好的足球投注网站。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集就可以不予考虑了，从而缩小了有哪些信誉好的足球投注网站范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。 6.1 分支限界法基础—基本思想 分支限界法是在问题的解空间上有哪些信誉好的足球投注网站问题解的算法。以广度优先或以最小耗费（最大效益）优先的方式有哪些信誉好的足球投注网站问题的解空间树。 有哪些信誉好的足球投注网站策略： 在当前扩展结点处，先生成其所有儿子结点，舍弃不可能通向最优解的结点，将其余的加入到活结点表中。 然后再在当前活结点表中选择下一个扩展结点。 重复上述结点的扩展过程，直到找到所需的解或活结点表为空。 6.1 分支限界法基础—基本思想 为了有效的选择下一扩展结点，加速有哪些信誉好的足球投注网站进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，是有哪些信誉好的足球投注网站朝着解空间上的最优分支推进，以便尽快找出一个最优解。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入到活结点表中。 6.1 分支限界法基础-与回溯法区别 分支限界法与回溯法适用于解时间复杂性上困难的往往难以用其它方法解决的问题, 是两种应用十分广泛的有哪些信誉好的足球投注网站技术。但两者又有所区别。 （1）求解目标： 回溯法是找出解空间树中满足约束条件的所有解； 分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 （2）有哪些信誉好的足球投注网站方式的不同： 回溯法以深度优先的方式有哪些信誉好的足球投注网站解空间树; 分支限界法则以广度优先或以最小耗费（最大效益）优先的方式有哪些信誉好的足球投注网站解空间树。 6.1 分支限界法基础-与回溯法区别 6.1 分支限界法基础-示例 6.1.2 示例：迷宫问题 （1）问题描述 迷宫是一个矩形区域，如图6.1左图所示，它有一个入口和一个出口，其内部包含不能穿越的墙或障碍。本问题就是要寻找一条从入口到出口的路径。 对于这样的矩形迷宫，可用图6.1右图所示的方阵[n,m]表示，n和m分别代表迷宫的行数和列数。这样迷宫中的每个位置都可用其行号和列号来指定。(1,1)表示入口位置，(n,m)表示出口位置；为表示障碍，在方阵中0表示可以通过，1表示不能通过。 6.1 分支限界法基础-示例 6.1 分支限界法基础-示例 6.1 分支限界法基础-示例 求解过程 ① (1,1)为当前扩展结点，其儿子结点(2,1)和(1,2)均为可行结点，将其加入到活结点队列，并舍弃(1,1) ② 按先进先出原则，下一扩展结点为(2,1)，其儿子结点(2,2)为不可行结点故舍去，另一可行儿子结点(3,1)加入活结点队列，舍弃(2,1)。 ③ (1,2)为当前扩展结点，其儿子结点(2,2)为不可行结点故舍去，另一可行儿子结点(1,3)加入活结点队列。舍弃(1,2)。 ④ 扩展(3,1)，其儿子结点(3,2)加入活结点队列，舍弃(3,1)。 ⑤ 扩展(1,3)，其儿子结点(2,3)为不可行结点故舍去。舍弃(1,3)。 6.1 分支限界法基础-示例 6.1 分支限界法基础-分类 从活结点表中选择下一个扩展结点的不同方式导致不同的分支限界法。 最常见的有两种方式： （1）队列式（FIFO）分支限界法 按照队列先进先出原则选取下一个结点为扩展结点。 （2）优先队列式分支限界法。 按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。 6.1 分支限界法基础-分类 队列式分支限界法 将活动结点表组织成一个队列，并按队列的的先出先进原则选 取下一个结点作为扩展结点。步骤如下： ①将根节点加入活动结点队列； ②从活结点队列中取出队头结点，作为当前扩展结点； ③对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把满足条件约束函数的儿子结点加入活动结点队列中； ④重复步骤?和?，直到找到一个解或活动队列为空为止。 6.1 分支限界法基础-分类 优先队列式分支限界法 将活结点表组织成一个优先队列，并选取优先级最高的活结点作为当前扩展结点。步骤如下： ①计算起始结点的优先级并加入优先队列(与特定问题相关的信息的函数值决定优先级)； ②从优先队列中取出优先级最高(最有利)的结点作为当前扩展结点，使有哪些信誉好的足球投注网站朝着解空间数上可能有