中南大學(xué)算法分析與設(shè)計(jì)復(fù)習(xí)課件

1、中南大學(xué)算法分析與設(shè)計(jì)復(fù)習(xí)1 Branch-and-bound中南大學(xué)算法分析與設(shè)計(jì)復(fù)習(xí)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)中南大學(xué)算法分析與設(shè)計(jì)復(fù)習(xí)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.中南大學(xué)算法分析與設(shè)計(jì)復(fù)習(xí)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.中南大學(xué)算法分析與設(shè)計(jì)復(fù)習(xí)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).中南大學(xué)算法分析與設(shè)計(jì)復(fù)習(xí)6StartIb=10a1Ib=17a 2Ib=10a 3Ib=20a 4Ib=18b1Ib=13b 3Ib=14b 4Ib=17c 3Ib=13c 4Ib=20d 4Cost/p>

7、910o邊界（下界）的選擇：邊界（下界）的選擇：n初始節(jié)點(diǎn)邊界：包括最優(yōu)解在內(nèi)，任何解的成本都不會(huì)小于矩陣每行中的最小元素的和。n節(jié)點(diǎn)其它邊界：實(shí)際產(chǎn)生的成本+還要付出的最小成本（估計(jì)）中南大學(xué)算法分析與設(shè)計(jì)復(fù)習(xí)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、中南大學(xué)算法分析與設(shè)計(jì)復(fù)習(xí)8Traveling Salesman ProblemBounding Functiono 邊界（下界）函數(shù)的選擇：邊界（下界）函數(shù)的選擇：n 初如節(jié)點(diǎn)邊界：對(duì)于每一個(gè)城市，求出該城市到距離其最近的另外兩個(gè)城市的距離之和，并把所有城市的該距離和除以2取整。n 其它節(jié)點(diǎn)邊界：實(shí)際產(chǎn)生的成本+還要付出的最小成本（估計(jì)）中南大學(xué)算法分析與設(shè)計(jì)復(fù)習(xí)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中南大學(xué)算法分析與設(shè)計(jì)復(fù)習(xí)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.中南大學(xué)算法分析與設(shè)計(jì)復(fù)習(xí)11The 0/1 knapsack problem o Positive integer P1, P2, , Pn (profit) W1, W2, , Wn (weight) M (capacity)中南大學(xué)算法分析與設(shè)計(jì)復(fù)習(xí)12Knapsack problemn 先按單位價(jià)值對(duì)待處理的物品進(jìn)行排序 v1/w1v2/w2 vn/wnn bound function（邊界函數(shù)（上界）: ub=v+(W-w)(vi+1/wi+1)即即：已經(jīng)選擇物品的總價(jià)值v+背包的剩余承重W-w與剩下物品的最佳單位回報(bào)vi+1/wi+1的乘積。中南大學(xué)算法分析與設(shè)計(jì)復(fù)習(xí)13ExampleItem weight value value/weight1 4 40 102 7 42 63 5 25 5 4 3 12 4W=10中南大學(xué)算法分