Let us return to the example of finding shortest paths in Pittsburgh. Say we wanted to do what we talked about in first lecture: find shortest path from Skibo (imagine at intersection 0) to every other intersection in Pittsburgh. Paths from intersection to intersection like maze in homework two, except different streets have different lengths. That is, we have a graph (in the terms of homework two, a maze) with distances on edges. Also, might have one-way streets (one-way edges). Here, there's a dynamic programming approach that works pretty well, so let's look at that. Later we'll see a faster way using some more sophisticated data structures.
30 50
5-------------------3-----------------4- Fifth
^ | |
15 | S. Dithridge 20 | S. Craig 15 | Moorewood
^ (one way) | |
| | |
6-------------2-------------------1-----------------0-- Forbes
30 30 45 Skibo
Say our map has N nodes and E edges.
Dynamic programming approach: need to organize problem into sequence of subproblems of larger and larger sizes so can solve next larger based on previous solutions. For this problem, break it up in this way: Ask "what's the shortest path to point X that uses at most i edges?" (If none, write "infinity"). This gives us a table:
node #: 0 1 2 3 4 5 6
-------------------------------------
i = 0 |
i = 1 |
i = 2 |
To calculate the shortest path to X with at most i edges, we can take the smaller of:
Our algorithm, therefore, looks like the following. Say we have a two-dimensional array whose element distance[X][i] will contain the shortest path to X using at most i edges. First, initialize all distances to infinity, except the starting point itself, which will be zero (``infinity'' will be some horrendously large number in an implementation in C). Then our algorithm will go as follows:
for(i=1; i < n; ++i) { /* number of edges */
for each node X {
for each edge e from some V to X
distance[X][i] = min(distance[X][i-1], distance[V][i-1] + length[e]);
}
}
What's the running time of this? Well, we have three loops, so a good
estimate is O(N²E). Actually, you can refine
this a bit; think about it a while.
Since we have an adjancency list representation here, the inner loop is used only as many times as we have neighbors out of X, rather than the total number of edges. The total time, then, of the algorithm will be N (for the outer loop) times the sum over all nodes of the number of edges from each node. The latter is at most twice E, so it's more accurate to say that the algorithm is O(NE).
Recall the knapsack problem from class: you have a bunch of tasks, each has a time to complete, and a value. You have some fixed amount of time to spend and you want to know the maximum value you can get.
Idea of solution: say you have time t, and tasks 1,...,i. Then the best solution either DOESN'T use item i, in which case your value is the best you can do with time t and items 1,...,i-1, or else it DOES use item i, in which case your value is value[i] + (best you can do with time t - time[i] and items 1,...,i-1).
Consider a recursive implementation: say given time "t", items 1,...,n. This returns the maximum value achievable:
int
knapsack(int t, int n) {
if(t <= 0 || n == 0) return 0;
if(time[n] > t) return knapsack(t, n-1); // not enough time to do item n.
return max(knapsack(t, n-1), knapsack(t - time[n], n-1) + value[n]);
}
(Say max is a function, not a macro.)
Why does this return the correct value?
How long does this take? Lets consider case where time[i] is small and n is big. Then to solve on n, call twice on n-1. Thus this is exponential in n.
Now, let's use memoizing. We start with array varr[][] with each element initialized to UNKNOWN = -1:
int
knapsack2(int t, int n) {
if(t < 0) return 0;
if(varr[t][n] != UNKNOWN) return varr[t][n];
if(t == 0 || n == 0) varr[t][n] = 0;
else if (time[n] > t) varr[t][n] = knapsack(t, n-1);
else varr[t][n] = max(knapsack(t, n-1),
knapsack(t - time[n], n-1) + value[n]);
return varr[t][n];
}
How much time does this take?
It takes O(NT). You can see this by observing that this just like the dynamic programming solution, but top-down. Try doing an example to see how this works. Look at it this way: We only go past the (... != UNKNOWN) line once per pair (t,n). (t>0 and n>0). So we only execute the ``else'' lines at most n*t times. So we have at most --> at most 2*n*t + 1 calls to knapsack2, since except for the very first call (the "+ 1"), every call results from executing an "else" line, and executing one of those lines causes <= 2 calls to be made.