March 29, 2008 at 11:38Dynamic programming in practice.
This is my first article on such topics, so please treat with understanding. I will be glad to any comments and comments.
I think many of you have heard, and many have even come across such a method of solving certain problems as the dynamic programming method. For those who don’t know, here is the Wikipedia definition:
A pretty good and understandable explanation, but let's better take an example. I think the simplest thing that comes to mind is the Fibonacci numbers. For it, some initial data are given - A [1] = 1, A [2] = 1, after which the element A [i] = A [i-1] + A [i-2]. Moreover, A [i] is often called a state , and a certain relation with respect to the calculated data is called a transition . In this case, there are 2 transitions from A [i] - to A [i-1] and to A [i-2]. The number of transitions may vary depending on the task.
But dynamic programming is not just used. Namely, because it can sometimes very significantly reduce the time it takes to solve a problem, which sometimes, with large volumes of input data, can be very critical. And I want to show one such problem that I met at the Zone School Olympics this year. Literally, I don’t remember the condition, but here is the general meaning:
So, in order to know the value of the elements in any line, we need to know the values of the elements in all lines above it. The simplest solution that comes to mind is for each element to simply take and go through all the elements in the triangle above it, counting the sum. Yes, this can be done when time is not critical or when the restrictions on N and M are small, because such an algorithm works for the asymptotics of order O (N 4) (if we take N = M). Those. even with N = M = 100 it will work on the order of 5-10 seconds (depends on the computer), I am already silent about N = M = 2000. So, we need to speed up this business somehow. And let's do this. We have a triangle that needs to be counted. And we have pre-calculated triangles for all the elements above it. So let's make a new triangle using the ones already calculated! We look at the picture:
i.e. if we need to calculate a triangle with a beginning in A [i, j], then it will be calculated by the formula:
A [i, j] = (A [i-1, j] + 2 * A [i-1, j-1 ] + 2 * A [i-1, j + 1] -2 * A [i-2, j]) mod K. (where mod K - take modulo K)
We subtract the triangle A [i-2, j] since this is the intersection region of two triangles A [i-1, j-1] and A [i-1, j + 1], otherwise we would count it 2 times. By the way, think for yourself why we multiply by 2 some values.
The general idea of this task is this. Try to write its solution yourself (there are several nuances in it that I suggest you find for yourself) and test it using the usual brute force algorithm on different tests. If something is not clear - please contact, I will try to help, although I must admit that I myself am not a pro in this matter and I can not solve all problems, but I am capable of something ;-)
I think many of you have heard, and many have even come across such a method of solving certain problems as the dynamic programming method. For those who don’t know, here is the Wikipedia definition:
The idea of dynamic programming is to divide the problem into several independent subtasks, solve each of them, and then calculate the initial result. To solve the subtasks, the same algorithm is applied recursively. In this case, for each subtask, the calculated answer is remembered, and if at some step the subtask met a second time, then no calculations are performed for it.
http://ru.wikipedia.org/wiki/Dynamic_programming
A pretty good and understandable explanation, but let's better take an example. I think the simplest thing that comes to mind is the Fibonacci numbers. For it, some initial data are given - A [1] = 1, A [2] = 1, after which the element A [i] = A [i-1] + A [i-2]. Moreover, A [i] is often called a state , and a certain relation with respect to the calculated data is called a transition . In this case, there are 2 transitions from A [i] - to A [i-1] and to A [i-2]. The number of transitions may vary depending on the task.
But dynamic programming is not just used. Namely, because it can sometimes very significantly reduce the time it takes to solve a problem, which sometimes, with large volumes of input data, can be very critical. And I want to show one such problem that I met at the Zone School Olympics this year. Literally, I don’t remember the condition, but here is the general meaning:
There is a matrix of numbers A of size NxM and number K. Its first row is given - A [1,1] .. A [1, M]. After that, for each element below the first row, the value is defined as the sum of all elements in the triangle above it modulo K. It is required to output the last row of this matrix A [N, 1] .. A [N, M]. Limitations: 1 ≤ N, M ≤ 2000; 2 ≤ K ≤ 10 9 .
So, in order to know the value of the elements in any line, we need to know the values of the elements in all lines above it. The simplest solution that comes to mind is for each element to simply take and go through all the elements in the triangle above it, counting the sum. Yes, this can be done when time is not critical or when the restrictions on N and M are small, because such an algorithm works for the asymptotics of order O (N 4) (if we take N = M). Those. even with N = M = 100 it will work on the order of 5-10 seconds (depends on the computer), I am already silent about N = M = 2000. So, we need to speed up this business somehow. And let's do this. We have a triangle that needs to be counted. And we have pre-calculated triangles for all the elements above it. So let's make a new triangle using the ones already calculated! We look at the picture:
i.e. if we need to calculate a triangle with a beginning in A [i, j], then it will be calculated by the formula:
A [i, j] = (A [i-1, j] + 2 * A [i-1, j-1 ] + 2 * A [i-1, j + 1] -2 * A [i-2, j]) mod K. (where mod K - take modulo K)
We subtract the triangle A [i-2, j] since this is the intersection region of two triangles A [i-1, j-1] and A [i-1, j + 1], otherwise we would count it 2 times. By the way, think for yourself why we multiply by 2 some values.
The general idea of this task is this. Try to write its solution yourself (there are several nuances in it that I suggest you find for yourself) and test it using the usual brute force algorithm on different tests. If something is not clear - please contact, I will try to help, although I must admit that I myself am not a pro in this matter and I can not solve all problems, but I am capable of something ;-)