Editing Dynamic programming

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 132: Line 132:
  
 
So we can finally conclude that the total number of ways to go from <math>x_0</math> to <math>x_n</math> is the ''sum'' of the number of ways to go from <math>x_0</math> to <math>x_i</math> for all <math>i</math> such that we can make the trip from <math>x_i</math> to <math>x_n</math> in a single step (that is, <math>A \leq x_n - x_i \leq B</math>).
 
So we can finally conclude that the total number of ways to go from <math>x_0</math> to <math>x_n</math> is the ''sum'' of the number of ways to go from <math>x_0</math> to <math>x_i</math> for all <math>i</math> such that we can make the trip from <math>x_i</math> to <math>x_n</math> in a single step (that is, <math>A \leq x_n - x_i \leq B</math>).
 
===Example===
 
Consider the standard set of locations in the problem statement: 0, 990, 1010, 1970, 2030, 2940, 3060, 3930, 4060, 4970, 5030, 5990, 6010, 7000. Let <math>A = 970</math> and <math>B = 1040</math>. The problem statement tells us that there are four ways to make the trip; we will see how to compute this number.
 
 
As indicated above, in order to count trips from 0 to 7000, we should consider all possible final legs of the trip, that is, consider every possible motel that is between 970 and 1040 km away from our final destination and assume that we will first travel there in some number of days, stay the night there, and then drive to the final destination on the final day. There are two possible motels that could come just before our final destination: the one at 5990 and the one at 6010.
 
 
By trial and error, we can determine by hand that there is one possible path that ends up at 5990, that is: 0-990-1970-2940-3930-4970-5990. There are also three possible paths that end up at 6010: 0-990-1970-2940-3930-4970-6010, 0-990-2030-3060-4060-5030-6010, 0-1010-2030-3060-4060-5030-6010. From the one path ending at 5990, we can construct one path ending at 7000 with final leg 5990, simply by appending it onto the end: 0-990-1970-2940-3930-4970-5990-7000. From the three paths ending at 6010, we can construct three paths ending at 7000 with final leg 6010, simply by appending the leg 6010-7000 to the end of each one: 0-990-1970-2940-3930-4970-6010-7000, 0-990-2030-3060-4060-5030-6010-7000, 0-1010-2030-3060-4060-5030-6010-7000. We see that all four of the paths we obtained in this way are distinct, and, furthermore, they cover all possible paths from 0 to 7000, because if we take any path from 0 to 7000, either it ends in 5990-7010 or it ends in 6010-7010, and then after removing the final leg we must get a valid path to 5990 or a valid path to 6010, and we have enumerated all of those already. We conclude that, to find the number of paths from 0 to 7000, we add the number of paths from 0 to 5990 and the number of paths from 0 to 6010. If <math>A</math> and <math>B</math> were different, we might have to consider a different set of penultimate destinations, but the idea is the same.
 
  
 
===Pseudocode implementation===
 
===Pseudocode implementation===
Line 155: Line 148:
 
</pre>
 
</pre>
  
==Paths in a DAG==
+
<!--
All counting problems solvable by DP are ultimately isomorphic to the problem of counting paths in a directed acyclic graph, or DAG. This problem itself has a simple DP solution, but more complicated problems can be solved by thinking of them in this way.
+
==General example: Nukit==
 
+
The problem {{Problem|ccc08s5|Nukit}}
===Example problem: Water Park===
+
We will start by considering the problem {{Problem|ccc07s4|Water Park}}, which is similar to ''Keep On Truckin''' but slightly more general. The input is a network of water slides. Each water slide connects two points, and you always slide from the higher point to the lowest point, for obvious reasons, but there may be multiple water slides that go into or come out of a single point. The problem is to determine how many different ways there are to go from the highest point (labelled 1) to the lowest point (labelled <math>n</math>) by sliding down the given water slides. Two ways are different if at one of them uses a slide that the other one does not use.
+
 
+
We solve this problem using reasoning very similar to that used in ''Keep on Truckin'''. In order to count the number of paths from point 1 to some point <math>p > 1</math>, we divide the paths into categories based on the last slide taken along the path. That is, for any given path from point 1 to point <math>p</math>, we either travelled directly from point 1 to point <math>p</math>, or we travelled from point 1 to point 2 then took a final, additional slide from point 2 to point <math>p</math>, or we travelled from point 1 to point 3 then took a final, additional slide from point 3 to point <math>p</math>, and so on. These categories of paths are disjoint because two paths from different categories have different final slides and therefore cannot be the same; they are exhaustive because every path from point 1 to point <math>p</math> has to have ''some'' final slide and will hence end up in that slide's category. Finally, the size of each category is the number of paths from point 1 to the initial point of the final slide corresponding to that category.
+
 
+
We conclude that, in order to compute the number of paths from point 1 to point <math>p</math>, we make a list of slides that lead directly into point <math>p</math>, and then add up the number of paths into the initial point of each slide. Denote the initial point of a slide by <math>i(S)</math> and the terminal point by <math>t(S)</math>. Thus:
+
:<math>\displaystyle f(p) = \begin{cases} 1 & p = 1 \\ \sum_{i(S) = p} \, f(t(S)) & p > 1 \end{cases}</math>
+
We could also express this as follows:
+
:<math>\displaystyle f(p) = \begin{cases} 1 & p = 1 \\ \sum_{q < p} \, n_{qp} f(q) & p > 1 \end{cases}</math>
+
where we sum over all vertices higher (lower-numbered) than <math>p</math> and <math>n_{pq}</math> is the number of slides from <math>q</math> to <math>p</math>. (Note that the problem statement does not rule out multiple slides between the same pair of points!)
+
 
+
===Example===
+
Again, an example will help to illuminate the discussion. Suppose there are slides from 1 to 2, 1 to 3, 1 to 4, 2 to 3, 2 to 4, and 3 to 4. We want to compute the number of paths from point 1 to point 4. To do this, we first make a list of all the slides leading directly into point 4. There are three of these: 1-4, 2-4, and 3-4. Then we add the number of paths from 1 to 4 that end with the 1-4 slide, the number of paths from 1 to 4 that end with the 2-4 slide, and the number of paths from 1 to 4 that end with the 3-4 slide.
+
 
+
There is one path from 1 to 2: 1-2 (a single slide). We can obtain a path from 1 to 4 by adjoining 1-4, hence: 1-2-4. There are two paths from 1 to 3: 1-2-3 and 1-3; from these we obtain two paths from 1 to 4: 1-2-3-4 and 1-3-4. Finally, we shouldn't forget the direct path 1-4. We see that <math>f(4) = f(1) + f(2) + f(3)</math>; <math>f(1)</math> counts the one path from 1 directly to 4, <math>f(2)</math> counts the one path from 1 to 2 then directly to 4, and <math>f(3)</math> counts the two paths from 1 to 3 and then directly to 4. This covers all possible paths from 1 to 4 with no double-counting.
+
 
+
===Generalization===
+
This problem may be abstracted as follows: you are given a [[directed acyclic graph]]. The network of water slides is a graph, where each point is a vertex and each slide is an edge; it is directed because you can only go one way along each edge; and it is acyclic because you cannot proceed down a sequence of slides and get back to where you started from (you will always end up somewhere lower). You want to determine how many different paths there are in this graph between a given pair of nodes, say, node <math>s</math> and node <math>t</math>.
+
 
+
The general solution is to visit nodes in [[topological order]] from <math>s</math> to <math>t</math>; that is, visit nodes in an order such that, by time time we visit a node, we have already visited all the nodes with edges leading into that node. In ''Water Park'', this was easy: we just visit nodes in increasing numerical order. In general, this problem has disjoint and exhaustive substructure and we use the formula
+
:<math>\displaystyle f(s, u) = \begin{cases} 1 & u = s \\ \sum_{e = (v, u) \in E} \, f(s, v) & \text{otherwise} \end{cases}</math>
+
where the bottom line tells to sum over all edges <math>e \in E</math> into <math>u</math>; in the summand, <math>v</math> denotes the vertex that edge points away from.
+
  
Many optimization problems can be cast into a similar paradigm; here the analogous problem is finding the shortest (or longest) path between two vertices in a DAG, where each edge has some real number, its length. (Usually the problem would in fact be to find the optimal length, rather than the path itself.) We can now revisit ''Plentiful Paths'' in this light. The entire field may be considered a DAG, where each square is a vertex and there is an edge from one square to another if they are adjacent and the latter is either above or to the right of the former. Label an edge with 1 if its destination vertex contains an apple, or 0 if it does not. In this way, every possible way we can travel from the lower-left corner to the upper-right corner is assigned a weight that equals the number of apples we can collect along this path. (Actually, it will be off by one if the initial square contains an apple, but this effects only a trivial modification to the algorithm.) The problem is therefore to find the longest path between the vertices corresponding to the lower-left and upper-right squares in the DAG, and we use the formula
+
===
:<math>\displaystyle f(s, u) = \begin{cases} 0 & u = s \\ \max_{e = (v, u) \in E} \, f(s, v) + w(e) & \text{otherwise} \end{cases}</math>
+
where <math>w(e)</math> is the length or weight of the edge <math>e</math>. To find a shortest path instead of a longest path, replace <math>\max</math> with <math>\min</math>, or multiply all edge weights by -1. The meaning of this formula in this specific case is as follows: <math>f(s, v)</math> is the maximum number of apples that could've been collected by travelling from <math>s</math> to <math>v</math>, and <math>v</math> is either directly below or directly to the left of <math>u</math>, since it must be possible to travel directly from <math>v</math> to <math>u</math>. <math>w(e)</math> is 1 if there is an apple in square <math>u</math>, and 0 otherwise. By taking the maximum value of <math>f(s, v) + w(e)</math> for the two possible choices of <math>v</math>, we're selecting the predecessor square with the better optimum path (since <math>w(e)</math> in this case is independent of <math>v</math>). All this is exactly the same as in the original solution.
+
  
===State and dimension===
 
Problems that involve travelling from one place or another often obviously fall into the DAG paradigm, but the paradigm is far more general than that. Indeed, traversing a DAG topologically is the essence of DP. In all the examples we've seen so far, we would likely use an array to store the values we have computed so far. Some entries in this array depend on others, and there is usually an obvious base case (an entry we can write down trivially without examining any others) and our objective is to compute some particular entry. Of course, two entries should not depend on each other, because then we would have no way to compute either of them. This system of dependencies can be expressed by identifying each entry of the array with a vertex of the DAG and each dependency as an edge; the base case corresponds to a source of the DAG, and the final entry we want is usually a sink (since there is no point in computing additional entries that depend on the answer after we have already computed the answer).
 
  
The key to solving any problem by DP, then, is to find a useful way to construct a DAG such that each vertex's value is some function of only the values of the vertices with edges leading into it (and not the details of the path taken from the source to those vertices), and where it is simple to compute the value of the source, and, finally, where the value of the sink will be the answer to the problem instance. If the DAG is not big enough, then the rule that each vertex's value must depend only on the values of the vertices immediately before it won't be satisfied; if it's too big, then the algorithm will likely be inefficient since we need to compute the values of all (or almost all) other vertices before we can get to the value we want at the sink.
+
==Counting example: Water Park==
 +
Another problem that admits a simple dynamic solution is {{Problem|ccc07s4|Water Park}}. The input is a network of water slides. Each water slide connects two points, and you always slide from the higher point to the lowest point, for obvious reasons, but there may be multiple water slides that go into or come out of a single point. The problem is to determine how many different ways there are to go from the highest point (labelled 1) to the lowest point (labelled <math>n</math>) by sliding down the given water slides. Two ways are different if at one of them uses a slide that the other one does not use.
  
We say that we want to pick the appropriate '''states''' and '''transitions'''. A state is a vertex of the DAG, and we will usually represent it with one or more integers, indices into the array we use to do the DP. Transitions are identified with the edges leading into any given vertex, and represented by a transition function <math>g</math>, so that <math>f(u) = g(f(v_1), f(v_2), ...)</math> where <math>f</math> is the function we are trying to compute and <math>v_1, v_2, ...</math> are the vertices with an edge pointing out of them into the vertex <math>u</math> of interest. (The case of multiple edges between a given pair of vertices is similar.) Usually, the number of states in the DP will be approximately <math>N^k</math> for some positive integer <math>k</math>, where <math>N</math> is the size of the problem instance. If this is the case, we call the DP '''<math>k</math>-dimensional'''; we will probably use a <math>k</math>-dimensional array to store the values computed so far.
+
This problem may be abstracted as follows: you are given a [[directed acyclic graph]]. The network of water slides is a graph, where each point is a vertex and each slide is an edge; it is directed because you can only go one way along each edge; and it is acyclic because you cannot proceed down a sequence of slides and get back to where you started from (you will always end up somewhere lower). You want to determine how many different paths there are in this graph between a given pair of nodes.
 +
-->
  
 
[[Category:Algorithms]]
 
[[Category:Algorithms]]

Please note that all contributions to PEGWiki are considered to be released under the Attribution 3.0 Unported (see PEGWiki:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

Cancel | Editing help (opens in new window)

Templates used on this page: