第六章 分支与界限.pdf

2011/11/21 学习要点 第六章 分支与界限  理解分支限界法的剪枝搜索策略。  通过应用范例学习分支限界法的设 计策略。 6.1 分支与界限法的基本思想 • 在整个搜索过程中，每遇到一个活结点，就对它的各个孩 子结点进行目标函数可能取得值得估算，以此来更新表结 点：丢弃不再需要的结点，加入新的结点。再从表中选取 “界”取极值的结点，并重复上述过程。 • 随着过程的不断深入，结点表中所估算的目标函数的极值， 越来越接近问题的解。当搜索到一个叶子结点时，如果对 n=3时，0/1背包问题的状态空间树 该结点所估算的目标函数的值就是结点表中最大或最小值， 那么沿叶子结点到根结点的路径确定的解就是问题的解。 分支与界限法的基本思想：在分支结点上，预先分别估算沿着它的各个 孩子结点向下搜索的路径中，目标函数可能取得的“界”，然后，把它 的这些孩子结点和它们可能取得的“界”保存在一张结点表中，再从表 中选取“界”最大或最小的结点向下搜索。 6.2 货郎担问题 • 搜索方法： • 费用矩阵 当从根结点开始向下搜索时，预先通过某 种方式的处理，从众多孩子结点中挑选一 0 1 2 3 4 0 ∞ 25 41 32 28 个孩子结点作为搜索树的一个分支结点， 1 5 ∞ 18 31 26 而把去掉这个结点之后的其他孩子结点的 2 20 16 ∞ 7 1 3 10 51 25 ∞ 6 集合，作为搜索树的另外一个分支结点。 4 23 9 7 11 ∞ 1 2011/11/21 6.2.1 费用矩阵的行归约（列归约） 6.2.2 矩阵的归约常数 • 费用矩阵c 的第i行（或第j 列）中的每个元素减去一个正常 数lh （或ch ），得到一个新的费用矩阵，使得新矩阵中第i • 对费用矩阵的每一行和每一列都进行归约 i j 行（或第j 列）中的最小值为0 ，称为费用矩阵的行归约 和列