These notes are intended for use by students in cs1501 at the University of Pittsburgh and no one else



Download 186.06 Kb.
Page24/24
Date03.05.2017
Size186.06 Kb.
1   ...   16   17   18   19   20   21   22   23   24

Implementing FF approach

      • 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
  • S
  • A
  • B
  • T
  • 1000
  • 1000
  • 1000
  • 1
  • 1000

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:
  • P
  • NP
  • P
  • NP
  • NP
  • P
  • P
  • NP
  • NP P

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
      • Discuss
    • 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
      • Discuss

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

Download 186.06 Kb.

Share with your friends:
1   ...   16   17   18   19   20   21   22   23   24




The database is protected by copyright ©sckool.org 2020
send message

    Main page