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

 Page 24/24 Date 03.05.2017 Size 186.06 Kb. #18863

## 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://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