《计算模型与算法技术：12-Coping with the Limitations of Algorithm Power》由会员分享，可在线阅读，更多相关《计算模型与算法技术：12-Coping with the Limitations of Algorithm Power（56页珍藏版）》请在金锄头文库上搜索。
1、L o g oChapter 12 Coping with the Limitations of Algorithm PowerCopyright 2007 Pearson Addison-Wesley. All rights reserved.L o g o2 2Keep on the lookout for novel ideas that others have used successfully . Your idea has to be original only in its adaptation to the problem youre working on. Thomas Ed
2、ison (18471931)L o g o3 3 3 312.1 BacktrackingL o g o4 4BacktrackingThe principal idea is to construct solutions one component at a time and evaluate such partially constructed candidates as follows. If a partially constructed solution can be developed further without violating the problems constrai
3、nts, it is done by taking the first remaining legitimate option for the next component. If there is no legitimate option for the next component, no alternatives for any remaining component need to be considered. In this case, the algorithm backtracks to replace the last component of the partially co
4、nstructed solution with its next option.L o g o5 5state-space treeIts root represents an initial state before the search for a solution begins. The nodes of the first level in the tree represent the choices made for the first component of a solution.The nodes of the second level represent the choice
5、s for the second component, and so on. A node in a state-space tree is said to be promising if it corresponds to a partially constructed solution that may still lead to a complete solution; otherwise, it is called nonpromising. Leaves represent either nonpromising dead ends or complete solutions fou
6、nd by the algorithm.L o g on-Queens ProblemL o g on-Queens ProblemL o g oHamiltonian Circuit Problemabdecf(a)Graphabcdefedffecda012345678910111213(b) State-space tree for finding a Hamiltonian circuit. The numbers above the nodes of the tree indicate the order in which the nodes are generated.Dead e
7、nd Dead end Dead end solutionL o g oSubset-Sum Problem0the subset-sum problem: find a subset of a give n set A = a1, . . . , an of n positive integers whose sum is equal to a given positive integer d.It is convenient to sort the sets elements in increasing order. So, we willassume that a1 a2 . . . 1
8、lb=9+3+1+4=17a-2lb=2+3+1+4=10a-3lb=7+4+5+4=20a-4lb=8+3+1+6=1801234Levels 0 and 1 of the state-space tree for the instance of the assignmentproblem being solved with the best-first branch-and-bound algorithm. Thenumber above a node shows the order in which the node was generated.A nodes fields indica
9、te the job number assigned to person a and thelower bound value, lb, for this node.The most promising of them is node 2 !L o g oAssignment Problemstartlb=100a-1lb=171xa-2lb=102a-3lb=203xa-4lb=184xb-1lb=135b-3lb=146b-4lb=177L o g oAssignment Problemstartlb=100a-1lb=171xa-2lb=102a-3lb=203xa-4lb=184xb-
10、1lb=135b-3lb=146b-4lb=177xxc-3d-4cost=138solutionc-4d-3cost=259inferior solutionL o g oKnapsack ProblemGiven n items of known weights wi and values vi , i = 1, 2, . . . , n, and a knapsack of capacity W, find the most valuable subset of the items that fit in the knapsack.itemweightvaluevalueweight14
11、$401027$42635$25543$124The knapsacks capacity W is 10.L o g oKnapsack Problemub=100w=0,v=00L o g oKnapsack Problemub=100w=0,v=00ub=761ub=60w=0,v=02w=4,v=40with 1w/o 1L o g oKnapsack Problemub=100w=0,v=00ub=761ub=60w=0,v=02w=4,v=40with 1Xw/o 1L o g oKnapsack Problemub=100w=0,v=00ub=761ub=60w=0,v=02w=
12、113ub=70.w=4,v=404w=4,v=40with 2Xw/o 2with 1w/o 1L o g oKnapsack Problemub=100w=0,v=00ub=761ub=60w=0,v=02w=113ub=70.w=4,v=404w=4,v=40w/o 2XXnot feasiblewith 1w/o 1with 2L o g oKnapsack Problemub=100w=0,v=00ub=761ub=60w=0,v=02w=113ub=70.w=4,v=404w=4,v=40ub=69.w=9,v=655ub=64.w=4,v=406w/o 2with 3w/o 3X
13、Xnot feasiblewith 1w/o 1with 2L o g oKnapsack Problemub=100w=0,v=00ub=761ub=60w=0,v=02w=113ub=70.w=4,v=404w=4,v=40ub=69.w=9,v=655ub=64.w=4,v=406w/o 2with 3w/o 3XXXnot feasiblewith 1w/o 1with 2L o g oKnapsack Problemub=100w=0,v=00ub=761ub=60w=0,v=02w=113ub=70.w=4,v=404w=4,v=40ub=69.w=9,v=655ub=64.w=4
14、,v=406w=127ub=65.w=9,v=658w/o 2with 3with 4w/o 4XXXnot feasiblewith 1w/o 1w/o 3with 2L o g oKnapsack Problemub=100w=0,v=00ub=761ub=60w=0,v=02w=113ub=70.w=4,v=404w=4,v=40ub=69.w=9,v=655ub=64.w=4,v=406w=127ub=65.w=9,v=658w/o 2with 3w/o 3with 4w/o 4XXXnot feasibleoptimal solutionXnot feasiblewith 1w/o
15、1with 2L o g oKnapsack Problemub=100w=0,v=00ub=761ub=60w=0,v=02w=113ub=70.w=4,v=404w=4,v=40ub=69.w=9,v=655ub=64.w=4,v=406w=127ub=65.w=9,v=658w/o 2with 3w/o 3with 4w/o 4Xnot feasibleXXnot feasibleoptimal solutionXinferior tonode 8inferior to node 8with 1w/o 1with 2L o g oTraveling Salesman Problemwe
16、can compute a lower bound on the length l of any tour as follows. For each city i, 1 i n, find the sum si of the distances from city i to the two nearest cities; compute the sum s of these n numbers, divide the result by 2, and, if all the distances are integers, round up the result to the nearest i
17、nteger:Weighted graphFor example:L o g oTraveling Salesman Problemalb=140For example, for all the Hamiltonian circuits of the graph in Figure 12.9a that must include edge (a, d), we get the following lower bound by summing up the lengths of the two shortest edges incident with each of the vertices,
18、with the required inclusion of edges (a, d) and (d, a):L o g oTraveling Salesman Problemalb=140a,blb=141a,c2a,dlb=163a,elb=194L o g oTraveling Salesman Problemalb=140a,blb=141a,c2a,dlb=163a,elb=194 Xlb = lof node11 Xlb lof node 11Xb is notbefore cL o g oTraveling Salesman Problemalb=140a,blb=141a,c2
19、a,dlb=163a,elb=194a,b,clb=165a,b,dlb=166a,b,elb=19 7 Xb is notbefore c Xlb = lof node11 Xlb lof node 11L o g oTraveling Salesman Problemalb=140a,blb=141a,c2a,dlb=163a,elb=194a,b,clb=165a,b,dlb=166a,b,elb=19 7 Xlb lof node11Xb is notbefore c Xlb = lof node11 Xlb lof node 11L o g oTraveling Salesman P
20、roblemalb=140a,blb=141a,c2a,dlb=163a,elb=194a,b,clb=165a,b,dlb=166a,b,elb=19 7 a,b,c,d(e,a)l=24a,b,c,e(d,a)l=1989Xb is notbefore c Xlb = lof node11 Xlb lof node 11 Xlb lof node11L o g oTraveling Salesman Problemalb=140a,blb=141a,c2a,dlb=163a,elb=194a,b,clb=165a,b,dlb=166a,b,elb=19 7 a,b,c,d(e,a)l=24
21、a,b,c,e(d,a)l=19a,b,c,d(e,a)l=24a,b,d,e(c,a)l=16891011Xb is notbefore c Xlb = lof node11 Xlb lof node 11 Xlb lof node11L o g oTraveling Salesman Problemalb=140a,blb=141a,c2a,dlb=163a,elb=194a,b,clb=165a,b,dlb=166a,b,elb=19 7 a,b,c,d(e,a)l=24first toura,b,c,e(d,a)l=19better toura,b,c,d(e,a)l=24inferi
22、or toura,b,d,e(c,a)l=16optimal tour891011Xb is notbefore c Xlb = lof node11 Xlb lof node 11 Xlb lof node11L o g oApproximation Algorithms for NP-Hard ProblemsNP-Hard Problemsexhaustive-search algorithmdynamic programming techniquebranch-and-bound techniqueA heuristic is a common-sense rule drawn fro
23、m experience rather than from a mathematically proved assertion.heuristicL o g oApproximation Algorithms for NP-Hard ProblemsWe can quantify the accuracy of an approximate solution sa to a problem ofminimizing some function f by the size of the relative error of this approximation,where s is an exac
24、t solution to the problem. Alternatively,we can simply use the accuracy ratio as a measure of accuracy of sa.Note that for the sake of scale uniformity, the accuracy ratio of approximate solutions to maximization problems is usually computed asL o g oApproximation Algorithms for NP-Hard ProblemsDEFI
25、NITION A polynomial-time approximation algorithm is said to be a c approximation algorithm, where c 1, if the accuracy ratio of the approximation it produces does not exceed c for any instance of the problem in question:The best (i.e., the smallest) value of c for which the inequality holds for alli
26、nstances of the problem is called the performance ratio of the algorithm anddenoted RA.L o g oApproximation Algorithms for the Traveling Salesman ProblemTHEOREM 1 If P NP, there exists no c-approximation algorithm for the traveling salesman problem, i.e., there exists no polynomial-time approximatio
27、n algorithm for this problem so that for all instancesfor some constant c.Nearest-neighbor algorithmThe following well-known greedy algorithm is based on the nearest-neighborheuristic: always go next to the nearest unvisited city.Step 1 Choose an arbitrary city as the start.Step 2 Repeat the followi
28、ng operation until all the cities have been visited:go to the unvisited city nearest the one visited last (ties can be broken arbitrarily).Step 3 Return to the starting city.L o g o4242Approximation Algorithms for the Traveling Salesman ProblemEXAMPLE 1 For the instance represented by the graph in F
29、igure 12.10, with a asthe starting vertex, the nearest-neighbor algorithm yields the tour (Hamiltoniancircuit) sa: a b c d a of length 10.The optimal solution, as can be easily checked by exhaustive search, is the tours: a b d c a of length 8. Thus, the accuracy ratio of this approximation is(i.e.,
30、tour sa is 25% longer than the optimal tour s).FIGURE 12.10 Instance of the traveling salesman problem.L o g o4343Approximation Algorithms for the Traveling Salesman ProblemMultifragment-heuristic algorithmStep 1 Sort the edges in increasing order of their weights. (Ties can be broken arbitrarily.)
31、Initialize the set of tour edges to be constructed to the empty set.Step 2 Repeat this step n times, where n is the number of cities in the instance being solved: add the next edge on the sorted edge list to the set of tour edges, provided this addition does not create a vertex of degree 3 or a cycl
32、e of length less than n; otherwise, skip the edge.Step 3 Return the set of tour edges.L o g o4444Approximation Algorithms for the Traveling Salesman ProblemMinimum-Spanning-TreeBased Algorithms There are approximation algorithmsfor the traveling salesman problem that exploit a connection between Ham
33、iltoniancircuits and spanning trees of the same graph. Since removing an edge from a Hamiltonian circuit yields a spanning tree, we can expect that the structure of a minimum spanning tree provides a good basis for constructing a shortest tourapproximation. Here is an algorithm that implements this
34、idea in a rather straightforward fashion.Twice-around-the-tree algorithmStep 1 Construct a minimum spanning tree of the graph corresponding to a given instance of the traveling salesman problem.Step 2 Starting at an arbitrary vertex, perform a walk around the minimum spanning tree recording all the
35、vertices passed by. (This can be done by a DFS traversal.)Step 3 Scan the vertex list obtained in Step 2 and eliminate from it all repeated occurrences of the same vertex except the starting one at the end of the list. (This step is equivalent to making shortcuts in the walk.) The vertices remaining
36、 on the list will form a Hamiltonian circuit, which is the output of the algorithm.L o g o4545Approximation Algorithms for the Traveling Salesman ProblemEXAMPLE 2 Let us apply this algorithm to the graph in Figure a. The minimum spanning tree of this graph is made up of edges (a, b), (b, c), (b, d),
37、 and (d, e) (Figure b). A twice-around-the-tree walk that starts and ends at a isFIGURE 12.11Illustration of the twice-around-the-tree algorithm. (a) Graph. (b) Walk around the minimum spanning tree with the shortcuts.a, b, c, b, d, e, d, b, a.Eliminating the second b (a shortcut from c to d), the s
38、econd d, and the third b (ashortcut from e to a) yields the Hamiltonian circuita, b, c, d, e, aof length 39.L o g oApproximation Algorithms for the Traveling Salesman ProblemTHEOREM 2 The twice-around-the-tree algorithm is a 2-approximation algorithm for the traveling salesman problem with Euclidean
39、 distances.Christofides AlgorithmThere is an approximation algorithm with a better performance ratio for the Euclidean traveling salesman problemthe well-known Christofides algorithmLocal Search HeuristicsThe best-known of these are the 2-opt, 3-opt, and Lin-Kernighan algorithms.2-change: (a) Origin
40、al tour. (b) New tour.L o g o47472-changes from the nearest-neighbor tourEXAMPLE 4 If we start with the nearest-neighbor tour a b c d e a inthe graph of Figure 12.11, whose length lnn is equal to 39, the 2-opt algorithm willmove to the next tour as shown in Figure 12.14.aebdc1274610aebdc127968l = 42
41、 lnn = 39L o g o48482-changes from the nearest-neighbor touraebdc1274610aebdc127968l = 42 lnn = 39aebdc1274610aebdc1299610l = 46 lnn = 39aebdc1274610aebdc12114810l = 45 lnn = 39aebdc1274610aebdc47810l = 38 lnn = 39(new tour)9L o g o3-changes from the nearest-neighbor tourC5C4C6C3C1C2C5C4C6C3C1C2C5C4
42、C6C3C1C2(a)(b)(c)3-change: (a) Original tour. (b), (c) New toursL o g oApproximation Algorithms for the Knapsack Problem5050Greedy algorithm for the discrete knapsack problemStep 1 Compute the value-to-weight ratios ri= vi/wi, i = 1, . . . , n, for the items given.Step 2 Sort the items in nonincreas
43、ing order of the ratios computed in Step 1.(Ties can be broken arbitrarily.)Step 3 Repeat the following operation until no item is left in the sorted list:if the current item on the list fits into the knapsack, place it in theknapsack and proceed to the next item; otherwise, just proceed to the next
44、 item.Greedy algorithm for the continuous knapsack problemStep 1 Compute the value-to-weight ratios vi/wi, i = 1, . . . , n, for the items given.Step 2 Sort the items in nonincreasing order of the ratios computed in Step 1.(Ties can be broken arbitrarily.)Step 3 Repeat the following operation until
45、the knapsack is filled to its full capacity or no item is left in the sorted list: if the current item on the list fits into the knapsack in its entirety, take it and proceed to the next item; otherwise, take its largest fraction to fill the knapsack to its full capacity and stop.L o g oAlgorithms f
46、or Solving Nonlinear Equations5151Bisection MethodL o g oBisection Method5252EXAMPLE 1 Let us consider equation, It has one real root.Graph of functionTrace of the bisection method for solving equationThe figure contains a trace of the first eight iterations of the bisection method applied to this e
47、quation. Thus, we obtained x8 = 1.3203125 as an approximate value for the root x of the equation ,and we can guarantee that|1.3203125 x| 102.Moreover, if we take into account the signs of the function f (x) at a8, b8, and x8,we can assert that the root lies between 1.3203125 and 1.328125.L o g o5353
48、Method of False PositionEXAMPLE 2 The figure below contains the results of the first eight iterations of thismethod for solving equation (12.9).Although for this example the method of false position does not perform as well as the bisection method, for many instances it yields a faster converging se
49、quence.Trace of the method of false position for equation (12.9). The signsafter the numbers in the second and third columns indicate the sign off (x) = x3 x 1 at the corresponding endpoints of the intervals.L o g o5454Newtons MethodNewtons method, also called the Newton-Raphson method, it can be il
50、lustrated by Figure 12.22: the next element xn+1 of the methods approximation sequence is obtained as the x-intercept of the tangent line to the graph of function f (x) at xn.The analytical formula for the elements of the approximation sequence turns out to beL o g o5555Newtons MethodEXAMPLE 4 Let u
51、s apply Newtons method to equation (12.9), which we previouslysolved with the bisection method and the method of false position. Formula (12.11) for this case becomesYou cannot fail to notice how much faster Newtons approximation sequence converges to the root than the approximation sequences of both the bisection method and the method of false position.L o g o56C l i c k t o e d i t c o m p a n y s l o g a n .
