Динамическое программирование для начинающих

Самый дешёвый путь

В каждой клетке прямоугольной таблицы N*M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).

Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол.

Динамическое программирование (иначе «динамическое планирование») есть особый метод оптимизации решений, специально приспособленный к так называемым «многошаговым» (или «многоэтапным») операциям.

Представим себе некоторую операцию О, распадающуюся на ряд последовательных «шагов» или «этапов», - например, деятельность отрасли промышленности в течение ряда хозяйственных лет; или же преодоление группой самолетов нескольких полос противовоздушной обороны; или последовательность тестов, применяемых при контроле аппаратуры. Некоторые операции (подобно вышеприведенным) расчленяются на шаги естественно; в некоторых членение приходится вводить искусственно - скажем, процесс наведения ракеты на цель можно условно разбить на этапы, каждый из которых занимает какое-то время

Итак, рассмотрим операцию О, состоящую из шагов (этапов). Пусть эффективность операции характеризуется каким-то показателем W, который мы для краткости будем в этой главе называть «выигрышем». Предположим, что выигрыш W за всю операцию складывается из выигрышей на отдельных шагах:

где - выигрыш на i-м шаге.

Если W обладает таким свойством, то его называют аддитивным критерием .

Операция О, о которой идет речь, представляет собой управляемый процесс, т. е. мы можем выбирать какие-то параметры, влияющие на его ход и исход, причем на каждом шаге выбирается какое-то решение, от которого зависит выигрыш на данном шаге и выигрыш за операцию в целом. Будем называть это решение «шаговым управлением». Совокупность всех шаговых управлений представляет собой управление операцией в целом. Обозначим его буквой , а шаговые управления - буквами :

Следует иметь в виду, что в общем случае - не числа, а, может быть, векторы, функции и т. д.

Требуется найти такое управление при котором выигрыш W обращается в максимум:

То управление при котором этот максимум достигается, будем называть оптимальным управлением. Оно состоит из совокупности оптимальных шаговых управлений:

Тот максимальный выигрыш, который достигается при этом управлении, мы будем обозначать :

Формула (12.5) читается так: величина W есть максимум из всех при разных управлениях (максимум берется по всем управлениям возможным в данных условиях). Иногда это последнее оговаривается в формуле и пишут:

Рассмотрим несколько примеров многошаговых операций и для каждого из них поясним, что понимается под «управлением» и каков «выигрыш» (показатель эффективности)

1. Планируется деятельность группы промышленных предприятий на период хозяйственных лет (-летку). В начале периода на развитие группы выделены какие-то средства которые должны быть как-то распределены между предприятиями. В процессе работы предприятия вложенные в него средства частично расходуются (амортизируются), а частично сохраняются и снова могут быть перераспределены. Каждое предприятие за год приносит доход, зависящий от того, сколько средств в него вложено. В начале каждого хозяйственного года имеющиеся в наличии средства перераспределяются между предприятиями. Ставится вопрос: какое количество средств в начале каждого года нужно выделять каждому предприятию, чтобы суммарный доход за лет был максимальным?

Выигрыш W (суммарный доход) представляет собой сумму доходов на отдельных шагах (годах):

значит, обладает свойством аддитивности.

Управление на шаге состоит в том, что в начале года предприятиям выделяются какие-то средства (первый индекс - номер шага, второй - номер предприятия). Таким образом, шаговое управление есть вектор с к составляющими:

Разумеется, величины в формуле (12.6) зависят от количества вложенных в предприятия средств.

Управление всей операцией состоит из совокупности всех шаговых управлений:

Требуется найти такое распределение средств по предприятиям и по годам (оптимальное управление при котором величина W обращается в максимум.

В этом примере шаговые управления были векторами; в последующих примерах они будут проще и выражаться просто числами.

2. Космическая ракета состоит из ступеней, а процесс ее вывода на орбиту - из этапов, в конце каждого из которых очередная ступень сбрасывается. На все ступени (без учета «полезного» веса кабины) выделен какой-то общий вес:

где - вес ступени.

В результате этапа (сгорания и сбрасывания ступени) ракета получает приращение скорости А, зависящее от веса данной ступени и суммарного веса всех оставшихся плюс вес кабины. Спрашивается, как нужно распределить вес G между ступенями, чтобы, скорость ракеты V при ее выводе на орбиту была максимальна?

В данном случае показатель эффективности (выигрыш) будет

где А - выигрыш (приращение скорости) на шаге.

Управление представляет собой совокупность весов всех ступеней

Оптимальным управлением будет то распределение весов по ступеням, при котором скорость V максимальна. В этом примере шаговое управление - одно число, а именно, вес данной ступени.

3. Владелец автомашины эксплуатирует ее в течение лет. В начале каждого года он может принять одно из трех решений:

1) продать машину и заменить ее новой;

2) ремонтировать ее и продолжать эксплуатацию;

3). продолжать эксплуатацию без ремонта.

Шаговое управление - выбор одного из этих трех решений. Непосредственно числами они не выражаются, но можно приписать первому численное значение 1, второму 2, третьему 3. Какие нужно принять решения по годам (т. е. как чередовать управления 1, 2,3), чтобы суммарные расходы на эксплуатацию, ремонт и приобретение новых машин были минимальны?

Показатель эффективности (в данном случае это не «выигрыш», а «проигрыш», но это неважно) равен

(12.10)

где - расходы в i-м году. Величину W требуется обратить в минимум.

что означает: первые два года эксплуатировать машину без ремонта, последующие три года ее ремонтировать, в начале шестого года продать, купить новую, затем снова эксплуатировать без ремонта и т. д. Любое управление представляет собой вектор (совокупность чисел):

где каждое из чисел имеет одно из трех значений: 1, 2 или 3. Нужно выбрать совокупность чисел (12.11), при которой величина (12.10) минимальна.

4. Прокладывается участок железнодорожного пути между пунктами А и В (рис. 12.1).

Местность пересеченная, включает лесистые зоны, холмы, болота, реку, через которую надо строить мост. Требуется так провести дорогу из в В, чтобы суммарные затраты на сооружение участка были минимальны.

В этой задаче, в отличие от трех предыдущих, нет естественного членения на шаги: его приходится вводить искусственно, для чего, например, можно отрезок АВ разделить на частей, провести через точки деления прямые, перпендикулярные АВ, и считать за «шаг» переход с одной такой прямой на другую. Если провести их достаточно близко друг от друга, то можно считать на каждом шаге участок пути прямолинейным. Шаговое управление на i-м шаге представляет собой угол , который составляет участок пути с прямой АВ. Управление всей операцией состоит из совокупности шаговых управлений:

Требуется выбрать такое (оптимальное) управление при котором суммарные затраты на сооружение всех участков минимальны:

(12.12)

Итак, мы рассмотрели несколько примеров многошаговых задач исследования операций. А теперь поговорим о том, как можно решать подобного рода задачи?

Любую многошаговую задачу можно решать по-разному: либо искать сразу все элементы решения на всех шагах, либо же строить оптимальное управление шаг за шагом, на каждом этапе расчета оптимизируя только один шаг. Обычно второй способ оптимизации оказывается проще, чем первый, особенно при большом числе шагов.

Такая идея постепенной, пошаговой оптимизации и лежит в основе метода динамического программирования. Оптимизация одного шага, как правило, проще оптимизации всего процесса: лучше, оказывается, много раз решить сравнительно простую задачу, чем один раз - сложную.

С первого взгляда идея может показаться довольно тривиальной.

В самом деле, чего казалось бы, проще: если трудно оптимизировать операцию в целом, разбить ее на ряд шагов. Каждый такой шаг будет отдельной, маленькой операцией, оптимизировать которую уже нетрудно. Надо выбрать на этом шаге такое управление, чтобы эффективность этого шага была максимальна. Не так ли?

Нет, вовсе не так! Принцип динамического программирования отнюдь не предполагает, что каждый шаг оптимизируется отдельно, независимо от других. Напротив, шаговое управление должно выбираться дальновидно, с учетом всех его последствий в будущем. Что толку, если мы выберем на данном шаге управление, при котором эффективность этого шага максимальна, если этот шаг лишит нас возможности хорошо выиграть на последующих шагах?

Пусть, например, планируется работа группы промышленных предприятий, из которых часть занята выпуском предметов потребления, а остальные производят для них машины. Задача операции - получить за лет максимальный объем выпуска предметов потребления. Допустим, планируются капиталовложения на первый год. Исходя из узких интересов этого шага (года), мы должны были бы все наличные средства вложить в производство предметов потребления. Но правильно ли будет такое решение с точки зрения эффективности операции в целом? Очевидно, нет. Это решение - расточительное, недальновидное. Имея в виду будущее, надо выделить какую-то долю средств и на производство машин. От этого объем продукции за первый год, конечно, снизится, зато будут созданы условия для его увеличения в последующие годы.

Еще пример. Допустим, что в задаче 4 (прокладка железнодорожного пути из А в В) мы прельстимся идеей сразу же устремиться по самому легкому (дешевому) направлению. Что толку от экономии на первом шаге, если в дальнейшем он заведет нас (буквально или фигурально) в «болото»?

Значит, планируя многошаговую операцию, надо выбирать управление на каждом шаге с учетом всех его будущих последствий на еще предстоящих шагах. Управление на шаге выбирается не так, чтобы выигрыш именно на данном шаге был максимален, а так, чтобы была максимальна сумма выигрышей на всех оставшихся до конца шагах плюс данный.

Однако из этого правила есть исключение. Среди всех шагов есть один, который может планироваться попросту, без оглядки на будущее. Какой это шаг? Очевидно, последний! Этот шаг, единственный из всех, можно планировать так, чтобы он сам, как таковой принес наибольшую выгоду.

Поэтому процесс динамического программирования обычно разворачивается от конца к началу: прежде всего планируется последний, шаг. А как его спланировать, если мы не знаем, чем кончился предпоследний? Т. е. не знаем условий, в которых мы приступаем к последнему шагу?

Вот тут-то и начинается самое главное. Планируя последний шаг, нужно сделать разные предположения о том, чем кончился предпоследний, шаг, и для каждого из этих предположений найти условное оптимальное управление на шаге («условное» потому, что оно выбирается исходя из условия, что предпоследний шаг кончился так-то, и так-то).

Предположим, что мы это сделали, и для каждого из возможных исходов предпоследнего шага знаем, условное оптимальное управление и соответствующий ему условный оптимальный выигрыш на шаге. Отлично! Теперь мы можем оптимизировать управление на предпоследнем, шаге. Снова сделаем все возможные предположения о том, чем кончился предыдущий, и найти не условно оптимальный, а просто оптимальный выигрыш .

В самом деле, пусть мы знаем, в каком состоянии была управляемая система (объект управления S) в начале первого шага. Тогда мы можем выбрать оптимальное управление на первом шаге. Применив его, мы изменим состояние системы на некоторое новое S и в этом состоянии мы подошли ко второму шагу. Тогда нам тоже известно условное оптимальное управление которое к концу второго шага переводит систему в состояние и т. д. Что касается оптимального выигрыша W за всю операцию, то он нам уже известен: ведь именно на основе его максимальности мы выбирали управление на первом шаге.

Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс «проходится» дважды: первый раз - от конца к началу, в результате чего находятся условные оптимальные управления и условные оптимальные выигрыши за оставшийся «хвост» процесса; второй раз - от начала к концу, когда нам остается только «прочитать» уже готовые рекомендации и найти безусловное оптимальное управление состоящее из оптимальных шаговых управлений

Первый этап - условной оптимизации - несравненно сложнее и длительнее второго. Второй этап почти не требует дополнительных вычислений.

Автор не льстит себя надеждой, что из такого описания метода динамического программирования читатель, не встречавшийся с ним до сих пор, поймет по-настоящему его идею. Истинное понимание возникает при рассмотрении конкретных примеров, к которым мы и перейдем.

Здравствуй, Хабрахабр. В настоящий момент я работаю над учебным пособием по олимпиадному программированию, один из параграфов которого посвящен динамическому программированию. Ниже приведена выдержка из данного параграфа. Пытаясь объяснить данную тему как можно проще, я постарался сложные моменты сопроводить иллюстрациями. Мне интересно ваше мнение о том, насколько понятным получился данный материал. Также буду рад советам, какие еще задачи стоит включить в данный раздел.

Во многих олимпиадных задачах по программированию решение с помощью рекурсии или полного перебора требует выполнения очень большого числа операций. Попытка решить такие задачи, например, полным перебором, приводит к превышению времени выполнения.

Однако среди переборных и некоторых других задач можно выделить класс задач, обладающих одним хорошим свойством: имея решения некоторых подзадач (например, для меньшего числа n ), можно практически без перебора найти решение исходной задачи.

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.

Последовательности

Последовательность Фибоначчи F n задается формулами: F 1 = 1, F 2 = 1,
F n = F n - 1 + F n - 2 при n > 1. Необходимо найти F n по номеру n .

Один из способов решения, который может показаться логичным и эффективным, — решение с помощью рекурсии:

Int F(int n) { if (n < 2) return 1; else return F(n - 1) + F(n - 2); }
Используя такую функцию, мы будем решать задачу «с конца» — будем шаг за шагом уменьшать n , пока не дойдем до известных значений.

Но как можно заметить, такая, казалось бы, простая программа уже при n = 40 работает заметно долго. Это связано с тем, что одни и те же промежуточные данные вычисляются по несколько раз — число операций нарастает с той же скоростью, с какой растут числа Фибоначчи — экспоненциально.

Один из выходов из данной ситуации — сохранение уже найденных промежуточных результатов с целью их повторного использования:

Int F(int n) { if (A[n] != -1) return A[n]; if (n < 2) return 1; else { A[n] = F(n - 1) + F(n - 2); return A[n]; } }
Приведенное решение является корректным и эффективным. Но для данной задачи применимо и более простое решение:

F = 1; F = 1; for (i = 2; i < n; i++) F[i] = F + F;
Такое решение можно назвать решением «с начала» — мы первым делом заполняем известные значения, затем находим первое неизвестное значение (F 3), потом следующее и т.д., пока не дойдем до нужного.

Именно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все F i для i < n ), затем, зная решения подзадач, нашли ответ (F n = F n - 1 + F n - 2 , F n - 1 и F n - 2 уже найдены).

Одномерное динамическое программирование

Пусть исходная задача заключается в нахождении некоторого числа T при исходных данных n 1 , n 2 , ..., n k . То есть мы можем говорить о функции T (n 1 , n 2 , ..., n k ), значение которой и есть необходимый нам ответ. Тогда подзадачами будем считать задачи
T (i 1 , i 2 , ..., i k ) при i 1 < n 1 , i 2 < n 2 , ..., i k < n k .

Следующая задача одномерного динамического программирования встречается в различных вариациях.

При n < 32 полный перебор потребует нескольких секунд, а при n = 64 полный перебор не осуществим в принципе. Для решения задачи методом динамического программирования сведем исходную задачу к подзадачам.

При n = 1, n = 2 ответ очевиден. Допустим, что мы уже нашли K n - 1 , K n - 2 — число таких последовательностей длины n - 1 и n - 2.

Посмотрим, какой может быть последовательность длины n . Если последний ее символ равен 0, то первые n - 1 — любая правильная последовательность длины
n - 1 (не важно, заканчивается она нулем или единицей — следом идет 0). Таких последовательностей всего K n - 1 . Если последний символ равен 1, то предпоследний символ обязательно должен быть равен 0 (иначе будет две единицы подряд), а первые
n - 2 символа — любая правильная последовательность длины n - 2, число таких последовательностей равно K n - 2 .

Таким образом, K 1 = 2, K 2 = 3, K n = K n - 1 + K n - 2 при n > 2. То есть данная задача фактически сводится к нахождению чисел Фибоначчи.

Двумерное динамическое программирование

Приведем пару формулировок таких задач:

Задача 2. n *m клеток. Можно совершать шаги длиной в одну клетку вправо или вниз. Посчитать, сколькими способами можно попасть из левой верхней клетки в правую нижнюю.

Задача 3. Дано прямоугольное поле размером n *m клеток. Можно совершать шаги длиной в одну клетку вправо, вниз или по диагонали вправо-вниз. В каждой клетке записано некоторое натуральное число. Необходимо попасть из верхней левой клетки в правую нижнюю. Вес маршрута вычисляется как сумма чисел со всех посещенных клеток. Необходимо найти маршрут с минимальным весом.

Для всех таких задач характерным является то, что каждый отдельный маршрут не может пройти два или более раз по одной и той же клетке.

Рассмотрим более подробно задачу 2. В некоторую клетку с координатами (i ,j ) можно прийти только сверху или слева, то есть из клеток с координатами (i - 1, j ) и (i , j - 1):

Таким образом, для клетки (i , j ) число маршрутов A[i][j] будет равно
A[j] + A[i], то есть задача сводится к двум подзадачам. В данной реализации используется два параметра — i и j — поэтому применительно к данной задаче мы говорим о двумерном динамическом программировании.

Теперь мы можем пройти последовательно по строкам (или по столбцам) массива A, находя число маршрутов для текущей клетки по приведенной выше формуле. Предварительно в A необходимо поместить число 1.

В задаче 3 в клетку с координатами (i , j ) мы можем попасть из клеток с координатами
(i - 1, j), (i , j - 1) и (i - 1, j - 1). Допустим, что для каждой из этих трех клеток мы уже нашли маршрут минимального веса, а сами веса поместили в W[j], W[i],
W. Чтобы найти минимальный вес для (i , j ), необходимо выбрать минимальный из весов W[j], W[i], W и прибавить к нему число, записанное в текущей клетке:

W[i][j] = min(W[j], W[i], W) + A[i][j];

Данная задача осложнена тем, что необходимо найти не только минимальный вес, но и сам маршрут. Поэтому в другой массив мы дополнительно для каждой клетки будем записывать, с какой стороны в нее надо попасть.

На следующем рисунке приведен пример исходных данных и одного из шагов алгоритма.

В каждую из уже пройденных клеток ведет ровно одна стрелка. Эта стрелка показывает, с какой стороны необходимо прийти в эту клетку, чтобы получить минимальный вес, записанный в клетке.

После прохождения всего массива необходимо будет проследить сам маршрут из последней клетки, следуя по стрелкам в обратную сторону.

Задачи на подпоследовательности

Задача 4. Дана последовательность целых чисел. Необходимо найти ее самую длинную строго возрастающую подпоследовательность.

Начнем решать задачу с начала — будем искать ответ, начиная с первых членов данной последовательности. Для каждого номера i будем искать наибольшую возрастающую подпоследовательность, оканчивающуюся элементом в позиции i . Пусть исходная последовательность хранится в массиве A. В массиве L будем записывать длины максимальных подпоследовательностей, оканчивающихся текущим элементом. Пусть мы нашли все L[i] для 1 <= i <= k - 1. Теперь можно найти L[k] следующим образом. Просматриваем все элементы A[i] для 1 <= i < k - 1. Если
A[i] < A[k], то k -ый элемент может стать продолжением подпоследовательности, окончившейся элементом A[i]. Длина полученной подпоследовательности будет на 1 больше L[i]. Чтобы найти L[k], необходимо перебрать все i от 1 до k - 1:
L[k] = max(L[i]) + 1, где максимум берется по всем i таким, что A[i] < A[k] и
1 <= i < k .

Здесь максимум из пустого множества будем считать равным 0. В этом случае текущий элемент станет единственным в выбранной последовательности, а не будет продолжением одной из предыдущих. После заполнения массива L длина наибольшей возрастающей подпоследовательности будет равна максимальному элементу L.

Чтобы восстановить саму подпоследовательность, можно для каждого элемента также сохранять номер предыдущего выбранного элемента, например, в массив N.

Рассмотрим решение этой задачи на примере последовательности 2, 8, 5, 9, 12, 6. Поскольку до 2 нет ни одного элемента, то максимальная подпоследовательность содержит только один элемент — L = 1, а перед ним нет ни одного — N = 0. Далее,
2 < 8, поэтому 8 может стать продолжением последовательности с предыдущим элементом. Тогда L = 2, N = 1.

Меньше A = 5 только элемент A = 2, поэтому 5 может стать продолжением только одной подпоследовательности — той, которая содержит 2. Тогда
L = L + 1 = 2, N = 1, так как 2 стоит в позиции с номером 1. Аналогично выполняем еще три шага алгоритма и получаем окончательный результат.

Теперь выбираем максимальный элемент в массиве L и по массиву N восстанавливаем саму подпоследовательность 2, 5, 9, 12.

Еще одной классической задачей динамического программирования является задача о палиндромах.

Задача 5. Дана строка из заглавных букв латинского алфавита. Необходимо найти длину наибольшего палиндрома, который можно получить вычеркиванием некоторых букв из данной строки.

Обозначим данную строку через S, а ее символы — через S[i], 1 <= i <= n . Будем рассматривать возможные подстроки данной строки с i -го по j -ый символ, обозначим их через S (i , j ). Длины максимальных палиндромов для подстрок будем записывать в квадратный массив L: L[i][j] — длина максимального палиндрома, который можно получить из подстроки S (i , j ).

Начнем решать задачу с самых простых подстрок. Для строки из одного символа (то есть подстроки вида S (i , i )) ответ очевиден — ничего вычеркивать не надо, такая строка будет палиндромом. Для строки из двух символов S (i , i + 1) возможны два варианта: если символы равны, то мы имеем палиндром, ничего вычеркивать не надо. Если же символы не равны, то вычеркиваем любой.

Пусть теперь нам дана подстрока S (i , j ). Если первый (S[i]) и последний (S[j]) символы подстроки не совпадают, то один из них точно нужно вычеркнуть. Тогда у нас останется подстрока S (i , j - 1) или S (i + 1, j ) — то есть мы сведем задачу к подзадаче: L[i][j] = max(L[i], L[j]). Если же первый и последний символы равны, то мы можем оставить оба, но необходимо знать решение задачи S (i + 1, j - 1):
L[i][j] = L + 2.

Рассмотрим решение на примере строки ABACCBA. Первым делом заполняем диагональ массива единицами, они будут соответствовать подстрокам S (i , i ) из одного символа. Затем начинаем рассматривать подстроки длины два. Во всех подстроках, кроме S (4, 5), символы различны, поэтому в соответствующие ячейки запишем 1, а в L — 2.

Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали, ведущей из левого верхнего угла в правый нижний. Для подстрок длины 3 получаются следующие значения: в подстроке ABA первая и последняя буквы равны, поэтому
L = L + 2. В остальных подстроках первая и последняя буквы различны.

BAC: L = max(L, L) = 1.
ACC: L = max(L, L) = 2.
CCB: L = max(L, L) = 2.
CBA: L = max(L, L) = 1.

Если же в задаче необходимо вывести не длину, а сам палиндром, то дополнительно к массиву длин мы должны построить массив переходов — для каждой ячейки запомнить, какой из случаев был реализован (на рисунке для наглядности вместо числовых значений, кодирующих переходы, нарисованы соответствующие стрелки).

На уроке будет рассмотрено понятие динамического программирования и исторический аспект его появления. Рассмотрены задачи динамического программирования и некоторые примеры их решения

Само понятие «динамическое программирование» впервые было использовано в 1940-х годах Ричардом Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения другой задачи, «предшествующей» ей.
Таким образом, американский математик и один из ведущих специалистов в области математики и вычислительной техники — Ричард Эрнст Беллман — стал прородителем динамического программирования.

Позднее формулировка понятия была доработана и усовершенствованна до современного вида самим же Беллманом.

Слово «программирование» в контексте «динамическое программирование» на самом деле к классическому пониманию программирования (написанию кода на языке программирования) практически никакого отношения не имеет . Слово «Программирование» имеет такой же смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация».

Поэтому программы будут использоваться в качестве оптимальной последовательности действий для получения решения задачи.

В общем же для начала, неформальное определение понятия динамического программирования может звучать так:

Динамическое программирование — это техника или метод, которая позволяет решать некоторые задачи комбинаторики, оптимизации и другие задачи, обладающие определенным свойством (свойством сооптимальности у подзадач).

Задачи оптимизации , как правило, связаны с задачей максимизации или минимизации той или иной целевой функции (например, максимизировать вероятность того, что система не сломается, максимизировать мат. ожидание получения прибыли и т.д.).

Задачи комбинаторики , как правило, отвечают на вопрос, сколько существует объектов, обладающих теми или иными свойствами, или сколько существует комбинаторных объектов, обладающих заданными свойствами.

То есть, ДП решает не все задачи, а лишь некоторые, определенный класс подзадач. Но этот класс подзадачи используется во многих областях знаний: программирование, математика, лингвистика, статистика, теория игр, экономика, в компьютерных науках и т.п.

Задачи, решаемые при помощи динамического программирования, должны обладать свойством сооптимальности , о котором будет сказано в дальнейших уроках.

Неформальное объяснение свойства оптимальности у подзадач может быть продемонстрировано с помощью диаграммы:
Есть задача, которую мы хотим решить при помощи ДП, т.е. найти какой-то план ее решения. Допустим эта задача сложна и сразу решить мы ее не можем. Мы берем малую подзадачу и решаем сначала ее (для x1). Затем используя это малое решение x1 , и не меняя структуру этого решения, решаем следующую задачу уже с x1 и x2 . И т.д.

Рис. 1.1. Неформальное объяснение свойства оптимальности у подзадач

Более подробно неформальное объяснение рассматривается .

Примеры, решаемых при помощи динамического программирования задач

Сначала рассмотрим задачи оптимизации (задачи 1-5):

1. Маршрут оптимальной длины

Пример: Есть некоторая карта дорог, представленная в виде графа. Наша цель: добраться из пункта А в пункт Б . Это сделать надо так, чтобы минимизировать расстояние или потраченное топливо.

Целевой функцией здесь является расстояние от А до Б . Т.е. наша цель — минимизировать расстояние.

А что является переменной выбора ? Для того, чтобы найти кратчайший путь, надо каждый раз принимать решения. Т.е. в каждой точке или на каждом перекрестке необходимо принимать решения: куда повернуть или ехать прямо.

Важно: Из этой задачи уже можно увидеть общую структуру задач, решаемых при помощи динамического программирования: в каждой задаче есть целевая функция и переменная выбора .

2. Замена машины (минимизация расходов)

Пример: Каждый год мы принимаем решение, ездить ли на старой машине еще год и понести при этом издержки на поддержку и обслуживание старой машины или же продать эту машину и купить новую (и понести при этом издержки на покупку).

Целевая функция: минимизация расходов (либо на издержки на поддержку старого автомобиля, либо на покупку нового).

Переменная выбора: каждый год принимать решение продать машину или оставить.

3. Биржевой портфель

Пример: Игра на бирже, приобретение акций каких-либо компаний


Целевая функция: максимизация средних доходов, т.к. на бирже доход получается вероятностным путем, т.е. это статистический процесс, вероятностный.

Переменная выбора: то, какой портфель вложений будет: сколько акций и какой фирмы нам необходимо купить.

4. Составление плана оптимального производства (логистика)

Пример: Есть завод, изготавливающий мебель. На заводе работает определенное количество работников, которые могут изготовить соответствующее кол-во определенной мебели (стулья, столы, шкафы и т.п.)


Целевая функция : максимизация прибыли.

Переменная выбора: выбор того, сколько необходимо изготовить стульев или столов, чтобы хватило рабочей силы.

5. Игры (вероятностные или не вероятностные)

Пример: Участие в различных играх


Целевая функция: максимизация вероятности выигрыша или максимизация среднего выигрыша и т.д.

Переменная выбора здесь зависит от конкретной игры.

Задачи 1 — 5 — это примеры задач оптимизации.

Комбинаторика:

6. Графы и деревья

Пример: Задача на решение того, сколько существует деревьев, у которых определенное число листьев; или сколько существует графов для решения такого-то задания и т.п.

7. Задача о размене монет или количество способов вернуть сдачу

Пример: Есть монеты разного достоинства, какими способами можно вернуть сдачу.

Это краткое описание задач для динамического программирования, которые подробно будут рассмотрены позднее.

Понятие динамического программирования

Неформальное объяснение оптимальности подзадач ДП.

Рассмотрим неформальную идею ДП.

Итак, возьмем пример с заводом, изготавливающим мебель.

Для достижения цели максимизации прибыли необходимо решить множество подзадач:

• сколько стульев произвести — переменная X1 ,
• сколько столов произвести — переменная X2 ,
• сколько нанять работников — переменная X3 ,
• … Хn .

При большом количестве подзадач сложно понять, как решать такую задачу. Как правило, решить одну малую задачу проще, чем решить большую задачу , состоящую из маленьких.

Поэтому ДП предлагает следующее:

• берем одну подзадачу с переменной X1 , об остальных подзадачах пока забываем.

Например, завод производит только стулья. У директора стоит задача получения максимальной прибыли с продажи стульев.

• После того, как найдем оптимальное решение для первой подзадачи, берем подзадачу для двух переменных Х1 и Х2 , и решаем ее с помощью уже найденного решения для первой подзадачи .
• Получаем решение уже для большей подзадачи, где фигурируют переменные Х1 и Х2 . Затем, используя полученное решение, берем подзадачи, охватывающие X1 , X2 и Х3 .
• И так продолжаем пока не получим решение для всей общей задачи.

Формальная идея ДП

Часто при постановке задачи кажущимся оптимальным решением является перебор всех возможных вариантов . Однако, вследствии очень большого количества таких вариантов и, как результат, перегрузки памяти компьютера, такой способ не всегда приемлем.

Кроме того, может возникнуть такой вопрос: для того чтобы найти, например, минимум или максимум, почему бы нам не найти производную? или не использовать множества Ла-Гранжа, или другие методы аппарата математического анализа? Зачем нужно ДП, если есть большой арсенал средств?

Дело в том, что:

В основе динамического программирования лежит идея решения поставленной задачи путем деления ее на отдельные части (подзадачи, этапы), решение этих подзадач и последующего объединения этих решений в одно общее решение. Часто большинство из подзадач абсолютно одинаковы.

При этом важно, что при решении более сложной задачи, мы не решаем заново маленькую подзадачу, а используем уже решенный ответ этой подзадачи.
На графике это может выглядеть так:

Важно: По этой причине разделение задачи на подзадачи и решение этих подзадач только один раз (!) , сокращая этим количество общих вычислений — более оптимальный способ, который и заложен в динамическом программировании

Когда мы решаем задачу с производными, множествами Ла-Гранжа и т.п., то мы работаем с непрерывными функциями. При решении же задач ДП мы будем работать в основном с дискретными функциями, поэтому говорить здесь о применении непрерывных функций неуместно.
По этой причине во многих задачах, но не во всех, применение аппарата математического анализа будет неприемлемым.

Простой пример решения задач при помощи ДП

Рассмотрим вариант решения задачи с помощью динамического программирования.

Пример: Необходимо вычислить сумму n чисел: 1 + 2 + 3 + ... + n

Попробуем применить к задаче идеи ДП и решить ее, разбивая на простые подзадачи.
(В ДП всегда необходимо сначала определить начальные условия или условие)

• Начнем с суммы одного первого элемента, т.е. просто берем первый элемент:
  F(1) = 1
• теперь с помощью решения для первого элемента, решим
  F(2) = F(1) + 2 = 1 + 2 = 3 , т.е. надо взять сумму первого элемента и добавить к нему второй элемент
• F(3) = F(2) + 3 = 6
• по аналогии продолжаем и получаем целевую функцию:
  F(n) = F(n-1) + An

Итак, что мы сделали: определили порядок и вычленили подзадачи, затем решили каждую из них, опираясь на решение предыдущей.

Простой пример, где пока неоправданно используется ДП (искусственно), демонстрирует принцип идей ДП.

Рассмотрим еще один пример.

Пример: имеется лесенка из n ступенек, перед которой находится человек, который за 1 шаг умеет подниматься либо на следующую ступеньку, либо перепрыгивает через одну ступеньку. Вопрос: сколькими способами он может попасть на последнюю ступеньку?

Рассмотрим самые простые варианты (подзадачи):

Рассмотрим пример из i ступенек

Как мы можем попасть на i ступеньку:

1. с i-1 ступеньки, а на i-1 ступеньку мы могли попасть a i-1 способами
2. с i-2 ступеньки, а на i-2 ступеньку мы могли попасть a i-2 способами

Например, как попасть на 4-ю ступеньку :

Т.о., общее количество способов попасть на i ступеньку:
f(a i) = f(a i-1) + f(a i-2)

Определим начальные значения , с которых следует начинать решать задачу.
Если начинать с 1, то формула соответствует нахождению последовательности чисел Фибоначчи.

Мы видим, что задача по сути комбинаторная (т.е. количество способов сделать что-либо) свелась к вычислению некоторой рекуррентной последовательности.

Задание 1: реализовать пример для первых десяти ступенек (по сути, первые 10 чисел ряда Фибоначчи), используя рекурсию.

Дополните код:

var c:integer; procedure getKolSposob(i,n: integer); begin writeln (i+n," "); inc(c); if ... then getKolSposob(...,...) end; begin c:=1; getKolSposob(0,1); end.

Задание 2:
Решение 15-го типа заданий ЕГЭ (Графы. Поиск количества путей).

) , выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.

Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.

Метод динамического программирования сверху - это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.

Энциклопедичный YouTube

• 1 / 5

  Словосочетание «динамическое программирование» впервые было использовано в -х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В г. он уточнил это определение до современного. Первоначально эта область была основана, как системный анализ и инжиниринг, которая была признана IEEE . Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана , центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме.

  Слово «программирование» в словосочетании «динамическое программирование» в действительности к «традиционному» программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование », которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определенное расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий.

  Идея динамического программирования

  Оптимальная подструктура в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. К примеру, кратчайший путь в графе из одной вершины (обозначим s) в другую (обозначим t) может быть найден так: сначала считаем кратчайший путь из всех вершин, смежных с s, до t, а затем, учитывая веса ребер, которыми s соединена со смежными вершинами, выбираем лучший путь до t (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.

  1. Разбиение задачи на подзадачи меньшего размера.
  2. Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм .
  3. Использование полученного решения подзадач для конструирования решения исходной задачи.

  Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).

  Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи , F 3 = F 2 + F 1 {\displaystyle F_{3}=F_{2}+F_{1}} и F 4 = F 3 + F 2 {\displaystyle F_{4}=F_{3}+F_{2}} - даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали дважды. Если продолжать дальше и посчитать , то F 2 {\displaystyle F_{2}} посчитается ещё два раза, так как для вычисления F 5 {\displaystyle F_{5}} будут нужны опять F 3 {\displaystyle F_{3}} и F 4 {\displaystyle F_{4}} . Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решения для задач, которые он уже решал.

  Чтобы избежать такого хода событий мы будем сохранять решения подзадач, которые мы уже решали, и когда нам снова потребуется решение подзадачи, мы вместо того, чтобы вычислять его заново, просто достанем его из памяти. Этот подход называется мемоизацией . Можно проделывать и дальнейшие оптимизации - например, если мы точно уверены, что решение подзадачи нам больше не потребуется, можно выкинуть его из памяти, освободив её для других нужд, или если процессор простаивает и мы знаем, что решение некоторых, ещё не посчитанных подзадач, нам понадобится в дальнейшем, мы можем решить их заранее.

  Подводя итоги вышесказанного можно сказать, что динамическое программирование пользуется следующими свойствами задачи:

  • перекрывающиеся подзадачи;
  • оптимальная подструктура;
  • возможность запоминания решения часто встречающихся подзадач.

  Динамическое программирование обычно придерживается двух подходов к решению задач:

  • нисходящее динамическое программирование: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач.
  • восходящее динамическое программирование: все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи. Этот способ лучше нисходящего программирования в смысле размера необходимого стека и количества вызова функций, но иногда бывает нелегко заранее выяснить, решение каких подзадач нам потребуется в дальнейшем.

  Языки программирования могут запоминать результат вызова функции с определенным набором аргументов (мемоизация), чтобы ускорить «вычисление по имени». В некоторых языках такая возможность встроена (например, Scheme , Common Lisp , Clojure , Perl), а в некоторых требует дополнительных расширений (C++).

  Известны сериальное динамическое программирование, включённое во все учебники по исследованию операций , и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах.

  Обычное динамическое программирование является частным случаем несериального динамического программирования, когда граф взаимосвязей переменных - просто путь. НСДП, являясь естественным и общим методом для учета структуры задачи оптимизации, рассматривает множество ограничений и/или целевую функцию как рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причём эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объём вычислений на каждом этапе может сохраняться в разумных пределах.

  Одним из основных свойств задач, решаемых с помощью динамического программирования, является аддитивность . Неаддитивные задачи решаются другими методами. Например, многие задачи по оптимизации инвестиций компании являются неаддитивными и решаются с помощью сравнения стоимости компании при проведении инвестиций и без них.

  Классические задачи динамического программирования

  • Задача о наибольшей общей подпоследовательности : даны две последовательности, требуется найти самую длинную общую подпоследовательность.
  • Задача поиска наибольшей увеличивающейся подпоследовательности : дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.
  • Задача о редакционном расстоянии (расстояние Левенштейна) : даны две строки, требуется найти минимальное количество стираний, замен и добавлений символов, преобразующих одну строку в другую.
  • Задача о порядке перемножения матриц : даны матрицы A 1 {\displaystyle A_{1}} , …, A n {\displaystyle A_{n}} , требуется минимизировать количество скалярных операций для их перемножения.
  • Задача о выборе траектории
  • Задача последовательного принятия решения
  • Задача об использовании рабочей силы
  • Задача управления запасами