Page 24/24 Date 03.05.2017 Size 186.06 Kb.
dad[] array to store augmenting path A way to determine an augmenting path for the graph How that this be done in a regular, efficient way? We need to be careful so that if an augmenting path exists, we will find it, and also so that "quality" of the paths is fairly good Implementing FF approach Ex: Consider the following graph Poor algorithm: Aug. Paths SABT (1), SBAT (1), SABT (1), SBAT (1) … Every other path goes along edge AB in the opposite direction, adding only 1 to the overall flow 2000 Aug. Paths would be needed before completion Implementing FF approach Good algorithm: Aug. Paths SAT (1000), SBT (1000) and we are done In general, if we can find aug. paths using some optimizing criteria we can probably get good results Edmonds and Karp suggested two techniques: Use BFS to find the aug. path with fewest edges Use PFS to find the aug. path with largest augment In effect we are trying to find the path whose segments are largest Since amount of augment is limited by the smallest edge, this is giving us a "greatest" path See board and flownew.cpp Implementing FF approach Let's look at flownew.cpp For now we will concentrate on the "main" program Later we will the PFS augmenting path algo Main will work with BFS or PFS – it uses algo to build spanning tree starting at source , and continuing until sink is reached Total flow is updated by the value for the current path Each path is then used to update residual graph Path is traced from sink back to source, updating each edge along the way If sink is not reached, no augmenting path exists and algorithm is finished Unsolvable problems Some computational problems are unsolvable No algorithm can be written that will always produce the "right" answer Most famous of these is the "Halting Problem" Given a program P with data D, will P halt at some point? It can be shown (through a clever example) that this cannot be determined for an arbitrary program Other problems can be "reduced" to the halting problem Indicates that they too are unsolvable Intractable Problems Some problems are solvable, but require an exponential amount of time We call these problems intractable For even modest problem sizes, they take too long to solve to be useful Ex: List all subsets of a set Ex: List all permutations of a sequence of characters We know this is Theta(2N) We know this is Theta(N!) Polynomial Problems Most useful algorithms run in polynomial time Largest term in the Theta run-time is a simple power with a constant exponent Most of the algorithms we have seen so far this term fall into this category NP-Complete Problems Background Some problems don't (yet) fall into any of the previous 3 categories: We have not proven that any solution requires exponential execution time No one has been able to produce a valid solution that runs in polynomial time It is from within this set of problems that we produce NP-complete problems NP-Complete Problems More background: Define P = set of problems that can be solved by deterministic algorithms in polynomial time What is deterministic? At any point in the execution, given the current instruction and the current input value, we can predict (or determine) what the next instruction will be Most algorithms that we have discussed this term fall into this category NP-Complete Problems Define NP = set of problems that can be solved by non-deterministic algorithms in polynomial time What is non-deterministic? Formally this concept is tricky to explain Involves a Turing machine Informally, we allow the algorithm to "cheat" We can "magically" guess the solution to the problem, but we must verify that it is correct in polynomial time Naturally, our programs cannot actually execute in this way We simply define this set to categorize these problems http://www.nist.gov/dads/HTML/nondetermAlgo.html http://en.wikipedia.org/wiki/Nondeterministic_algorithm NP-Complete Problems Ex: TSP (Traveling Salesman Problem) Instance: Given a finite set C = {c1, c2, … cm} of cities, a distance d(cI,cJ)for each pair of cites, and in integer bound, B (positive) Question: Is there a "tour" of all of the cities in C (i.e. a simple cycle containing all vertices) having length no more than B? In non-deterministic solution we "guess" a tour (ex: minimum length) and then verify that it is valid and has length <= B or not within polynomial time In deterministic solution, we need to actually find this tour, requiring quite a lot of computation No known algo in less than exponential time NP-Complete Problems So what are NP-Complete Problems? Naturally they are problems in set NP They are the "hardest" problems in NP to solve All other problems in NP can be transformed into these problems in polynomial time If any NP-complete problem can be solved in deterministic polynomial time, then all problems in NP can be Since the transformation takes polynomial time, we would have A polynomial solution of the NP-Complete problem A polynomial transformation of any other NP problem into this one Total time is still polynomial NP-Complete Problems Consider sets P and NP: We have 5 possibilities for these sets: NP-Complete Problems 3 of these can be easily dismissed We know that any problem that can be solved deterministically in polynomial time can certainly be solved non-deterministically in polynomial time Thus the only real possibilities are the two in blue: P NP P is a subset of NP, as there are some problems solvable in non-deterministic polynomial time that are NOT solvable in deterministic polynomial time P = NP The two sets are equal – all problems solvable in non-deterministic polynomial time are solvable in deterministic polynomial time NP-Complete Problems Right now, we don't know which of these is the correct answer We can show P NP if we can prove an NP-Complete problem to be intractable We can show P = NP if we can find a deterministic polynomial solution for an NP-Complete problem Most CS theorists believe the P NP If not, it would invalidate a lot of what is currently used in practice Ex: Some security tools that are secure due to computational infeasibility of breaking them may not actually be secure But prove it either way and you will be famous! Proving NP-Completeness Situation: You have discovered a new computational problem during your CS research What should you do? Try to find an efficient solution (polynomial) for the problem If unsuccessful (or if you think it likely that it is not possible), try to prove the problem is NP-complete This way, you can at least show that it is likely that no polynomial solution to the problem exists You may also try to develop some heuristics to give an approximate solution to the problem Proving NP-Completeness How to prove NP-completeness? From scratch Show the problem is in NP Show that all problems in NP can be transformed to this problem in polynomial time Very complicated – takes a lot of work to do Luckily, we only need to do this once, thanks to method 2) below Through reduction Show that some problem already known to be NP-complete is reducible (transformable) to the new problem in polynomial time Idea is that, since one prob. can be transformed to the other in poly time, their solution times differ by at most a polynomial amount Heuristics Ok, so a problem is NP-complete But we may still want to solve it If solving it exactly takes too much time using a deterministic algorithm, perhaps we can come up with an approximate solution Ex: Optimizing version of TSP wants the minimum tour of the graph Would we be satisfied with a tour that is pretty short but not necessarily minimum? Ex: Course scheduling Ex: Graph coloring Heuristics We can use heuristics for this purpose Goal: Program runs in a reasonable amount of time, yet gives an answer that is close to the optimal answer How to measure quality? Let's look at TSP as an example Let H(C) be the total length of the minimal tour of C using heuristic H Let OPT(C) be the total length of the optimal tour Ratio bound: Heuristics For original TSP optimization problem, it can be proven that no constant ratio bound exists for any polynomial time heuristic But, for many practical applications, we can restrict TSP as follows: For each distance in the graph: d(cI,cJ) <= d(cI,cK) + d(cK,cJ) TRIANGLE INEQUALITY A direct path between two vertices is always the shortest Given this restriction, heuristics have been found that give ratio bounds of 1.5 in the worst case Local Search How do heuristics approach a problem? Many different approaches, but we will look only at one: Local Search Idea: Instead of optimizing the entire problem, optimize locally using a neighborhood of a previous sub-optimal solution We are getting a local optimum rather than a global optimum Let's look at an example local search heuristic for TSP (assuming triangle inequality) We call this heuristic 2-OPT 2-OPT 2-OPT Idea: Assume we already have a valid TSP tour We define a neighborhood of the current tour to be all possible tours derived from the current tour by the following change: Given that (non-adjacent) edges (a,b) and (c,d) are in the current tour, replace them with edges (a,c) and (b,d) See picture on board Note that each transformation guarantees a valid tour For each iteration we choose the BEST such tour and repeat until no improvement can be made See trace on board 2-OPT Implementation: can be done in a fairly straightforward way using an adjacency matrix Pseudocode: bestlen = length of initial tour while not done do improve = 0; for each two-opt neighbor of current tour diff = (C(A,B) + C(C,D)) – (C(A,C) + C(B,D)) if (diff > improve) improve = diff store current considered neighbor if (improve > 0) update new tour bestlen -= improve else done = true Let's look at the code – twoopt.c 2-OPT Performance issues: How big is a neighborhood (i.e. how many iterations will the foreach loop have)? Consider "first" edge in the original tour Cannot consider with it any adjacent edges or itself Thus, if the tour has n total edges, we have n-3 neighbor tours with the first edge in them Now consider the other edges in the original tour Same number of neighbor tours as the first However, each neighbor is considered twice (once from each original edge's point of view) Thus we have (N-3)(N)/2 total neighbors of the original tour Asymptotically Theta(N2) neighbors 2-OPT How many iterations are necessary (i.e. how many iterations of outer while loop are required?) In the worst case this can be extremely high (exponential) But this is a rare (and contrived) case In practice, few iterations of the outer loop are generally required What is the quality of the final tour? Again, in the worst case it is not good In normal usage, however, it does very well (a ratio bound of 1.05 on average, given a good initial tour) Variations on local search can improve the situation so that the worst case problems of 2-OPT go away More sophisticated algorithms such as simulated annealing and genetic algorithms Dynamic Programming In Divide and Conquer problems We break a large problem into subproblems and use the subproblem solutions to solve the original problem However, in some situations this approach is not an efficient one Famous example is the Fibonacci Sequence: Recursively we see: FIB(N) = FIB(N-1) + FIB(N-2) for N > 2 FIB(2) = FIB(1) = 1 Problems with Fibonacci However, if we trace the execution of this problem, we see that the execution tree is very large – exponential in N See simple trace on board If we approach this problem from the "bottom up", we can improve the solution efficiency Start by solving FIB(1), then FIB(2), and build the solution until we get to the desired value of N Now we are calculating each smaller solution only one time See fibo.java Dynamic Programming for Exponential Problems Some problems that have exponential run-times can be solved in pseudo-polynomial time using dynamic programming Idea: Given some instances of the problem, by starting at a solution to a small size and building up to a larger size, we end up with a polynomial run-time Example: Subset Sum Given a set of N items, each with an integer weight and another integer M Is there a subset of the set that sums to M? Subset Sum Exhaustive Search Try (potentially) every subset until one is found that sums to M or none are left Theta(2N) since there are that many subsets Branch and Bound If we do this recursively, we can stop the recursion and backtrack whenever the current sum exceeds M See subset.java Subset Sum Dynamic Programming Solve problem for M = 1, M = 2, … up to the input value of M Use the previous solutions in a clever way to help solve the next size We are using an array of size M to store information from previous answers Look at the code See structure Note that we are using a lot of space here However, note that we can come up with situations in which this solution is very good (pseudo polynomial) but also in which it is very poor Subset Sum N = 20, M = 1000 10 20 30 5 15 25 8 10 16 22 24 26 2 4 6 1 3 7 9 1000 This instance shows the worst case behavior of the branch and bound solution All combinations of the first 19 elements (2^19) must be tried but to no avail until the last element is tried It is poor because we don't ever exceed the "bound" so the technique doesn't help us The dynamic programming solution in this case is much better Subset Sum N = 4, M = 1111111111 1234567890 1357924680 1470369258 1111111111 This instance shows the worst case behavior of the dynamic programming solution Recall that our array must be size M, or 1111111111 Already, we are using an incredible amount of memory We must also process all answers from M = 1 up to M = 1111111111, so this is a LOT of work Since N = 4, the branch and bound version will actually work in very few steps and will be much faster This is why we say dynamic programming solutions are "pseudo-polynomial" and not actually polynomial Share with your friends:
The database is protected by copyright ©sckool.org 2020
send message
