Сразу оговорюсь - данная статья не претендует на полноту освещения этой темы программирования. Скорее это просто мое понимание. Литературы об этом, кажется, немного (или я плохо искал?..), поэтому я решил написать некую сборную статью, в которую вложу понемногу из того, что понаходил во многих местах и постараюсь снабдить достаточным кол-вом примеров.
Ну да ладно, приступим собственно к теме статьи :)
(Возможно что-то будет сразу непонятно дочитайте до примеров, не поленитесь, возможно станет понятнее)
В типичном случае динамическое программирование применяется к задачам оптимизации, которые не решаются простым перебором (из-за временных ограничений или слишком большого объема необходимой памяти) и жадными алгоритмами (из-за того, что они не дают оптимального результата), а более простой путь решения если и существует, то его нахождение неочевидно. У таких задач может быть много решений и в общем случае это определяет некий показатель (назовем его качеством решения), и требуется выбрать оптимальное, при котором данный показатель становится либо минимумом либо максимумом (или еще чем-то :) - в зависимости от условия задачи).
По своему принципу динамическое программирование напоминает метод разделяй и властвуй задача делится на подзадачи, которые либо являются очевидными, либо сводятся к своим подзадачам и т.д. Но есть и некоторые отличия например, таких подзадач обычно относительно немного, что позволяет решить каждую только один раз, а результат (то самое качество) занести в некий массив такой подход называется memoization (не бейте меня, это не я такое придумал! :))).
Небольшое кол-во подзадач, многие из которых приходится решать много раз называется перекрытием подзадач и является характерным признаком динамического программирования.
Вторым характерным признаком излагаемого метода является оптимальность для подзадач. Говорят, что задача обладает таким свойством, если оптимальное решение задачи содержит оптимальные решения ее подзадач.
Общий рецепт построения алгоритмов по принципу динамического программирования следующий:
* Хорошо понять условие :)
* Найти такое разбиение задачи на две или более подзадач, чтобы оптимальное решение задачи содержало оптимальное решение всех подзадач, которые в нее входят.
* Написать рекуррентное соотношение (если мы разбиваем задачу на подзадачи, значит, можем выразить качество решения задачи либо через ее подзадачи, либо элементарным образом)
* Вычислить оптимальное значение параметра для всей задачи. Тут возможно два варианта если задачу решаем рекурсивно, значит процедура делит заданную ей задачу на подзадачи (предварительно выяснив, не является ли задача тривиальной и проверив, не решалась ли она ранее тогда нужно лишь взять уже готовое решение из соответствующего массива) и получив решение ставит флаг, что эта подзадача уже решена. Такое решение называется решением сверху вниз т.е. берем глобальную задачу, потом решаем только необходимые для нее подзадачи. Если же рекурсия невозможна по техническим или еще каким-нить причинам (может просто не любит какой программер рекурсию :)), то применяется такой подход: решаются сначала элементарные подзадачи, потом только те, которые требуют результатов уже решенных подзадач и т. д., пока не будет решена общая задача. Такой метод называется решением снизу вверх в большинстве случаев он оказывается быстрее, но менее понятным и простым, хотя есть и исключения
* Если необходимо получить не только значение качества оптимального решения, но и найти само решение, то на шаге 3 нужно также запоминать некоторую дополнительную информацию о ходе решения решение каждой подзадачи. Этот шаг иногда еще называют обратным ходом.
Так общий подход я изложил, теперь перейду к примерам (Самое лучшее изложение динамического программирования я нашел в книге Т.Кормена, Ч.Лейзерсона и Р.Ривеста Алгоритмы: построение и анализ. Там же взята примерно половина материала и примеры о матрицах и НОП. В книге, конечно, почитать лучше, но для полноты я вкратце привел и их мне почему-то кажется, что не у всех есть эта классная книга :( )
ПРИМЕР 1. Перемножение матриц
Задача о перемножении матриц формулируется следующим образом: дана последовательность из n матриц (А1, А2, , Аn) заданных размеров (матрица i имеет размеры pi-1 x pi); требуется найти такую полную расстановку скобок в произведении А1А2А3Аn, чтобы количество умножений было минимально возможным (далее кол-во умножений еще называется стоимостью т.е. это именно тот параметр, который в данной задаче необходимо минимизировать).
Будем говорить, что в произведении полностью расставлены скобки, если это произведение состоит из единственной матрицы, либо является заключенным в скобки произведением двух произведений с полностью расставленными скобками.
Так как произведение матриц ассоциативно [A(BC)=(AB)C], то расстановка скобок не повлияет на результат, но может существенно повлиять на кол-во умножений. Для начала неплохо было бы убедиться в том, что полный перебор всех возможных вариантов не даст эффективного алгоритма: действительно, в каждой тройке матриц можно расставить скобки двумя вариантами, а значит в 3n матриц можно расставить скобки не менее, чем 2n вариантами, т.е. кол-во вариантов (а следовательно и время работы программы, перебирающей все варианты) экспоненциально зависит от n.
(Строго говоря количество вариантов - более подробно см. в вышеупомянутой книге)
Значит, можно со спокойной совестью разбираться с динамическим программированием
Шаг 1. найти разбиение задачи на подзадачи
Обозначим через Аi..j матрицу, являющуюся произведением матриц АiAi+1Aj. Допустим, что последнее произведение матриц при оптимальной расстановке скобок в произведении A1A2An производится между матрицами A1..k и Ak+1...n. Иными словами, при перемножении, диктуемом такой расстановкой скобок мы сначала вычисляем произведение A1..k, потом Ak+1..n и наконец, вычисляем их произведение. Значит стоимость этой оптимальной расстановки равна стоимости вычисления каждой из этих двух матриц плюс стоимость их перемножения.
(Тут немного отклонюсь от темы. Я некоторое время не мог понять свойства оптимальности для подзадач: если задача содержит оптимальные решения подзадач, то почему нельзя просто применить жадный алгоритм? Объясняется это вот как: жадный алгоритм выбирает из всех возможных подзадач ту, которая решается легче всего. Но этой подзадачи (которую выберет жадный алгоритм) может просто не быть в оптимальном решении всей задачи! Например, возьмем произведение трех матриц А1*А2*А3 размерами 10*4, 4*2, 2*5 соответственно. Стоимость произведения А1А2 равна 80, а стоимость произведения А2А3 равна 40. Т.е. жадный алгоритм выберет расстановку скобок А1(А2А3), стоимость которой на самом деле 240 вместо (А1А2)А3, стоимость которой 180. Это произошло потому, что подзадачи А2А3 вообще нет в оптимальном решении. А оптимальность для подзадач на этом примере означает не то, что мы на каждом шаге выбираем самое дешевое (как известно, оно далеко не всегда лучшее...), а что произведение в скобках (А1А2) также вычислено оптимальным образом. Для задачи расстановки скобок в произведении матриц это свойство можно сформулировать так: любое произведение, заключенное в скобки вычисляется оптимальным образом)
Так как способ вычисления матриц A1..k и Ak+1...n не влияет на результат, то чем меньше стоимость вычисления этих матриц, тем меньше стоимость всех умножений. Т.е. оптимальное решение задачи включает в себя оптимальное решение подзадачи, что и позволяет применить динамическое программирование.
Таким образом, мы разбили всю задачу на подзадачи вычисление стоимости матриц Аi..j.
Шаг 2. Написать рекуррентное соотношение
Замечу, что соотношение тут будет рекуррентным вне зависимости от того, как реализована сама программа итеративно или рекурсивно.
Обозначим через m[i, j] минимальную стоимость вычисления матрицы Ai..j. Элементарным случаем тогда будет i=j, т.е. Аi..j=Ai и умножения вообще не нужны, следовательно стоимость равна 0.
Случай:
Тогда:
В этом равенстве подразумевается, что лучшее значение k нам известно. В действительности его еще нужно найти. Тут единственным вариантом является перебор всех значений k в промежутке от i до j-1. Т.е. окончательно получаем:
Шаг 3. Вычислить оптимальное значение для всей задачи.
Пользуясь соотношением, полученным на шаге 2, легко написать рекурсивный алгоритм, вычисляющий оптимальное значение для всей задачи. Однако такой алгоритм будет работать экспоненциальное время. Настоящий выигрыш получается, когда промежуточные значения m[i, j] вычислять лишь по одному разу и заносить в массив.
Ниже приводится как рекурсивный, так и итеративный решения. (Для итеративного нужно было заметить, что для вычисления произведения l последовательных матриц AiAi+1Al необходимо знать лишь стоимости произведения меньшего, чем l кол-ва матриц, что и показывает соотношение из п. 2. Это и использует алгоритм, вычисляя последовательно стоимости произведения l=2, 3 n матриц)
Рекурсивный алгоритм:
Код:
Function GetM(i, j: integer):longint;
var k:integer;
res:longint;
begin
if m[i, j]<>-1 then { "-1"-ми изначально должен быть заполнен
весь массив m, кроме главной диагонали,
где 0, т.к. m[i, i]=0 }
begin
GetM:=m[i, j];
exit;
end;
res:=GetM(i+1, j) + p[i-1]*p[i]*p[j]; { для нахождения
минимума изначально инициализируем первым
возможным значением k=i [GetM(i, i)=0] }
s[i, j]:=i;
for k:=i+1 to j-1 do
if res>GetM(i, k) + GetM(k+1, j) + p[i-1]*p[k]*p[j] then
begin
res:= GetM(i, k) + GetM(k+1, j) + p[i-1]*p[k]*p[j];
s[i, j]:=k;
end;
GetM:=res;
m[i, j]:=res;
end;
Итеративный алгоритм:
Код:
....
for i:=1 to n do m[i, j]:=0; { тут можно и "0"-ми сразу заполнять, чтобы
не трудиться проверять еще, главная это диагональ или нет }
for l:=2 to n do { кол-во сомножителей, которое рассчитываем }
for i:=1 to n-l+1 do begin
j:=i+l-1;
m[i, j]:= m[i+1, j] + p[i-1]*p[i]*p[j]; { сунули туды первое
значение и ищем минимум }
s[i, j]:=i;
for k:=i+1 to j-1 do
if m[i, j] m[i, k] + m[k+1, j] + p[i-1]*p[k]*p[j] then
begin
m[i, j]:= m[i, k] + m[k+1, j] + p[i-1]*p[k]*p[j];
s[i, j]:=k;
end;
end;
....
Шаг 4. Построение оптимального решения...
(именно самого решения, а не его стоимости!)
Думаю, что все заметили некую жутко таинственную матрицу c, про которую нету ни слова... :)) В ней сохраняется выбор, который дал оптимум для подзадачи i..j. Вот именно по нему и будем восстанавливать все решение. Алгоритм достаточно очевиден, поэтому много комментировать не буду...
Код:
procedure PrintSolution(i, j:integer);
begin
if i=j then
write(A, i)
else
begin
write(();
PrintSolution(i, s[i, j]);
write(*);
PrintSolution(s[i, j]+1, j);
write());
end;
end;
Такс.. ну первый пример я расписал подробно, а эти буду только вкратце идею решения кидать... :)
ПРИМЕР 2. Наибольшая общая подпоследовательность
Последовательность Z=(z1, z2, ... , zk) называется подпоследовательностью последовательности X=(x1, x2, ... , xn) если существует последовательность индексов i1i2...ik, такая, что [i]. Говорят, что Z является общей подпоследовательностю последовательностей X и Y, если она есть подпоследовательностью как X, так и Y.
Задача о наибольшей общей подпоследовательности (сокращенно НОП) формулируется так: найти одну из общих подпоследовательностей последовательностей X и Y наибольшей длины.
Так как любая последовательность длины n имеет 2n подпоследовательностей, то очевидно, полный перебор всех возможных подпоследовательностей не даст эффективного алгоритма.
Шаг 1. Нахождение подходящих подзадач
Назовем префиксом последовательности X длины i последовательность Xi=(x1, x2, ... , xi). X0 в таком случае будет пустая последовательность. Сформулируем принцип строения НОП, из которого будет очевидно рекуррентное соотношение: пусть Z=(z1, z2, ... , zk) - одна из наибольших общих подпоследовательностей для последовательностей X=(x1, x2, ... , xm) и Y=(y1, y2, ... , yn). Тогда:
* если xm=yn, то zk=xm=yn и Zk-1 является НОП для Xm-1 и Yn-1
* если xm?yn и zk?xm, то Z является НОП для Xm-1 и Y
* если xm?yn и zk?yn, то Z является НОП для X и Yn-1
Доказательство, в принципе, очевидно... :)
Легко видеть (черт, как меня эта фраза обычно раздражает вот теперь и я хоть кого-то пораздражаю, а то все меня да меня :)))), что НОП двух последовательностей содержит в себе НОП их префиксов, а следовательно, задача о НОП обладает свойством оптимальности для подзадач. Их перекрытие также имеет место, как будет ясно из рекурретной формулы.
Шаг 2. Рекуррентное соотношение
Пусть c[i, j] длина НОП для последовательностей Xi и Yj. Тогда исходя из рассуждений, проведенных на шаге 1:
Понять эту формулу несложно, поэтому распространяться много не буду... :)
Шаг 3. Вычисление длины наибольшей НОП
Смотря на вышеприведенную формулу, можно заметить, что c[i, j( может требовать для вычисления только те с[a, b(, которые выше и/или левее него (a<=i, b<=j), а значит, заполняя массив сверху вниз строчка за строчкой и слева направо мы не встретим ни одного непросчитанного элемента. Данный факт просто "убивает" рекурсивный вариант этой программы - он будет жрать больше памяти и медленнее работать, да и понимать его сложнее...
Остается итеративный:
Код:
...
for i:=1 to m do c[i, 0]:=0;
for i:=1 to n do c[0, i]:=0;
for i:=1 to m do
for j:=1 to n do
if x[i]=y[j] then
c[i, j]:=c[i-1, j-1] + 1
else
if c[i-1, j]=c[i, j-1] then
c[i, j]:=c[i-1, j]
else
c[i, j]:=c[i, j-1];
...
Шаг 4. Построение оптимального решения
Я его строить не буду попробуйте сами. Ну, а те, кто гиперленивы, как я найдите книгу и посмотрите... :)
Фуууххх... :) я так подумал, сколько времени на все это уходит больше не дам примеров... ну разве, что если очень нужно будет... :)
А задач еще пару подкину
(кстати говоря, про задачи два примера выше далеко не простейшие, так что если все там ясно, то первые несколько задач можно пропустить они попроще. И еще: не удивляйтесь идиотизму задач в большинстве своем они взяты из олимпиад по программированию, а там все такие :))))):
1. Черепашка
(классика уже :) )
На квадратной доске расставлены целые неотрицательные числа. Черепашка, находящаяся в левом верхнем углу, мечтает попасть в правый нижний. При этом она может переползать только в клетку справа или снизу и хочет, чтобы сумма всех чисел, оказавшихся у нее на пути, была бы максимальной. Определить эту сумму.
2. Робот
В исследовательской лаборатории фирмы Robots&Co разработали новую модель робота. Главной особенностью данной модели робота является то, что он работает по заранее заданной программе, в которой могут присутствовать команды: сделать шаг на Юг, на Север, на Восток или на Запад. Робот исполняет программу строго последовательно и, дойдя до конца программы, останавливается. Специалисты из Robots&Co заинтересовались вопросом, сколько существует различных программ, состоящих из K инструкций, таких, что робот, выйдя из начала координат, придет в точку с координатами (X, Y). Оси координат располагаются параллельно сторонам света, и единица измерения, соответствует одному шагу робота. Напишите программу, которая дает ответ на этот вопрос
3. Взрывоопасность
При переработке радиоактивных материалов образуются отходы двух видов - особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры, последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более двух контейнеров типа A. Для заданного количества контейнеров N определить число безопасных стопок.
4. Игра обезьян
В игру играют 2 обезьяны. Изначально на столе находится L бананов. За свой ход первая обезьяна может взять ai бананов, где i=1, 2,...k, причем a1<a2<...<ak, а вторая обезьяна за свой ход может взять соответственно b1, b2, ... bm бананов (опять-таки b1<b2<...<bm). Выигрывает та мартышка, которая НЕ сможет на своем ходу взять бананы (т.е. если число оставшихся к данному ходу бананов обозначить l, то условие выигрыша первой l<a1, а второй l<b1). Определить может ли выиграть первая обезьяна, если она начинает ходить и вторая обезьяна будет ходить оптимально.
Примечание: довольно интересная задача, есть над чем подумать... из-за того, что обезьяны 2, возникают небольшие трудности. Но рассказывать не хочу... :)
5. К-ичные числа
Требуется вычислить количество N-значных чисел в системе счисления с основанием K, таких что их запись не содержит двух подряд идущих нулей.
6. Разбиение абзаца на строки
Абзац текста состоит из n слов текста длиной l1, l2, ... , ln соответственно. Считая, что все символы имеют равную ширину, необходимо оптимальным образом разбить абзац на строки шириной не более M символов. Оптимальность при этом определяется так: посчитаем число лишних пробелов в каждой строке (то есть посмотрим, на сколько длина строки меньше М) и сложим кубы этих чисел для всех строк, кроме последней: чем больше эта сумма, тем хуже абзац.
Примечание: эта задача почти аналогична задаче о перемножении матриц, только несколько усложнена. Кстати не забудьте про подвох: между словами посредине строки еще должен быть пробел, а в конце строки его быть не должно... радуйтесь! :)
7. Палиндром
Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH. Напишите программу, находящую в данной строке подпалиндром максимальной длины.
8. Паровозики
N локомотивов, имеющих номера от 1 до N и установленных на железнодорожную колею, начинают двигаться в одну сторону, причем локомотив номер k изначально движется со скоростью k км/ч. Если локомотив, движущийся с большей скоростью, нагоняет более медленный локомотив, дальше они движутся один за другим со скоростью впереди идущего локомотива. Очевидно, через некоторое время после начала движения локомотивы разобьются на несколько групп, движущихся с разной скоростью. Написать программу, определяющую, сколько начальных расстановок s из N! Возможных дадут в результате p групп движущихся локомотивов.
9. Плитки
У Пети имеется неограниченный набор красных, синих и зеленых плиток размером 1 * 1. Он выбирает ровно N плиток и выкладывает их в полоску. Например, при N = 10 она может выглядеть следующим образом:
Код:
К К К С З К К З К С
(буквой К обозначена красная плитка, С - синяя, З - зеленая).
После этого Петя заполняет следующую таблицу:
Красный Синий Зеленый
Красный Y Y Y
Синий Y N Y
Зеленый Y Y N
В клетке на пересечении строки, отвечающей цвету А, и столбца, отвечающего цвету Б, он записывает "Y", если в его полоске найдется место, где рядом лежат плитки цветов А и Б и "N" в противном случае. Считается, что плитки лежат рядом, если у них есть общая сторона. (Очевидно, что таблица симметрична относительно главной диагонали - если плитки цветов А и Б лежали рядом, то рядом лежали и плитки цветов Б и А.)
Назовем такую таблицу диаграммой смежности данной полоски.
Так, данная таблица представляет собой диаграмму смежности приведенной выше полоски. Петя хочет узнать, сколько различных полосок имеет определенную диаграмму смежности. Помогите ему.
(Заметьте, что полоски, являющиеся отражением друг друга, но не совпадающие, считаются разными. Так, полоска
Код:
С К З К К З С К К К
не совпадает с полоской, приведенной в начале условия.)
Скачать примеры к статье можно здесь.
автор: VaN