Динамическое программирование
автор: Лосева Ирина Алексеевна Довольно часто на олимпиадах по информатике встречаются задачи, провоцирующие к применению алгоритмы перебора. Но простой подсчет числа вариантов убеждает в неэффективности такого подхода. Для решения таких задач используется метод динамического программирования. Суть его заключается в том, что для отыскания решения поставленной задачи решается похожая, но более простая. При этом осуществляется переход к еще более простым и так далее, пока не доходят до тривиальной. Метод решения, описанный выше или ему подобный, скорее всего, будет эффективным, если задача удовлетворяет всем следующим условиям.
- В задаче можно разумно выделить подзадачи аналогичной структуры меньшего размера. Иногда бывает, что исходящая задача не является одной из задач серии, но ее можно легко решить, опираясь на решения одной или нескольких задач серии.
- Среди выделенных подзадач есть тривиальные, т.е. имеющие «малый размер» и очевидное решение.
- Оптимальное решение подзадачи большего размера можно построить из оптимальных решений подзадач (классическая формулировка: у оптимально решенной задачи все подзадачи решены оптимально).
- При решении различных подзадач приходится многократно решать одни и те же (нетривиальные) подзадачи меньшего размера (подзадачи прерываются). Действительно, только при этих условиях есть смысл запоминать какие-либо промежуточные результаты.
- Таблицы для запоминания ответов подзадач имеют разумные, не слишком большие, размеры.
Описанный метод решения задач называют динамическим программированием, применением принципа оптимальности (принцип Беллмана) илитабличной техникой динамического программирования. Под словом «программирование» здесь не имеется в виду процесс составления компьютерных программ. «Динамическое программирование» – короткое и общепринятое название этого метода.
Из предыдущего рассуждения видно, что решение можно оформить рекурсивно. Но простое применение этого приема очень легко может привести к переполнению стека. Необходимо позаботится об оптимизации рекурсивных проходов и не вычислять одно и тоже значение несколько раз, сделать так называемое отсечение. Можно вообще отказаться от рекурсии и решать задачу «наоборот» –– прежде «решить» тривиальные случаи, а затем переходить ко все более сложным.
Конкретные задачи, рассмотренные ниже, вполне могут сформировать (хотя бы на интуитивном уровне) идеи, лежащие в основе решения задач данного класса.
Черепашка На квадратной доске расставлены целые неотрицательные числа. Черепашка, находящаяся в левом верхнем углу, мечтает попасть в правый нижний. При этом она может переползать только в клетку справа или снизу и хочет, чтобы сумма всех чисел, оказавшихся у нее на пути, была бы максимальной.
Определить эту сумму.Формат входных данных Первая строка - N размер доски.
Далее следует N строк, каждая из которых содержит N целых чисел, представляющих доску.Формат выходных данных Одно число –– максимальная сумма. Эта задача является классикой динамического программирования. Ни одно печатное или электронное пособие по решению задач не обходится без разбора «Черепашки». Рассмотреть все возможные маршруты и просчитать их невозможно. Но можно свести задачу к аналогичной. Пусть нам известен «максимальный» путь для всех клеток, кроме правой нижней (функция F (X, Y)). Все нужные маршруты проходят через одну из клеток, смежных с этим углом (их всего две). Максимальный же маршрут проходит через ту клетку из двух, для которой значение функции F больше. Остается только правильно выполнить отсечение: Function F (x, y: integer) : longint;
Begin
If B [x, y] = -1 then
If F(x-1, y) > F(x, y-1)
Then B [x, y]: = F(x-1, y) + A[x, y]
Else B [x, y]: = F(x, y-1) + A[x, y];
F : = B [x, y]
End; Теперь необходимо подумать о граничных условиях. Логически правильнее было бы посчитать нашу функцию для левой и верхней границы. Это делается легко, так как для этих клеток существует только один маршрут (непосредственно вдоль границы). Но еще проще ввести в рассмотрение фиктивные нулевые строку и столбец и присвоить им нулевые значения. Действительно, эти клетки, в принципе, недостижимы, поэтому максимальная сумма равна нулю.
Итеративное заполнение массива также довольно просто. После введения граничных условий (любых из рассматриваемых выше) дальнейшее заполнение осуществляется двойным циклом: For i: =1 to N do
For j: =1 to N do
If B [i-1, j] >B[i,j-1]
Then B[i, j] : = B [i-1, j] + A[i, j]
Else B[i, j] : = B[i,j-1] + A[i, j]; Гвоздики На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.Формат входных данных В первой строке входного файла записано число N - количество гвоздиков (1 <= N <= 100). В следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).Формат выходных данных В выходной файл нужно вывести единственное число - минимальную суммарную длину всех ниточек.
Пример | input.txt | output.txt | 5
4 10 0 12 2 | 6 |
Сначала отсортируем гвоздики по возрастанию координат. Решим следующую подзадачу: найдем минимальную длину веревочек, необходимую для того, чтобы связать первые k гвоздиков согласно условию (обозначим требующуюся для этого длину веревочек ak).
Можно считать, что любая ниточка связывает два соседних гвоздика (иначе ее можно разрезать на несколько частей, связывающих все гвоздики между теми, которые связывала наша ниточка изначально).
Научимся вычислять ak. Заметим, что в оптимальной конфигурации (для первых k гвоздиков) между последним (k-m) и предпоследним ((k-1)-m)гвоздиками ниточка есть всегда, а вот между предпоследним ((k-1)-m) и предпредпоследним ((k-2)-m) она может либо быть, либо не быть. В первом случае первые k-1 гвоздиков удовлетворяют условию задачи, во втором - первые k-2. Значит ak=min(ak-1,ak-2)+lk-1,k, где lk-1,k - расстояние между k-m иk-1-м гвоздиками (в отсортированном массиве). Для удобства вычислений удобно ввести фиктивные первый и нулевой элементы равные 0 и бесконечности соответственно (в реальной программе в роли бесконечности обычно выступает какое-нибудь достаточно большое число, например для данной задачи вполне подойдет 30000). Теперь последовательно заполняя массив a с помощью данной формулы, мы получим верный ответ на поставленную задачу в элементе aN.
Число действий, выполненных данным алгоритмом, пропорционально N.
Лесенки Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков меньше, чем предыдущий.
---
| |
---------
| | | | |
-----------
| | | | | |
-----------------
| | | | | | | | |
-----------------
Подсчитать число лесенок, которое можно построить из N кубиков.
Формат входных данных Во входном файле записано число N (1 <= N <= 100).
Формат выходных данных В выходной файл вывести искомое число лесенок.
Пример Переформулируем нашу задачу на язык математики. В каждом следующем слое (считая сверху вниз) кубиков больше, чем в предыдущем, а в сумме их n. Значит, нам требуется представить n в виде суммы возрастающих натуральных слагаемых.
---
1 | |
---------
4 | | | | |
-----------
5 | | | | | |
-----------------
8 | | | | | | | | |
-----------------
n=1+4+5+8
Пусть в качестве первого слагаемого мы взяли L, тогда нам требуется n-L разбить на слагаемые. Но теперь добавляется дополнительное условие - слагаемые должны быть больше либо равны L+1. Значит, нам достаточно научиться считать число разбиений числа n на слагаемые не меньшие k(обозначим an, k). Есть два случая: слагаемое k либо входит в разбиение (таких способов an-k, k+1), либо нет (таких способов an, k+1). Так как никакое разбиение не подходит одновременно под оба эти случая, то an,k=an-k, k+1 + an, k+1. Заметим, что для единицы существует единственное разбиение: 1 = 1. Значит a1, 0 = a1, 1 = 1, a1, f = 0, где f >= 2. an, k удобно вычислять в порядке невозрастания k. При равных k - в произвольном порядке.
Данный алгоритм выполняет порядка N2 действий.
Эксперимент Результат эксперимента представляет из себя матрицу из 0 < N <= 1000 строк и 0 < M <= 1000 столбцов, заполненную целыми числами по модулю не превосходящими 103. Отвечающим условиям эксперимента считаются такие подматрицы размера K строк и L столбцов (0 < K < N, 0 < L < M), что сумма элементов в каждой из них в точности равна заданному числу S.
Требуется определить, сколько подматриц в исходной матрице отвечают условиям эксперимента.
Например, в матрице 3*3, состоящий из единиц, подматрицы размера 2*2 с суммой 4 встречаются 4 раза.
Входные данные: В первой строке стандартного потока ввода находятся 5 чисел N, M, K, L и S, разделенные пробелами. В каждой из следующих N строк находится поM чисел, разделенных пробелами, являющихся элементами матрицы (целые числа, по модулю не превосходящие 30000 [здесь, возможно, опечатка, т.к. в описании сказано, что каждый элемент не превосходит 1000. М.Г.]).
Выходные данные: В выходной поток записывается одно число - количество подматриц размера K*L, сумма элементов в которых равна S.
Пример: Входные данные:
3 3 2 2 4
1 1 1
1 1 1
1 1 1
Результат:
4
Несложно понять, что для решения этой задачи используется динамическое программирование. Действительно, будем использовать дополнительную матрицу такого же размера, в каждом элементе которой будем хранить сумму всех элементов, лежащих не ниже и не правее данного. Пусть A - исходная матрица, B - преобразованная (она может совпадать с A, как мы увидим в дальнейшем элементы матрицы A не понадобятся нигде, кроме как при составлении матрицы B).
Тогда B[x,y] = sum[i=1,x](sum[j=1,y](A[i,j])).
Чтобы ускорить процесс воспользуемся тем, что B[x,y] = A[x,y] + B[x-1,y] + B[x,y-1] - B[x-1,y-1]. Для облегчения подсчетов, создадим "барьер" вокруг матрицы B, шириной 1 и заполненный нулями (т.е. создадим нулевые строку и столбец в матрице B и заполним их нулями). Теперь у нас есть матрица B, в которой хранятся суммы. Допустим, мы хотим проверить, является ли точка (x,y) - верхним левым краем искомой подматрицы. Если это так, то должно выполняться условие: B[x,y] + B[x+K,y+L] - B[x,y+L], - B[x+K,y] = S. Теперь достаточно пройти циклом по всем возможным правым углам подматриц и определить, сколько из них удовлетворяют условию.
Робот В исследовательской лаборатории фирмы Robot&Co разработали новую модель робота. Главной особенностью данной модели робота является то, что он работает по заранее заданной программе, в которой могут присутствовать команды: сделать шаг на Юг, на Север, на Восток или на Запад. Робот исполняет программу строго последовательно и, дойдя до конца программы, останавливается. Специалисты из Robot&Co заинтересовались вопросом, сколько существует различных программ, состоящих из К инструкций, таких, что робот, выйдя из начала координат, придет в точку с координатами ( X, Y). Оси координат располагаются параллельно сторонам света, и единица измерения, соответствует одному шагу робота. Напишите программу, которая дает ответ на этот вопрос.
Формат входных данных Во входном файле находятся три числа K ,X иY ( 0<= K<=16, | X |,| Y|<=16), разделенные пробелами.
Формат выходных данных В выходной файл ваша программа должна поместить одно число –– количество программ для робота.
В этой задаче мы впервые сталкиваемся с функцией трех переменных: F(X, Y, Z) – показывает количество маршрутов длины Z, приводящее в клетку( X, Y). К сожалению, такая структура данных как
Array [ - 16.. 16, - 16..16, 0.. 16] of Longint;
в память не помещается. Забудем пока об этой трудности и напишем рекурсивную часть. Для ответа на поставленный в задаче вопрос можно посчитать число маршрутов длины Z-1 в четыре клетки, смежных с заданной, а результаты сложить, не забывая случаи клеток на границе. Граничными условия будут F(X, Y, 0) = 0, если хотя бы одна из координат X или Y отлична от нуля, и F(0,0,0) = 1. Действительно, если робота не двигать, то он может оказаться только в начале координат. Теперь вспомним о проблеме хранения данных. Выхода существует два. Первый, чисто программистский, заключается в разбиении большой структуры на несколько меньших и размещении их в динамической памяти. Сделать это можно, например, так
Type T 1 = array [- 16.. 16, - 16..16] of Longint;
T2 = array [0.. 16] of ^ T 1;
Var D: T2;
Тогда наша функция будет записана так (предполагается, что память выделена, граничные условия введены, а для не вычисленных значений функции в массиве хранится «- 1»):
Function F (X: integer) : longint;
Var s : longint;
Begin
If D [Z]^[X,Y] = -1 then
Begin
S: = 0;
If X< > -16 then S:= s+ F (X-1, Y, Z-1);
If X< > 16 then S: = s+ F (X+1,Y, Z-1);
If Y< > -16 then S: = s+ F (X, Y-1, Z-1);
If Y< > 16 then S: = s+ F (X, Y+1, Z-1);
D [Z]^[X,Y] = s
End;
F: = D [Z]^[X,Y]
End; Это, конечно, решение, но оно далеко не оптимальное (сточки зрения расходования памяти). Действительно, для вычислений в некий момент времени необходимы данные только за предыдущий, что же происходило ранее, нас не интересует – с этим мы уже справились. Значит, достаточно хранить только 2 квадратные матрицы размером 31, - одна несет данные в предыдущий момент времени, а вторая вычисляется для текущего с использованием первой матрицы. После окончания расчета данные первой уже не нужны, ей присваиваем значение второй матрицы. После окончания расчета данные первой уже не нужны, ей присваиваем значение второй матрицы, увеличиваем счетчик времени и т. д
Ясно, что такую идею можно реализовать только итеративно.
For z : =1 to k do
Begin
Way2: = Way1
For i : =-16 to 16 do
For J : =-16 to 16 do
Begin
S: = 0;
If I < > -16 then S: = s+ Way2 [i-1, j];
If I < > 16 then S: = s+ Way2 [i+1, j];
If J< > -16 then S: = s+ Way2 [i, j-1];
If J< > 16 then S: = s+ Way2 [i, j+1];
Way1[i, j] : = s
End;
End; Интересно, что итеративное решение на некоторых тестах работает несколько дольше рекурсивного. Это становится понятным, если учесть, что в итеративной форме мы подсчитываем количества всевозможных маршрутов, а в рекурсивном делаем только то, что нас просят.
|
