中南大学算法分析与设计复习课件

1、Jin Zheng, Central South University,1,Branch-and-bound,Jin Zheng, Central South University,2,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 a

2、nd is used for nonoptimization problems. Branch and bound: does not limit us to any particular way of traversing the tree (Best-first),Jin Zheng, Central South University,3,Branch and bound (cont.),Branching strategy: how to partition solution space Node selection strategy: sequence of exploring nod

3、es: depth first (tries to obtain a solution fast) breadth/best bound first (tries to find the best solution) which nodes to explore,Selecting the node with the best estimated cost among all nodes.,Combine depth-first search and breadth-first search.,Jin Zheng, Central South University,4,Branch and B

4、ound,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 omponents to the partial solution represented by the node.

5、 The value of the best solution seen so far.,Jin Zheng, Central South University,5,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 t

6、han 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).,Jin Zhe

7、ng, Central South University,6,边界（下界）的选择： 初始节点边界：包括最优解在内，任何解的成本都不会小于矩阵每行中的最小元素的和。 节点其它边界：实际产生的成本+还要付出的最小成本（估计）,Jin Zheng, Central South University,7,Given a set of points and their pairwise distances, the task is to find a shortest tour that visits each point exactly once. It is NP-complete.,The tra

8、veling salesperson optimization problem,Jin Zheng, Central South University,8,Traveling Salesman ProblemBounding Function,边界（下界）函数的选择： 初如节点边界：对于每一个城市，求出该城市到距离其最近的另外两个城市的距离之和，并把所有城市的该距离和除以2取整。 其它节点边界：实际产生的成本+还要付出的最小成本（估计）,Jin Zheng, Central South University,9,Traveling salesman,0,1,2,3,4,5,6,7,9,8,10

9、,11,b is not before c,Jin Zheng, Central South University,10,Notes,Finding a good bounding is not a simple task. On the one hand. We want this function to be easy to compute. On the other hand, it cannt be too simplistic.otherwise, it would fail in its principal task to prune as many branches of a s

10、tate-space tree as soon as possible.,Jin Zheng, Central South University,11,The 0/1 knapsack problem,Positive integer P1, P2, , Pn (profit) W1, W2, , Wn (weight) M (capacity),Jin Zheng, Central South University,12,Knapsack problem,先按单位价值对待处理的物品进行排序 v1/w1v2/w2 vn/wn bound function（边界函数（上界）: ub=v+(W-w)(vi+1/wi+1),即：已经选择物品的总价值v+背包的剩余承重W-w与剩下物品的最佳单位回报vi+1/wi+1的乘积。,Jin Zheng, Central South University,13,Example,Item weight valu