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

1、中南大学算法分析与设计复习1 Branch-and-bound中南大学算法分析与设计复习2Branch and Boundo An enhancement of backtrackingn Similarityo A state space tree is used to solve a problemn Differenceo used only for optimization problems.o The backtracking requires the using of DFS traversal and is used for nonoptimization problems.o

2、Branch and bound: does not limit us to any particular way of traversing the tree (Best-first)中南大学算法分析与设计复习3Branch and bound (cont.)o Branching strategy:how to partition solution spaceo Node selection strategy:n sequence of exploring nodes:o depth first (tries to obtain a solution fast)o breadth/best

3、 bound first (tries to find the best solution)n which nodes to exploreoSelecting the node with the best estimated cost among all nodes.oCombine depth-first search and breadth-first search.中南大学算法分析与设计复习4Branch and Boundo Compared to backtracking ,branch-and-bound requires two additional items.n A way

4、 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.n The value of the best solution seen so far.中南大学算法分析与设计复习5The main ideap Set up a b

5、ounding 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 promisingp Promising (if the bound is better than the value of the best solution so far: expand beyond the node.p Nonpromising (if the bound is no bette

6、r 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).中南大学算法分析与设计复习6StartIb=10a1Ib=17a 2Ib=10a 3Ib=20a 4Ib=18b1Ib=13b 3Ib=14b 4Ib=17c 3Ib=13c 4Ib=20d 4Cost/p>

7、910o边界（下界）的选择：边界（下界）的选择：n初始节点边界：包括最优解在内，任何解的成本都不会小于矩阵每行中的最小元素的和。n节点其它边界：实际产生的成本+还要付出的最小成本（估计）中南大学算法分析与设计复习7o Given a set of points and their pairwise distances, the task is to find a shortest tour that visits each point exactly once. o It is NP-complete.The traveling salesperson optimization problem

8、中南大学算法分析与设计复习8Traveling Salesman ProblemBounding Functiono 边界（下界）函数的选择：边界（下界）函数的选择：n 初如节点边界：对于每一个城市，求出该城市到距离其最近的另外两个城市的距离之和，并把所有城市的该距离和除以2取整。n 其它节点边界：实际产生的成本+还要付出的最小成本（估计）中南大学算法分析与设计复习9Traveling salesmanaIb=14a,bIb=14a,ca,dIb=16a,eIb=19012345679a,b,cIb=16a,b,eIb=19a,b,dIb=168a,b,c,d,e,al=241011b is

9、not before ca,b,c,e,d,al=19a,b,d,c,e,aI=24a,b,d,e,c,aI=16中南大学算法分析与设计复习10Notesp Finding a good bounding is not a simple task.p On the one hand. We want this function to be easy to compute.p On the other hand, it cannt be too simplistic.otherwise, it would fail in its principal task to prune as many b

10、ranches of a state-space tree as soon as possible.中南大学算法分析与设计复习11The 0/1 knapsack problem o Positive integer P1, P2, , Pn (profit) W1, W2, , Wn (weight) M (capacity)中南大学算法分析与设计复习12Knapsack problemn 先按单位价值对待处理的物品进行排序 v1/w1v2/w2 vn/wnn bound function（边界函数（上界）: ub=v+(W-w)(vi+1/wi+1)即即：已经选择物品的总价值v+背包的剩余承重W-w与剩下物品的最佳单位回报vi+1/wi+1的乘积。中南大学算法分析与设计复习13ExampleItem weight value value/weight1 4 40 102 7 42 63 5 25 5 4 3 12 4W=10中南大学算法分