The primary topics in this part of the specialization are: shortest paths (Bellman-Ford, Floyd-Warshall, Johnson), NP-completeness and what it means for the algorithm designer, and strategies for coping with computationally intractable problems (analysis of heuristics, local search).
A Dynamic Programming Heuristic for Knapsack
Loading...
En provenance du cours de Stanford University
Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
378 notes
À partir de la leçon
Week 3
Approximation algorithms for NP-complete problems.
Rencontrer les enseignants
Tim RoughgardenProfessor
Computer Science
A greedy heuristic for the knapsack problem is pretty good, but let's work a
little harder and do quite a bit better. We're going to accomplish a quite
ambitious goal. The knapsack problem, being NP-complete,
is not we expect going to admit an exact polynomial time algorithm.
Let's shoot for the next best thing, arbitrarily close approximation.
That is, let's accept from a user error parameter epsilon, and, return the
solution whose value is guaranteed to be at least ibe minus epsilon times that of
an optimal knapsack solution. So, a client who wants to be guaranteed
that this heuristic outputs a solution with a 99% of optimal just has to set
epsilon to be 0.01. If this sounds a little too good to be
true, there is a catch. The running time is going to increase as
we take epsilon to be smaller and smaller.
But what this algorithm exports to the client is an accuracy running time
trade-off. That is, it exports via this parameter
epsilon a knob that the user can turn wherever they want.
If you want more accuracy and are willing to wait a little bit longer, you set
epsilon to be epsilon to be smaller. If you want something really fast and
you're okay with a bit of inaccuracy, you take espsilon to be bigger.
And, this is as good as it gets, for Np-complete problems.
Assuming P is not equal to NP, there's no way to solve it exactly in polynomial
time, the next best thing you can have, hope for, is arbitrarily close
approximation, in polynomial time. That is what we will get for the napsack
problem using a dynamic programming base heuristic.
Sadly, the knapsack problem is the exception that proves the rule. Most
NP-complete problems, it is believed you cannot get an arbitrarily close
approximation. One concrete example is the vertex cover
problem, we discussed exact, expnential time
algorithms for vertex cover in a seperate video and we've been talking about
polynominal time heuristics for vertex cover, and there are some good ones. You
can get within a factor two of an optimum vertex cover in polynomial time, but, it
is believed you cannot get arbitrarily close approximation of the optimal vertex
cover in polynomial time. In fact, if you came up with such an algorithm, that
would imply p equals NP. While there are some other problems out
there like knapsack that admit arbitrarily close approximation, there's
many more out there which are like vertex cover where, assuming p not equal to NP,
it is not possible to get arbitrarily close approximation in polynomial time.
But this is an algorithms class, we should stay positive and focus on what
you can do. So let's move on to the arbitrarily close
approximation for knapsack. So the high-level idea is both very cool
and also very natural. What we're going to do is we're going to
take the knapsack instance that we're given, so items that have values and
weights, and some kapsack capacity. And we're going to massage it a little
bit, not too much, just a little bit but we
want to put it squarely in one of our computationally tractable special cases,
and then, we're going to solve this transformed version of the original
input. Now, because we're not solving the
problem that we were given, we're not going to get the right answer.
But as long as we didn't transform it too much, we can hope that the optimal
solution to the transformed problem is a pretty good approximation of the original
problem that we were give. Well, what's a computationally tractable
special case of the knapsack problem? To date, we do know one, but we only know
one so far, which is if we assume that the sizes of the items in the knapsack
capactiy are integers, we can go back to our dynamic programing solution for the
knapsack problem which runs in time, n, the number of items time capital W, the
knapsack capacity. So if it were the case of the knapsack
capacity W wasn't too big, if for example, it was polynomial and the number
of items, n, then this dynamic programing algorithm would run in polynomial time.
For technical reasons, which I'll say a little bit more about later, this
computationally tractable special case is not well-suited for deployment in a
dynamic programming heuristic. Instead, we're going to want to develop a
second similar but different computationally tractable special case.
The second special case is when the sizes and the knapsack capacity can be
arbitrary, but where the item values are integers that are not too big. This
assumption can also be exploited by a dynamic programing algorithm. As we'll
show in a separate video, there is a different dynamic programming
algorithm for the knapsack problem, whose running time is N squared times the
largest item value, N squared times Vmax.
So from this second dynamic programming algorithm, we can extract a second
computationally tractable special case of the knapsack problem.
Namely if all of the item values are small integers, say a polynomial in the
number of items n, then this dynamic programming algorithm already gives us a
polynomial time algorithm for instances of that form.
Armed with the second computationally tractable special case, we can now return
to the high-level idea at the beginning of this slide and execute it.
Here's how we do it. Our knapsack algorithm is given some
knapsack instance, the item values need not be small integers.
Now we massage the instance a little bit. We transform it, so that it becomes an
instance that we know how to solve in polynomial time.
How do we do that? We force the item values to be small integers.
How do you take arbitrary numbers and make sure that they're small numbers?
Well, the first thing to try is drop the low order bits and that's essentially
what we're going to do. Our algorithm then, solves this
transformed instance, by construction, the instance has small item value so we
can solve it in polynomial time using our second dynamic programing algorithm.
Now, we're probably not going to get an optimal solution to the original
instance. After all, we solved the wrong instance.
Unless we transform the values before invoking our dynamic programming
algorithm. But, the hope, and this is just a hope,
this is definitely going to require a proof. The hope is that we didn't loose
too much information just by throwing out some lower order bits.
So, by virtue of computing a solution which is 100% optimal, for the almost
correct problem, maybe that solution is also almost optiomal for the fully
correct correct problem. So here is the algorithm in full detail.
It really only has two steps. Fist, we do the transformation.
We round the item values to the small integers,
then we invoke the second dynamic programming algorithm on the transformed
instance. Precisely, here is how we round each item
value v sub i. To begin, we decrease vi to the nearest
multiple of a parameter m. I'm going to leave this parameter m
unspecified at the moment and therefore this algorithm will be undetermined.
Once we start analyzing the algorithm, we'll see what the parameter m has to be
as a function of epsilon. So don't forget that epsilon is the
accuracy parameter supplied by our client.
If the client sets a given value of epsilon, what it means is that our
responsibility is to output a feasible solution with value at least one minus
epsilon times that of an optimal solution.
So the smaller the epsilon, the more accurate our algorithm needs to be.
When we round an item value vi down to the nearest multiple of m, we're
decreasing it by an amount somewhere between 0 and m.
If vi was already a multiple of m, we don't decrease it at all.
If vi was just below a multiple of m, then we wind up decreasing it by
essentially m. Therefore, the bigger the m, the more
information we're throwing out about our instance and the less we should expect
our accuracy. That is, the smaller value of epsilon the
more accuracy demanded by our client, the smaller we're going to have to take our
value of m. Now, once we've made everything a
multiple of m, we may as well just scale down,
we may as well divide everything by m, we're going to get integers.
The integers that we get after rounding down to the nearest multiple of m and
then dividing by m are going to be called the V hats.
An alternative succinct way to describe the V hats is V hat i is by definition,
Vi/m rounded down. And so these funny brackets in blue on
the right, that's called the floor operator,
that takes in a real number and returns the biggest integer that's less than or
equal to the input. Thus, what is the transformation? In
effect, we take the item values that were given, we divide them by this parameter m
and then we also round down just to make sure we're dealing with integers.
Step 2 of our heuristic is to just invoke the second dynamic programming algorithm
to solve exactly the transformed instance.
That is, we feed into that second dynamic programming algorithm, the instance with
N items, the sizes are exactly the same as in the knapsack instance we were given
originally. The knapsack capacity, capital W, is
exactly the same we were given originally, but we feed in the values, V
hat one through V hat n. That is, we solve it with respect to the
transformed values, not with respect to the original values,
the Vi's. Let's make two quick observations before
we conclude. So first of all, remember the dynamic programming algorithm, the
second one for knapsack, the running time is n squared times the largest item
value, and of course, here we're running the dynamic programming algorithm with
these transformed item values the V hats. So therefore, if the V hat are big, then
this running time is slow, if the V hats are small, then this
running time is going to be reasonable. Now, let's remember the definition of the
V hats. They're essentially the original item
values divided by this magical parameter m, which we haven't yet specified.
But qualitiatively, if m is big, the V hats are going to small and the running
time is going to be fast. On the other hand, if m is small, the V
hats are going to be big and this algorithm is going to be slow.
That's how m controls the running time of this dyanamic programming base heuristic.
Also, remember we argued how intutitively it seemed to be controlling the accuracy.
The more you jack up m, the more information you lose when you round the
Vs and transform them into the V hats, and so, the less accuracy you're going to
have. So bigger m means, on the one hand,
faster running time, but at the cost of worst accuracy.
So this parameter m, really a knob that we can tune to figure out whether we want
a faster algorithm or higher accuracy. The non-trivial statement which we need
to prove in the next video is that there's a sweet spot for m.
That you can simultaneously get a pretty good running time, poloynomial running
time and excellent accuracy. So one trivial observation, but that's
still really nice, is that this dynamic programming based heuristic is guaranteed
to produce a feasible solution. Whatever output of items we get in step
2, it's guaranteed to fit inside the knapsack.
The reason for that is we pass to the dynamic programming algorithm in step 2,
fully accurate sizes, the original Wi's, and similarly a fully accurate knapsack
capacity, capital W. Therefore, the feasible solutions for the
transform knapsack instance are exactly the same as they were in the original
knapsack instance. This explains why we needed to develop a
second dynamic programming algorithm for knapsack, rather than trying to use the
the first one we developed. Thankfully there is this second
computation retractable special case where the items have small sizes and that
turns out to be exactly what you want to make this two-step recipe work.
The analysis is coming right up.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2019 Coursera Inc. Tous droits réservés.
