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

Американский математик Ричард Беллман (1920–1984) придумал метод решения широкого класса сложных многошаговых задач. Идея метода состоит в том, что на многошаговую задачу надо посмотреть «с конца» и при нахождении оптимальной стратегии поведения на каком-либо шаге использовать уже найденные оптимальные стратегии на последующих шагах.

Такой метод получил название метод динамического программирования, и в основе метода лежит принцип оптимальности Беллмана.

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

Попробуем разобраться в этом на первый взгляд запутанном принципе на простом примере. Пусть есть квадратная доска, например 4x4, в клетках которой записаны числа. Пусть в левом нижнем углу доски стоит фишка, которую на каждом шаге можно двигать на одну клетку вверх либо вправо. Обозначим левую нижнюю клетку Ст (старт), а правую верхнюю Фн (финиш). Нужно провести фишку из клетки Ст в клетку Фн так, чтобы сумма всех чисел в промежуточных клетках была бы наименьшей.

4	7	2	1	Фн
3	9	0	4	3
2	4	5	6	8
1	Ст	3	7	5
	А	B	C	D

Таблица 1. Исходные данные задачи.

Для обозначения клеток в дальнейших рассуждениях введём нотацию, аналогичную шахматной – строки обозначим цифрами, а столбцы – буквами. Пусть теперь фишка находится не в начальной клете А1, а в некоторой другой (например, С3). Тогда, согласно принципу оптимальности Беллмана, каким бы образом мы не пришли в клетку С3, далее следует двигаться так, чтобы сумма чисел, встреченных на пути из С3 в D4, была бы наименьшей.

         Обозначим функцию, ставящую в соответствие клетке число, занесённое в неё, через f (например, в данном случае f(B2)=5), а функцию, ставящую в соответствие клетке минимальную сумму на пути из неё в D4 через g(x) (пока мы не знаем значение этой функции, но хотим узнать, и будем постепенно узнавать это значение для различных клеток, двигаясь справа-налево и сверху-вниз).

Рассмотрим клетки 4-й строки. Очевидно, что из каждой из них существует единственный путь в D4, а именно – двигаться всё время вправо. При этом сумма чисел в этой клетке и в клетках, которые встретятся на дальнейшем пути, равна: для С4 – 1, для В4 – 2+1=3, для А4 – 7+2+1=10.

Поскольку из каждой из этих клеток существует единственный путь в А4, то он является оптимальным (из всех возможных). Отсюда g(C4)=1, g(B4)=3, g(А4)=10. Аналогично, из клеток столбца D существует единственный путь в D4, а именно – двигаться все время вверх. Вычислим суммы чисел для этих клеток. Для D3 – 3, для D2 – 8+3=11, для D1 – 5+8+3=16. Отсюда g(D3)=3, g(D2)=11, для g(D1)=16.  

Внесём в клетки вычисленные суммы, а также стрелками покажем направления движения в соседние клетки (для клеток 4-й строки это будут стрелки вправо, а для столбца D – стрелки вверх). Теперь обратим внимание на клетку С3.

Мы уже знаем, какую сумму мы добавим, если пойдём вверх к С4 (g(С4)=1) или если пойдем вправо (g(D3)=3). Поскольку мы хотим получить как можно меньшую добавку, выбираем движение вверх и полагаем, что

g(C4)=f(C4)+min(g(C4),g(D3))=4+1=5.

4	10,→	3,→	1,→	Фн
3			5, ↑	3,↑
2				11, ↑
1				16, ↑
	А	B	C	D

Таблица 2. Значение функции g и оптимальные траектории, промежуточные вычисления

Пусть для некоторой клетки значение g ещё неизвестно, но оно известно для «соседок» данной клетки сверху и справа. Тогда минимальное значение суммы по всем траекториям, начинающимся в данной клетке, равно сумме числа, стоящего в этой клетке, и минимального из двух значений функции g – от соседки сверху и соседки справа.

g(клетка)=f(клетка)+min(g(соседка сверху), g(соседка справа)).

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

В таблице 2 клетками, к которым можно применить данную формулу, являются В3 и С2:

g(B3)=0+min(3,5)=0+3=3, вверх; g(C2)=6+min(5,11)=6+5=11, вверх.

После этого доступными для вычисления g становятся клетки А3, В2 и С1: g(A3)=9+min(10,3)=9+3=12, вправо; g(В2)=5+min(3,11)=5+3=8, вверх; g(C1)=7+min(11,16)=7+11=18, вверх.

После этого доступными для вычисления g становятся клетки А2, В1 и наконец, А1: g(A2)=4+min(12,8)=4+8=12, вправо; g(В1)=3+min(8,18)=3+8=11, вверх; g(A1)=0+min(12,11)=11, вправо.

4	10,→	3,→	1,→	Фн
3	12, →	3, ↑	5, ↑	3,↑
2	12, →	8, ↑	11, ↑	11, ↑
1	11, →	11, ↑	18, ↑	16, ↑
	А	B	C	D

Таблица 3. Значение функции g и оптимальные траектории, окончательные вычисления.

По таблице 3, двигаясь по стрелкам из А1 в D4, находим оптимальную траекторию: A1-B1-B2-B3-B4-C4-D4, и искомое минимальное значение суммы равно 11.

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

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

Ханойские башни

Головоломка с таким названием была придумана в 1883 году французским математиком Эдуардом Люка (1842–1891). Название было придумано самим Люка, чтобы придать головоломке восточно-мистический смысл и тем самым обеспечить её лучшие продажи. Внешне нанизанные друг на друга кольца действительно напоминают восточную пагоду.

Смысл головоломки состоит в следующем.

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

Возникает два вопроса – за какое минимальное количество ходов можно переместить n колец с одного стержня на другой и как собственно это сделать?

Обозначим минимальное число ходов для головоломки с n башнями через f(n). Пусть n=1. Тогда, очевидно, нужно просто за один ход переместить одно кольцо с одного стержня на другой. Таким образом, f(1)=1.

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

Таким образом, нужно переместить n-1 кольцо с А на В (по предположению, мы умеем это делать, и для этого понадобится f(n-1) шагов), переместить нижнее кольцо с А на С и переместить n-1 кольцо с В на С, используя освободившийся стержень А в качестве промежуточного (для этого опять же понадобится f(n-1) шагов). Таким образом, для f(n) справедливо рекуррентное соотношение: f(n)=2f(n-1)+1.

Функция, удовлетворяющая этому соотношению и начальному условию f(1)=1 имеет вид: f(n)=2ⁿ–1.

Желающие увидеть решение головоломки в динамике могут посмотреть на youtube ролик под названием «Задача о ханойской башне».

Задача выбора самой длинной возрастающей подпоследовательности

Пусть задано последовательность действительных чисел a₁, a₂,…,a_n. Подпоследовательностью данной последовательности назовём любую последовательность, которую можно получить из данной путём вычёркивания элементов. Из исходной последовательности нужно выбрать возрастающую подпоследовательность максимальной длины.

Решение.

Рассмотрим последовательность s_k=a₁, a₂,…,a_k. Возрастающую подпоследовательность данной последовательности назовём бесперспективной, если существует другая подпоследовательность не меньшей длины и с не большим последним элементом, чем данная, причём, по крайней мере, одно из неравенств строгое.

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

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

Пример.

1,3,2,5,4,8,3,6,7

1-й шаг. Единственная перспективная подпоследовательность – 1
2-й шаг. Имеем две подпоследовательности – 1 и 1,3
3-й шаг. Оставляем 1, добавляем 1,2 и отбрасываем 1,3
4-й шаг. 1;   1,2;   1,2,5
5-й шаг. 1; 1,2; 1,2,4 (1,2,5 отбрасываем)
6-й шаг.  1;   1,2; 1,2,4; 1,2,4,8
7-й шаг.    1; 1,2; 1,2,3; 1,2,4,8
8-й шаг.    1;   1,2; 1,2,3 1,2,3,6 (1,2,4,8 отбрасываем)
9-й шаг.  1,2,3,6,7 – самая длинная возрастающая подпоследовательность.

Задача о рюкзаке

Пусть есть рюкзак вместимостью W и n неделимых предметов, каждый из которых характеризуется весом w_i и ценностью p_i, и пусть суммарный вес предметов превышает вместимость рюкзака. Нужно из множества предметов выбрать подмножество так, чтобы их суммарная ценность была бы максимальной, и при этом их суммарный вес не превышал вместимости рюкзака.

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

Аналогичная ситуация возникает при решении задачи о загрузке транспортных средств в условиях ограниченной грузоподъёмности (т.е. когда суммарный вес грузов превышает грузоподъёмность транспортного средства).

Другое применение данной задачи – планирование рабочего времени.

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

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

Пусть есть четыре предмета, их характеристики задано в таблице:

Предмет	1	2	3	4
Вес	2	4	5	8
Ценность	4	5	9	11

Пусть вместимость рюкзака равна 10. Каждому способу заполнения рюкзака будем ставить в соответстие пару чисел, где первое число означает суммарный вес, а второе – суммарную полезность. Например, если в рюкзаке лежит первый и второй предметы, то их суммарный вес равен 2+4=6, а суммарная полезность – 4+5=9. Такому заполнению соответствует запись (6,9).

Будем решать задачу пошагово. На нулевом шаге есть только один способ заполнения рюкзака – в нём нет предметов, обозначаем это (0,0). На каждом шаге будем добавлять по одному предмету и будем к уже найденным способам заполнения рюкзака добавлять новые, возникающие в результате добавления нового предмета. Сделать это очень просто.

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

Например, пусть уже найден способ заполнения (4,5). Пытаемся добавить третий предмет (с весом 5 и ценностью 9). Тогда суммарный вес предметов станет равным 4+5=9, что не превышает вместимости рюкзака, равной 10.

Таким образом, возникает дополнительный способ заполнения (9,14). Если же попытаемся добавить к способу (4,5) четвёртый предмет (с весом 8 и ценностью 11), то суммарный вес предметов составит 4+8=12, что превышает вместимость рюкзака. В этом случае не пишем ничего. После того, как на очередном шаге к уже имеющимся способам были добавлены новые, упорядочим все способы в порядке возрастания веса и отбросим бесперспективные.

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

0-й шаг – (0,0)
1-й шаг – (0,0), (2,4)
2-й шаг – остаются два старых способа (0,0), (2,4), и ещё в результате добавления 2-го предмета возникает два новых – (4,5) и (6,9).
Записываем список способов: (0,0), (2,4), (4,5) , (6,9).
3-й шаг – к множеству способов 2-го шага (0,0), (2,4), (4,5), (6,9) в результате добавления 3-го предмета добавляется ещё три способа – (5,9), (7,13) и (9,14). Заметим, что вариант заполнения рюкзака (6,9) является бесперспективным, поскольку существует способ (5,9). Отбрасываем этот бесперспективный способ и упорядочиваем остальные в порядке возрастания веса: (0,0), (2,4), (4,5) , (5,9), (7,13), (9,14).
4-й шаг. – В результате добавления 4-го предмета возникает ещё два способа – (8,11) и (10,15). Из всех способов максимальная полезность равна 15, и она достигается, когда в рюкзаке лежат 1-й и 4-й предметы.

Читателю предлагается самостоятельно решить задачу о рюкзаке для данного набора предметов, предположив, что вместимость рюкзака равна не 10, а 12.

С.И. Доценко, кандидат физико-математических наук, старший научный сотрудник факультета компьютерных наук и кибернетики КНУ имени Тараса Шевченко