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

6

ДиНАМЧЕСКОЕ
ПРОГРАММИРОВАНИЕ

Лестница фараона

Дворец фараона славился своей русскойю: жемчужные занавесы, стены, отделанные янтарем, золотая посуда — всего не перечень. Но больше всего поражала тех, кто допускался в тронный зал дворца, золотая лестница, которая вела к трону. Как выглядела эта лестница в разрезе, если перевести древнегипетские меры в действительны, вы видите на рисунке 1.
Археологам не пришлось долго ломать головы, чтобы понять, отчето ступени лестницы были такими низкими, все объяснялось просто: представленный фараон не хотел, чтобы подданные видели, как тяжело ему взбираться на трон, они могли утратить почтение, а кто знает, чем это могло кончиться?
Позмоту он и повелел приводным ювелирам сделать лестницу с таким низкими ступенями, не выше 1,5 дм.
Но время шло, и старый фараон скончался. Его молодой сын принял царство.
Молодой фараон слышал и раныше, как приворные посменвались над наивной хитростью отца. И хотя сам он общино взлетал на трон, прыгая через три ступенки, но кривотолки продолжались. И молодой фараон решил покончить с ним, нарастив лестницу. Для этого он призвал приворных ювелиров и казначей и сказал им:
— Слуши мои! Повелеваю вам нарастить лестницу так, чтобы она имела самоое большое четыре ступени. Устройте их, где хотите, но чтобы их было не большое четырех!
— Но госпударь, — робко вышел вперед казначей, — где взят столко золота? Вот я тут прикнул на листке паприуса (и казначей показал то, что изображен на рисунке лестницы пунктиром). Лестница имеет ширину 1 м, или 10 дм. Значит, для ее наращивания попадится [3×1,5+1,2×(5+1)+1×1+1×3+0,8(3+4)+1,2×11]×10 = 345 дм³ золота! Увы, госпударь, столко не найдется в нашей казне, разоренной войной с Эфюпней.
— Презренный! Ты бросаешь тень на мое могущество! Если через 7 дней лестница не будет готова, я сам утоплю тебя в свяшеном Ниле, а ювелиры будут проданы в работе. И не видумай еще раз соваться со своим дураскими чертежами!
Удрученный ущел казначей от фараона и отпавлися к своему другу. Не было человек искуснее, когда нужно было распланировать парамиду или исчислить земельные надели. Хотя друг и был по должности жрецом столчного храма, но слышил человеком расчетливым и практичным. Узнав о беде, он спросил:
— А сколько золота осталось в казне?
— 200 дм³.
— Не густо! А может быть можно обойтись меньшим количеством, если иначе распланировать ступенки?

8

нарастить или вторую, или первый ступеньку, а знак min показывает, что нужно взять наименьшую из них. Подставим в фигуры скобки величины $f_1(1)$ и $f_1(2)$, найdenные равные:
$$f_2(3) = \min\{(0+0,7\times4), (4,5+0)\} = 2,8.$$
Тепер уже видно, что если в листнице всего три ступеньки, а их число нужно сократить до двух, то наращивать нужно вторую ступеньку.
— А если бы ступенек было 4?
— Тогда
$$f_2(4) = \min\{(f_1(1) + 0,7\times4 + 1\times(4+1)), (f_1(2) + 1\times1), (f_1(3) + 0)\} = \min\{(0+7,8), (4,5+1), (9,4+0)\} = 5,5$$
то есть, если в листнице было 4 ступеньки, а мы заменяем их двумя, то первый лучше всего закончит на второй старой (рис. 4).
— Погоди, я хочу убедиться, что понял, — первая его казначей. — Значит, чтобы найти $f_2(5)$, нужно действовать так:
$$f_2(5) = \min\{(0+7,8+1,2\times(4+1+5)), (4,5+1\times1+1,2\times(1+5)), (9,4+1,2\times5), (17,4)\} = \min\{(19,8), (12,7), (15,4), (17,4)\} = 12,7.$$
— Вопросу, мудрые следят за казной государства, — пользовали.

Рис. 2.
8

жрец. — А дальше
$$f_2(6) = \min\{(0+19,8 + 1\times(4+1+5)), (4,5+8,2+1\times(1+5+3)), (9,4+1,2\times5+8), (17,4+1\times3), (33+0)\} = \min\{(0+32,8), (4,5+17,2), (9,4+14,0), (17,4+3), (33+0)\} = \min\{(32,8), (21,7), (23,4), (20,4), 33\} = 20,4.$$
Можно было бы продолжать и найти $f_2(7)$, но в этом нет нужны, как ты вскоре увидишь. Перейдем теперь к случая, когда лестница заменяется треем ступеньками.
Начнем с того, что найдем $f_3(4)$, то есть самый разумный вариант наращивания первых четырех ступенек. Ведь $f_3(1)$ и $f_3(2)$ лишены смысла (не стоит заменять одну или две ступеньки треем), а $f_3(3)=0$ — наращивание трех ступенек до трех не требуется никакого расхода золота. Чтобы найти $f_3(4)$, посмотрим, где может кончаться вторая ступенька. Конечно, или на 2-й, или на 3-й старой. Значит,
$$f_3(4) = \min\{f_2(2)+1\times1), (f_2(3)+0)\} = \min\{0+1), (2,8+0)\} = 1.$$
Следовательно, наращивание 4 ступеньки так, чтобы их стало 3, нужно окончит новую вторую ступеньку.

10

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

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

Пусть требуется нарастить лестницу, имеющий $N$ ступенек, так, чтобы она их имела $n$, где $N \gg n$, то есть $N$ намного больше $n$. Допустим, что нам уже известно оптимальное распределение ступенек, когда их в новой лестнице $j$, где $j \leq n$. Пусть $S_j$ — номер старов ступенек, на котором кончается $j$-я новая. Очевидно, начинается эта $j$-я ступенка на $(S_{j-1}+1)$-й старой. Добавочная площадь лестницы, изображенная на рисунке 6 штриховкой, будет завися от $S_{j-1}$ и $S_j$, то есть от того, где начинается и где кончается $j$-я ступенка; обозначим ее через $g(S_{j-1}, S_j)$. Пусть $f_j(S_j)$ — минимальная площадь для лестницы из $S_j$ ступенек, заменяемой на $j$ ступенек, а $f_{j-1}(S_{j-1})$ минимальная площадь лестницы из $S_{j-1}$-й ступенек, заменяемой на $j-1$ ступенек. Установим зависимость между этим величины, то есть найдем такие значения переменных $S_j$, которые дают наименьшее значение добавочной площади:

$$g(S_1, S_2) + g(S_2, S_3) + \dots + g(S_{n-1}, S_n), \quad S_n = N.$$

Введем функцию

$$f_j(S_j) = \min \left[ g(S_1, S_2) + \dots + g(S_{j-1}, S_j) \right],$$

где $j=1, 2, \dots, n$. Заметим, что $g(S_{j-1}, S_j)$ не зависит от $S_1, \dots, S_{j-2}$. Следовательно, $g(S_{j-1}, S_j)$ можно вывести за знак минимизации по $S_1, S_2, \dots, S_{j-2}$ (анаалогично тому, как способит по оси $OY$ парабoly — самая низкая точка парабoly от этого не изменится):

$$f_j(S_j) = \min \left\{ g(S_{j-1}, S_j) + \min \left[ g(S_1, S_2), \dots, g(S_{j-2}, S_{j-1}) \right] \right\}.$$

Но второй член в формулы скобках мы обозначили через $f_{j-1}(S_{j-1})$. Отсюда получаем

$$f_f(S_f) = \min \left\{ g(S_{j-1}, S_f) + f_{j-1}(S_{j-1}) \right\}.$$

Это и есть уравнение Р. Беллана, которое лежит в основе динамического программирования. Вместитель в проведении численные выкладки, и вы увидите, что мы получаем им

11

На каждом шаге. Его нужно понимать так: для отыскания минимума следует придавать $S_j$ все возможные значения, начняя с 1, и для каждого найти и заполнить значение $S_{j-1}$, доставляющей наименьшую величины $f_j(S_j)$. А затем, doitя до последнего значения $j=n$, нужно, «пятясь», вернуть назад и найти все оптимальные значения $S_j$.

Осыужение метода и немного истории

Обратим внимание на то, что в описанном методе не накладывается никаких условий на вид функции $g(S_{j-1}, S_j)$. Этим динамическое программрование выгодно отличаться от линейного *), в котором требуется, чтобы все рассматриваемые зависимости были линейными и переменные изменялись непрерывно. Поэтому уравнение Р. Беллана и вышеописанный метод использовался сейчас очень широко. Но, разумеется, не для удовлетворения прихотей фараонов. Попробуйте без него найти оптимальное соответствие весов ступеней космической ракеты, определять наилучший приципп унификации деталей, построить расписание, в котором было бы меньше всего простое! Вы очиститесь в отчаянном положении казначей, снищero перед обилем возможных вариантов. Разумеется, bruchnу с помощью динамического программрования почти

*) См., например, статью: А. В. Като к, Экономика и линейные нераваенства, «Квант» №№ 3, 4, 1971.

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

Идея метода динамического программрования витала уже давно. В какой-то мере ее применял еще К. Маклорен (1698—1746). Однако окончательно оформился она в работах американского математика Р. Беллана и связьается с его именем.

Мы здесь показали применение динамического программрования к весы простой задаче. Сразу же возникает мысль: а насоклько применим этот метод к задачам более сложным? На него нужно ответить с известной осторожностью. Дело в том, что при этом возникает спецификация трудность, которое называли «проклятем размерности». Приходится перебрать так много разных возможностей и запоминать столько результатов, что метод теряет свои положительные черты.

Еще одно приложение

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

— Государь! Подходит подкрепление кочевников! Мы гибнем!

— Придется отступать. Нам нужно посмотреть его перейти, — со стоном выдавил фараон, глаза на карту. — Но каким путем нам пойти? Скажты! Ты искусен в вычислениях и уже однажды помог мне, — обратился он к казначей.

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

— Я им не верю. Эти глупцы предрекали мне победу.

«Теперь я пропал»,— подумал казначей, вглядываясь в карту (рис. 7).

12

Рис. 7. Извания пунктов заменены цифрами в кружках, а числа между ними показывают длины переходов в днях.

Внезапно его осенило: «А ведь ход мысленей жреца можно использовать и здесь!»

Рассмотрим сначала путь от места битвы 1 к ближайшим пунктом 2, 3 и 4, номера которых мы будем писать в каждом кружочке слева (рис. 8), а справа покажем длины путь (красным цветом). Например, чтобы достигнуть пункта 4 нужно 8 дней.

Тепер рассмотрим все путь из пунктов 2, 3, 4, не обращая внимание на пункт 1 (рис. 9). Некоторые путь уже привели к целю. Так, в пункте 5 привели два путь. Оставим лучший из них (он занял 18 дней), а худший исключим, пометив его знаком «минус». Одновременно исключим путь в пункт 7 (он занял 21 день), в пункт 6 (он занял 24 дня) и в пункт 2 (на первом шаге у нас был лучший путь за 2 дня). Осталось проверить всего 3 пункта: 3, 4, 5.

Аналіз рисуна 10 дает, что лучший путь занimaет 16 дней и ведет через пункты 2, 3, 5.

Заметим, что на последнем этапе казначей уже не интересовался, каким образом армия попала в пункты 3, 4 (сравните с задачей о лестнице!). То есть дальнейший наилучший путь не зависит от того, как мы оказылись в каком-либо пункте. Это общее правило носит название «причина оптимальности» и лежит в основе дианического программирования.

Упражнения

1. Для школьной мастерской решили сначала купить 9 разных токарных станков стойностью 10, 20, 40, 60, 75, 100, 130, 160,