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

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

F (a₁, a₂, …, a_m) = С(a₁) + С(a₂) +…+ С(a_m),

где С(a_i) – функция, определенная для всех a_i. Показатели такого вида называют аддитивными. Требуется найти такой набор (a₁, a₂, …, a_m), чтобы стоимость была минимальной (максимальной).

Рассмотрим примеры многошаговых операций.

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

· продать аппарат и заменить его новым;

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

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

Требуется спланировать управление на все m лет, чтобы суммарные расходы на эксплуатацию, ремонт и приобретение новых аппаратов были минимальными. Управление состоит в выборе одного из трех решений в начале каждого года. Обозначим их цифрами 1, 2 и 3.

Стоимость складывается из годовых затрат. Решение представляет из себя комбинацию чисел 1, 2 и 3. Например, (3, 3, 2, 2, 2, 1, 3, …) означает: первые 2 года эксплуатировать аппарат без ремонта, последующие 3 года производить ремонт, в начале шестого года продать, купив новый, затем снова эксплуатировать без ремонта и т. д.

Планируется деятельность промышленных предприятий B₁, B₂, …, B_k на m лет. В начале периода на развитие всей группы предприятий выделены средства в размере S единиц. В процессе работы предприятия вложенные в него средства частично расходуются, а частично сохраняются и снова могут быть перераспределены. Каждое предприятие за год приносит доход, зависящий от того, сколько средств в него вложено. В начале каждого года имеющиеся в наличии средства перераспределяются между предприятиями. Ставится вопрос: какое количество средств нужно выделять каждому предприятию, чтобы суммарный доход за m лет был максимальным?

Суммарный доход представляет собой сумму доходов на отдельных шагах (годах). На каждом i-ом шаге предприятиям выделяются некоторые средства a_i1, a_i2, …, a_ik (первый индекс – номер шага, второй – номер предприятия), то есть ai = (a _i1, a_i2, …, a _ik). Таким образом, элементы a_i представляют собой вектора.

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

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

Планируя последний шаг, нужно рассмотреть все возможности того, чем кончился предпоследний (m-1)-й шаг, и для каждой такой возможности найти наилучший вариант последнего шага. В динамическом программировании это называют условным оптимальным управлением, так как оно выбирается из условия, что предпоследний шаг закончился определенным образом. Затем находят условное оптимальное управление на (m-2)-м шаге и т. д., пока не доходят до первого шага, на котором находится уже истинное оптимальное управление, минимизирующее функцию стоимости. Сейчас двигаясь от начала к концу, на каждом i-ом шаге находят наилучшие значения ai.

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

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

Пусть, например, прямоугольник (квадрат) заполнен следующим образом:

Для удобства клетки обозначаются аналогично шахматам: буквами по горизонтали и цифрами по вертикали. Результаты прохода от конечной клетки к начальной показаны ниже. Направление лучшего хода отмечено символами " ► ” и " ▲ ”. В каждой клетке проставлена наименьшая стоимость пути, включая стоимости ее самой и конечной клетки.

Начнем с конечной клетки E1. В нее можно попасть за один ход из клеток D1 и E2. В обеих клетках возможен единственный ход. В клетке D1 проставляется стоимость 14+9=23, а в e2 – (-1)+9=8. Далее проставим минимальную стоимость во все клетки первой строки, двигаясь влево от клетки D1. Для каждой такой клетки также имеется единственный ход, и стоимость формируется путем сложения стоимости текущей клетки с минимальной стоимостью клетки справа, рассмотренной на предыдущем шаге. Аналогично сверху вниз находятся минимальные стоимости для всех клеток последней вертикали E.

Далее также в порядке сверху вниз рассмотрим клетки предпоследнего столбца D. В клетке D2 нужно, очевидно, двигаться направо, поскольку стоимость клетки E2 меньше, чем D1. Запомним направление движения из клетки D2 и минимальную стоимость 12+8=20. В клетке D3 лучший ход вверх при стоимости 8+12=20. Затем можем перейти к третьему столбцу с и т. д. Отметим, что, в клетке B5 оба хода приводят к одинаковой стоимости 35.

Начальная клетка A5 будет рассмотрена последней. Получим, что минимальная стоимость пути из A5 в E1 составляет 43 единицы. Сам путь восстанавливается по тем лучшим ходам, которые были сохранены. В этом примере есть 2 пути минимальной стоимости: A5, B5, B4, C4, C3, C2, C1, В1, E1 и A5, B5, C5, C4, C3, C2, C1, D1, E1.

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

Отметим в заключение некоторые дополнительные аспекты применения методов динамического программирования.

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

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

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

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

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

…