1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 73
Текст из файла (страница 73)
Indeed, let us consider the special casein which the distances d ij satisfy the triangle inequalitydij :::; d ik+ d kjfor each i,j, k,a fairly natural assumption on distance matrices, which holds in most instancesof the TRAVELING SALESMAN PROBLEM arising in practice. As it turns out, thisspecial case is partly approximable, and the best known error bound is ~. Whatis more, when the cities are restricted to be points on the plane with the usualEuclidean distances -another special case of obvious appeal and relevancethen the problem becomes fully approximable! Both special cases are knownto be NP-complete (see Problem 7.4.3 for the proof for the triangle inequalitycase).Backtracking and Branch-and-BoundAll NP-complete problems are, by definition, solvable by polynomially boundednondeterministic Turing machines; unfortunately we only know of exponentialmethods to simulate such machines.
We examine next a class of algorithms thattries to improve on this exponential behavior with clever, problem-dependentstratagems. This approach typically produces algorithms that are exponentialin the worst case, but often do much better.340Chapter 7: NP-COMPLETENESSA typical NP-complete problem asks whether any member of a large setSo of "candidate certificates", or "candidate witnesses" (truth assignments, setsof vertices, permutations of nodes, and so onrecall Section 6.4) satisfies certainconstraints specified by the instance (satisfies all clauses, is a clique of size K,is a Hamilton path). We call these candidate certificates or witnesses solutions.For all interesting problems, the size of the set So of all possible solutions istypically exponentially large, and only depends on the given instance x (its sizedepends exponentially on the number of variables in the formula, on the numberof nodes in the graph, and so on).Now, a nondeterministic TUring machine "solving" an instance of this NPcomplete problem produces a tree of configurations (recall Figure 6-3).
Eachof these configurations corresponds to a subset of the set of potential solutionsSo, call it S, and the "task" facing this configuration is to determine whetherthere is a solution in S satisfying the constraints of x. Hence, So is the setcorresponding to the initial configuration. Telling whether S contains a solutionis often a problem not very different from the original one. Thus, we can seeeach of the configurations in the tree as a subproblem of the same kind as theoriginal (this useful "self-similarity" property of NP-complete problems is calledself-reducibility). Making a nondeterministic choice out of a configuration, sayleading to r possible next configurations, corresponds to replacing S with r sets,S1,"" Sr, whose union must be S, so that no candidate solution ever fallsbetween the cracks.This suggests the following genre of algorithms for solving Np-completeproblems: We always maintain a set of active subproblems, call it A; initially,A contains only the original problem So; that is, A = {So}.
At each point wechoose a subproblem from A (presumably the one that seems most "promising"to us), we remove it from A, and replace it with several smaller subproblems(whose union of candidate solutions must cover the one just removed). This iscalled branching.Next, each newly generated subproblem is submitted to a quick heuristictest. This test looks at a subproblem, and comes up with one of three answers:(a) It may come up with the answer "empty," meaning that the subproblem under consideration has no solutions satisfying the constraint of the instance,and hence it can be omitted. This event is called backtracking.(b) It may come up with an actual solution of the original problem containedin the current subproblem (a satisfying truth assignment of the originalformula, a Hamilton cycle of the original graph, etc.), in which case thealgorithm terminates successfully.(c) Since the problem is NP-complete, we cannot hope to have a quick heuristictest that always comes up with one of the above answers (otherwise, wewould submit the original subproblem So to it).
Hence, the test will oftenreply"?" , meaning that it cannot prove that the subproblem is empty, but it7.4: Coping with NP-completeness341cannot find a quick solution in it either; in this case, we add the subproblemin hand to the set A of active subproblems. The hope is that the test willcome up with one of the two other answers often enough, and thus willsubstantially reduce the number of subproblems we will have to examine-and ultimately the running time of the algorithm.We can now show the full backtracking algorithm:A:= {So}while A is not empty dochoose a subproblem S and delete it from Achoose a way of branching out of S, say to subproblems S1, ...
,Srfor each subproblem Si in this list doif test(Si) returns "solution found" then haltelse if test(Si) returns "?" then add Si to Areturn "no solution"The backtracking algorithm terminates because, in the end, the subproblems will become so small and specialized that they will contain just one candidate solution (these are the leaves of the tree of the nondeterministic computation); in this case the test will be able to decide quickly whether or not thissolution satisfies the constraints of the instance.The effectiveness of a backtracking algorithm depends on three important"design decisions:"(1) How does one choose the next subproblem out of which to branch?(2) How is the chosen subproblem further split into smaller subproblems?(3) Which test is used?Example 7.4.5: In order to design a backtracking algorithm for SATISFIABILITY, we must make the design decisions (1) through (3) above.In SATISFIABILITY the most natural way to split a subproblem is to choosea variable x and create two subproblems: one in which x = T, and one inwhich x =.1...
As promised, each subproblem is of the same sort as the originalproblem: a set of clauses, but with fewer variables (plus a fixed truth assignmentfor each of the original variables not appearing in the current subproblem). Inthe x = T subproblem, the clauses in which x appears are omitted, and x isomitted from the clauses in which it appears; exactly the opposite happens inthe x = .1.. subproblem.The question regarding design decision (2) is, how to choose the variablex on which to branch. Let us use the following rule: Choose a variable thatappears in the smallest clause (if there are ties, break them arbitrarily).
This isa sensible strategy, because smaller clauses are "tighter" constraints, and maylead sooner to backtracking. In particular, an empty clause is the unmistakablesign of unsatisfiability.342Chapter 7: NP-COMPLETENESSNow for design decision (1) -how to choose the next subproblem. In linewith our strategy for (2), let us choose the subproblem that contains the smallestclause (again, we break ties arbitrarily).Finally, the test (design decision (3)) is very simple:if there is an empty clause, return "subproblem is empty;"if there are no clauses, return "solution found;"otherwise return "7"See Figure 7-14 for an application of the backtracking algorithm describedabove to the instance(x V Y V z), (x V y), (y V z), (z V x), (x V y V z),which we know is unsatisfiable (recall Example 6.3.3).
As it turns out, thisalgorithm is a variant of a well-known algorithm for SATISFIABILITY, knownas the Davis-Putnam procedure. Significantly, when the instance has atmost two literals per clause, the backtracking algorithm becomes exactly thepolynomial purge algorithm of Section 6.3.0"empty""empty""empty""empty""empty"Figure 7-14Example 7.4.6: Let us now design a backtracking algorithm for HAMILTONIn each subproblem we already have a path with endpoints a and b, say,and going through a set of nodes T ~ V - {a, b}.
We are looking for a Hamiltonpath from a to b through the remaining nodes in V, to close the Hamilton cycle.Initially a = b is an arbitrary node, and T = 0.Branching is easy --we just choose how to extend the path by a new edge,say [a, el, leading from a to a node c rf:. T. This node e becomes the new valueCYCLE.7.4: Coping with NP-completeness343of a in the subproblem (node b is always fixed throughout the algorithm). Weleave the choice of the subproblem from which to branch unspecified (we pickany subproblem from A). Finally, the test is the following (remember that in asubproblem we are looking for a path from a to b in a graph G - T, the originalgraph with the nodes in T deleted).if G - T - {a, b} is disconnected, or if G - T has a degree-one nodeother than a or b, return "subproblem is empty;"if G - T is a path from a to b, return "solution found;"otherwise return "?"Figure 7-15: Execution of backtracking algorithm for HAMILTON CYCLE on thegraph shown in the root.
Initially both a and b coincide with the dotted node.In the leaf (backtracking) nodes the degree-one nodes are circled (in the middleleaves there are many choices). A total of nineteen subproblems is considered.The application of this algorithm to a simple graph is shown in Figure344Chapter 7: NP-COMPLETENESS7-15. Although the number of partial solutions constructed may seem large(nineteen), it is minuscule compared to the number of solutions examined bythe full-blown nondeterministic "algorithm" for the same instance (this numberwould be (n - I)! = 5,040). Needless to say, it is possible to devise moresophisticated and effective branching rules and tests than the one used here.<>Determining the best design decisions (1) through (3) depends a lot notonly on the problem, but also on the kinds of instances of interest, and usuallyrequires extensive experimentation.Backtracking algorithms are of interest when solving a "yes-no" problem.For optimization problems one often uses an interesting variant of backtrackingcalled branch-and-bound.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
