1、Last Section分支定界主要的分支定界法相關(guān)概念:Feasible （solution）, Infeasible （solution）, Partial Solution, Optimal Solution, Branch, Bound (tight), Traverse, Backtracking, Prune, DFS, BFS, Frontier Search, Initial solution, Relax分支定界法的主要思想分支定界法解整數(shù)規(guī)劃問題背包問題TSP有向圖的TSP分配（指派）問題匈牙利法一些說明Branch and BoundMinimum Cost Networ

2、k Flow Problem問題描述該類設(shè)計(jì)問題的目標(biāo)是，在一組節(jié)點(diǎn)之間設(shè)計(jì)一最小耗費(fèi)的網(wǎng)絡(luò)以滿足所有的流量需求。描述該問題的信息：每個(gè)源節(jié)點(diǎn)和目的節(jié)點(diǎn)對(O-D)之間的流量需求在每條邊(i,j)上負(fù)載流量的價(jià)值函數(shù)Cij=f(tij)The Problemlet G be the set of all undirected graphs on n nodes with G a member of this set. G is represented by its upper triangular node-node adjacency matrix B with elements bij.

3、The problem is to find a G*G which minimizes the cost of transporting required origin-destination flows subject to specified arc and node capacity, node degree and chain hop limit constraints. 問題描述設(shè)G表示在n個(gè)點(diǎn)上的所有無向圖的集合，G是該集合中的一個(gè)元素。 G以節(jié)點(diǎn)的鄰接矩陣B的上三角陣來表示，其元素為bij.該問題就是要找到一個(gè)G *G，使得在滿足給定的邊容量限制的前提下，實(shí)現(xiàn)傳輸所有源節(jié)點(diǎn)到目

4、的節(jié)點(diǎn)的流量需求所用的花費(fèi)最小。 Next ?The ProblemFormulation-1Interpretation of the formulationToo complicated? Then what?Transform and conquer Problem transformationConstant arc costsTree solution給定一個(gè)連通的無向圖G=(V,A,d,c)，點(diǎn)集V=1,2,n，邊集A.V中的每個(gè)節(jié)點(diǎn)對i和j間，有一定的流量要求dij.cij表示建立A中的邊(i,j)的花費(fèi)。每條邊(i,j)上的負(fù)載不能超過一個(gè)給定值kij.通過以上這些定義，該問題

5、就是要找到一個(gè)可以擴(kuò)展節(jié)點(diǎn)集V的最小生成樹，同時(shí)滿足所有的流量要求，而且每條邊(i,j)都符合負(fù)載限制kij.令fij表示經(jīng)過邊(i,j) 的總流量。定義xij=1,當(dāng)邊(i,j)被選中在解中；xij=0,當(dāng)邊(i,j)沒有被選中。Problem IIFormulation-2Interpretation of the formulationBranch and BoundWhat is the first task?Branch and BoundWhat is the first task?Constructing a search treeHow to construct the sea

6、rch tree?Branch and BoundWhat is the first task?Constructing a search treeHow to construct the search tree?-Innumerate ，Organize，BoundBranch and BoundThe search treea tree spanning n nodes must have exactly n-1 arcs consider the solution as a collection of n-1 arcs (for n-node problem) chosen from a

7、ll candidate arcsintroduce an arc-oriented branch and bound method, branching by using an arc or not. A Binary Search Tree Define an m-stage binary search tree for problem with n nodes, where, for complete graph problem, m equals the number of pairs of nodes. Give each of the arcs an arc number, fro

8、m 1 to m, as identification. The branching within each stage corresponds to the decision of either adding a certain arc to the solution arc set or not. Define traveling along left branch represents for choosing an arc and traveling along right branch represents for not choosing an arc. 二叉搜索樹對于n個(gè)節(jié)點(diǎn)的問

9、題定義一個(gè)m層的二叉搜索樹，對于完全圖問題，m等于節(jié)點(diǎn)對的個(gè)數(shù)。為每條邊編號(hào)，從1到m。每層的分支對應(yīng)于是否把某條邊添加到解集中的決策。定義沿左分支前進(jìn)表示選擇該邊，沿右分支前進(jìn)表示不選該邊。The search treehow big is it ?The search treeKEEP The Tree in MindThe search treeKEEP The Tree in MindWhats next?The search treeKEEP The Tree in MindWhats next?Regulations for traversing the search tree.T

10、raversing the search treeIt is obvious that an optimal solution can be found after having visited all the vertices of this binary tree.1.Always start from the root of the tree (Vertex 1).2.Always go along the left branch first when descending.3.Keep descending and backtrack when any of the following

11、 situations occurs:a.Current selected arcs make the solution infeasible.b.A feasible solution has been found.4.After backtracking to a vertex along its left branch, go forward along its right branch.5.After backtracking to a vertex along its right branch, go backward to its parent vertex.遍歷搜索樹明顯地，當(dāng)該

12、二叉樹中的所有頂點(diǎn)都被訪問過時(shí)，可以找到一個(gè)最優(yōu)解?？偸菑臉涞母?Vertex 1)開始。當(dāng)下行時(shí)，總是先沿左分支進(jìn)行。當(dāng)有如下情況之一發(fā)生時(shí)，進(jìn)行回溯：a. 當(dāng)前挑選的邊使得解不可行。b. 已經(jīng)找到一個(gè)解。當(dāng)從左分支回溯到某頂點(diǎn)時(shí)，接著沿其右分支向下進(jìn)行。當(dāng)從右分支回溯到某頂點(diǎn)時(shí)，接著回溯到其父頂點(diǎn)。Traversing the search treeStage1Ver 2Stage1Stage2Vertex 1Ver 4Ver 3Ver 6Ver 5Stage2Ver 8Ver 710911121314Ver 15Stage mStage mTraversing the search tr

13、eeWhats next?Traversing the search treeWhats next?Pruning the search treeboundUpper BoundTotal cost of an existing solution.目前已經(jīng)得到的一個(gè)解的總花費(fèi)Updated whenever a better solution is foundLower BoundEach vertex in the search tree represents a sub-problem generated from the original one. The difference betw

14、een a sub-problem and the whole problem is that, in a sub-problem, some arcs are defined not to be used while some other arcs must be included in the solution. If the capacity constraint is relaxed, the sub-problem is quite similar to the traditional minimum spanning tree (MST) problem. Here, the ca

15、pacity constraint relaxed sub-problem is named SMST problem.下界搜索樹的每個(gè)頂點(diǎn)代表由原始問題得到的一個(gè)子問題。子問題和整個(gè)問題的區(qū)別在于，在子問題中，有些邊已被定義為不選，而另外一些邊則必須選用。如果取消流量限制，那么子問題很類似于傳統(tǒng)的最小生成樹(MST)問題。這里，我們稱取消流量限制的子問題為SMST問題。A Modified Kruskals Algorithm for the SMST problem SMST問題的Modified Kruskals算法修改的Kruskals算法從空的解集開始：首先，把那些被定義為不選的邊從

16、整個(gè)候選邊集合中移除；然后，把那些必選的邊包含到解中（這些邊不會(huì)在解樹中上產(chǎn)生回路。這是由于，在搜索樹的每個(gè)頂點(diǎn)，當(dāng)添加相應(yīng)邊時(shí)，都會(huì)做回路檢查。）；接下來，選擇候選邊集合中權(quán)值最小的邊，并檢查如果把該邊添加到解集中是否滿足樹條件。如果它在解空間樹上形成回路，那么放棄該邊；否則，把這條邊添加到解集中。接著考察第二個(gè)權(quán)值最小的邊；重復(fù)上述步驟直到一個(gè)該節(jié)點(diǎn)集上的一個(gè)生成樹已經(jīng)構(gòu)成。Modified Kruskals AlgorithmTheorem 1 The solution found by the Modified Kruskals Algorithm is the optimal sol

17、ution for the SMST problem.Proof To prove the optimality of this solution, the method of “reduction to absurdity” is used. proofPruning The Search treeSince in the search tree, a certain vertex represents that some arcs have been chosen and some other arcs have been eliminated, we can use SMST as a

18、bound. At each vertex in the search tree, in addition to the feasibility checks, the current SMST is constructed and its total cost is calculated. If it is expensive than the cost of a solution already found, the sub-tree rooted at the current vertex in the search tree is pruned.對搜索樹剪枝因搜索樹中的一個(gè)頂點(diǎn)代表一些

19、邊被選上，而另一些邊被移除，我們可以使用SMST的值作為一個(gè)界。在搜索樹的每個(gè)節(jié)點(diǎn)，除了可行性檢查，當(dāng)前SMST也被構(gòu)造出來，并且計(jì)算出它的總花費(fèi)。如果該花費(fèi)大于目前已求出的解的花費(fèi)（上屆），以當(dāng)前節(jié)點(diǎn)為根的子樹被剪枝。Pruning The Search treeNext?Make the pruning faster.Pruning The Search tree-feasibility In addition to the SMST bound, an efficient feasibility check procedure is greatly essential for pruni

20、ng the search tree. When analyzing the above search routine, we found some ings. When an arc, which would have a smaller arc number and would possess a higher stage in the search tree, has a very low flow capacity, it will often cause the weakness that our algorithm will spend a lot of time searchin

21、g on the sub-tree under this stage while no feasible solution exists. 對搜索樹剪枝-可行性如果編號(hào)較小、在搜索中位于較高階段的邊的容量較小時(shí)，目前的算法會(huì)暴露出一個(gè)弱點(diǎn)：在該階段花費(fèi)大量時(shí)間搜索其子樹，而實(shí)際上并不存在可行解。Weakness Arc 3 is not overflow at Ver. 4Stage1Ver 2Stage1Stage2Vertex 1Ver 4Ver 3Ver 6Ver 5Stage2Ver 8Ver 710911121314Ver 15Stage mStage mWhat would you

22、 do?Predicting Violation of Capacity ConstraintAny idea?Predicting Violation of Capacity ConstraintAny idea?Problem transformationPredicting Violation of Capacity ConstraintProblem transformationUnit traffic demandProblem IIIFormulation-3Interpretation of the formulationPredicting Violation of Capac

23、ity ConstraintPredicting Violation of Capacity ConstraintPredicting Violation of Capacity ConstraintPredicting Violation of Capacity ConstraintPredicting Violation of Capacity ConstraintBefore the searching is engaged, the Link Degree value for every arc is calculated and stored. At every searching

24、stage, even the current partial solution is feasible, the procedure checks if any arcs current and are both greater than its Link Degree. If so, the procedure performs backtracking and the subtree rooted at the current vertex in the search tree is pruned, since it will sooner or later cause an overf

25、low if more arcs are added to the solution.預(yù)測流量約束是否違背在搜索之前，每條邊的Link Degree被計(jì)算并存儲(chǔ)起來。在搜索的每個(gè)階段，即使當(dāng)前部分解是可行的，算法要檢查是否有某一條邊的當(dāng)前NL和NR都比它的Link Degree大。如果是這樣，回溯并且以當(dāng)前頂點(diǎn)為根的子樹被剪枝，因?yàn)殡S著越來越多的邊加入到解集中，該邊遲早會(huì)溢出。Predicting Violation of Capacity ConstraintComparing the Link Degree and the current can foretell whether an a

26、rc will overflow even if it hasnt yet been connected to some other separated arcs or sub-trees and hasnt yet overflowed. Implementing this technique will prune the search tree far more quickly.AdvantageCapacity=302*13=263*12=36Feasibility Predicting Method for Problem with Non-Unit Traffic DemandPro

27、blem IIWhats the idea?Predicting Violation of Capacity ConstraintPredicting Violation of Capacity ConstraintPredicting Violation of Capacity ConstraintFuture flow boundCan you make the bound tighter?Future flow boundCan you make the bound tighter?The bound can be made even tighter if the possible mi

28、nimum flow on an arc is calculated based on every separated sub-tree but not on single node. Tighter future flow bound for non-unit traffic demand problemThe induction of tighter boundNon-unit Demand ProblemNode 1Non-unit Demand ProblemSubTree 1Node 1Node 3Node 2Further improvement Can you make the

29、searching more fast?Further improvement Can you make the searching more fast?We sort the arcs in the order of ascendant arc cost and give each of them an arc number, from 1 to m, as identification. Whats the advantages?Ascendant arc orderConstruction of SMST More advantages?Ascendant arc orderConstr

30、uction of SMST boundDominant frontier searchMore advantages?Ascendant arc orderConstruction of SMST boundDominant frontier searchTotal cost boundFurther improvement Can you make the searching more fast?Further improvement Can you make the searching more fast?An initial solution (upper bound)A modifi

31、ed Prims algorithmThe algorithmData structuresI consider the following to be the best data structure for an arc-orientated branch and bound searching. define “SolutionBuffer”, which stores the arcs (identified by arc number) that have been chosen to form a potential feasible solution, as an array 1.

32、N-1 of integer. An integer “FlagSolve” is used to store the total number of arcs already been added to “SolutionBuffer” at the current searching step.The algorithmCodes Faster ?Faster ?Faster forward traversing guided by SMSTFaster ?Faster ?Omitted SMST ConstructionFaster ?Faster ?Omitted cycle dete

33、ctionFaster ?Faster ?Sequence of function callsProblem INon-linear cost functionWhats your idea?Problem INon-linear cost functionWhats your idea?Piecewise constant Problem INon-linear cost functionWhats your idea?Piecewise constant What would you do?The efficiency of the algorithmProblem File NameRu

34、nning StepsRunning Time (Seconds)P100g-1.txt169474163P100g-2.txt279842407P100g-3.txt156281140P100g-4.txt188611160P100g-5.txt3312304720P100g-6.txt98158182P100g-7.txt217784400P100g-8.txt140683163P100g-9.txt628903700P100g-10.txt58048Lower Bound ArgumentsLower BoundsDefinition: A lower bound of a proble

35、m is the least amount of computation that any algorithm must use to solve this problem. Lower bounds are generally theoretically derived.The lower bound for a problem is not unique, but the higher the better.For example, (1), (n) and (nlogn) are all lower bounds for sorting but among them (nlogn) is

36、 the best. Lower BoundsAt present, if the best lower bound of a problem is (n) and the time complexity of the best algorithm is O(n2). This means thatwe may try to find a better lower bound, e.g. (nlogn);we may try to find a better algorithm, e.g. O(nlogn);both of the lower bound and the algorithm m

37、ay be improved. If the present lower bound is (nlogn) and there is an algorithm with time complexity O(nlogn), then the algorithm is optimal.Lower Bound ArgumentsTrivial Lower BoundsInformation-Theoretic ArgumentsAdversary ArgumentsProblem ReductionLower Bound on SortingComparison sort: A family of

38、algorithms that use comparisons to determine the sorted order of a list.Examples: Mergesort, QuicksortDecision tree = A tree that describes the comparisons required to sort a list of data.A B C A C BB A C B C AC A B C B AA B CA C BC A BB A CB C AC B AA B CA C BB A CB C AC A BC B AA B CA C BB A CB C

39、AA BB AC AA CC AA CC BB CC BB CDecision TreesGiven n items there are n! different ways to arrange them (permutation (排列).Only one of the permutations is in sorted order.The aim of sorting is to discover the sorted permutation.The worst case running time corresponds to the longest path from the root

40、to a leaf.The power of comparison Given n, we have M = n! permutations. Each permutation must appear as one of the leaves in the decision tree.Every time we perform a comparison, one of two branches eliminates (排除) at most half of the permutations.The power of comparisonThus, if sorting is done alon

41、g the longest path, we will use at least k = log2M comparisons.Another proof is that since any binary tree of height k has at most 2k leaves, we have 2k n!.The best general sorting algorithm requires log2(n!) comparisons in the worst case.How much is log2(n!)? Method 1log2(n!) = log2(n (n1) (n2) (2)

42、 (1)= log2n+log2(n1)+log2(n2)+ +log2(2)+log2(1) log2n+log2(n1)+log2(n2)+ +log2(n/2) n/2 log2(n/2) = n/2 (log2n 1) = (nlogn)Comparison-based SortingTheorem 1. Any comparison-based sorting algorithm must use (nlogn) comparisons for sorting an array of n elements in the worst case.This means that it is

43、 impossible to perform sorting using O(n) or O(log n) or O(n log(log n) comparisons.Determining The Maximum Theorem 2. Every comparison-based algorithm for determining the maximum of a set of n elements must use at least n/2 comparisons. Proof. Every element must participate in at least one comparis

44、on; if not, the pared element can be chosen to be the maximum. Each comparison compares 2 elements. Hence, at least n/2 comparisons must be made. Determining The MaximumTheorem 3. Every comparison-based algorithm for determining the maximum of a set of n elements must use at least n1 comparisons. Pr

45、oof. To say that a given element, x, is the maximum, implies that every other element has lost at least one comparison with another element (not necessarily x). Each comparison produces at most one loser. Hence at least n1 comparisons must be used. Lower Bound for Finding Max and MinWe can compute b

46、oth the maximum and minimum of a list of n numbers, using (3/2)n2 comparisons. We will prove that this solution is optimal. Here is an algorithm: Compare x1 with x2, x3 with x4, etc. We get n/2 maxima and n/2 minima. Find the maximum on the n/2 maxima with n/21 comparisons, and the same for the mini

47、ma. The total cost: n/2+n/21+n/21 = 3n/22 (when n even). Lower Bound for Finding Max and MinNote that x is the minimum and y is the maximum only if every element other than x has won at least one comparison and every element other than y has lost at least one comparison. Lower Bound for Finding Max

48、and MinCall a win “W”, a loss “L”. For each element, we label it according to the following 4 cases:N: never compared with anybody; W: won all comparisons; L: lost all comparisons; WL: won at least one and lost at least one. The algorithm must assign n1 Ws and n1 Ls. i.e., it MUST need 2n2 “units of

49、 information”. More precisely, n-2 WLs, 1 W and 1 L. Lower Bound for Finding Max and MinTo prove that the worst case can happen, we will use what is called an adversary (反對者) argument (論證、論據(jù)). An adversary is an opponent (對手) that the comparison algorithm plays against. Its ultimate (最終) goal is to

50、maximize the number of comparisons that the algorithm makes (minimize the amount of information obtained) by constructing an input to the problem. Lower Bound for Finding Max and MinThe adversary tentatively (暫時(shí)地) assigns values to the elements, which may change over time. However, they can only cha

51、nge in a fashion CONSISTENT (一致的) with previous answers. That is, an element labeled L may only DECREASE in value (since it has lost all previous comparisons, if it is decreased, it will still lose all of them), and an element labeled W may only INCREASE in value. An element labeled WL cannot change. Lower Bound for Finding Max and MinTheorem 4. Every comparison-base method for determining both the maximum and minimum of a set of n numbers must use at least (3n/2)2 comparisons, in the worst case. Proof. Assume n is eve