算法设计与分析chap11 branch-and-bound.pptVIP

Jin Zheng, Central South University Branch-and-bound（分支限界） Branch and Bound（分支限界） An enhancement of backtracking（和回溯法一样，也用到状态空间对） Similarity A state space tree is used to solve a problem Difference used only for optimization problems.（是求解最优化问题） The backtracking requires the using of DFS traversal and is used for nonoptimization problems. Branch and bound: does not limit us to any particular way of traversing the tree (Best-first)（最好的优先） Branch and bound (cont.) Node selection strategy(节点选择策略): sequence of exploring nodes: depth first (tries to obtain a solution fast)（深度优先:尽快获得可行解） breadth/best bound first (tries to find the best solution)（宽度/最好的界优先:尽快获得最优解) which nodes to explore 8-幻方问题 Branch and Bound Compared to backtracking ,branch-and-bound requires two additional items. A way to provide, for every node of a state-space-tree ,a bound on the best value of the objective function on any solution that can be obtained by adding further components to the partial solution represented by the node.(对产生的每个节点给出一个界估计值，用于确定优先扩展的节点） The value of the best solution seen so far.( 答案节点的值即为解的值,一旦得到一个答案节点的值,就可以剪掉很多扩展节点) The main idea Set up a bounding function, which is used to compute a bound (for the value of the objective function) at a node on a state-space tree and determine if it is promising Promising (if the bound is better than the value of the best solution so far: expand beyond the node. Nonpromising (if the bound is no better than the value of the best solution so far--:not smaller for a minimization problem and not larger for a maxmization problem ): not expand beyond the node (pruning the state-space tree). Assignment problem 边界（下界）的选择： 初始节点边界：包括最优解在内，任何解的成本都不会小于矩阵中每行中的最小元素之和。 节点其它边界：实际产生的成本+还要付出的最小成本（估计） The traveling salesperson optimization problem(TSP问题) Traveling Salesman Problem—Bounding Function 边界（下界）函数的选择： 初如节点边界：对于每一个城市，求出该城市到距离其最近的另外两个城市的距离之和，并把所有城市的该距离求和、并除以2取整。 其它节点边界：实际已选边的距离之和+其它节点边的最小距离（估计） Traveling salesman Notes: Finding a good