дома » Квант » Динамическое программирование

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

Динамическое  программирование. М.И.РЕЙТМАН

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

Страница переведена на новый сайт https://myeducation.su/ :

страница ФИЗИКО-МАТЕМАТИЧЕСКИЙ ЖУРНАЛ Квант (1972)

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

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

— Я пробовал, — вздохнул каз-
начей, — но вариантов так много,
а времени в обрез.
— Ладно, друг, — сказал жрец.—
Дай мне подумать, и приходи завтра.
Когда на следующий день убитый
горем казначей приплелся к жрецу,
тот встретил его довольной улыбкой.
— А скажи, друг, могу ли я
рассчитывать на оставшееся золото,
если обойдусь меньшим количеством?
— О боги! — воскликнул казна-
чей, не веря своему счастью. — Ты
получишь еще дюжину рабов и столь-
ко же мер зерна!
— Так-смотри же! — и жрец про-
тянул ему лист папируса, где был дру-
гой проект наращивания лестницы.
— Этот проект требует лишь 171 дмэ
золота. А остальные 29 дм3 — мои!
— Но скажи, о величайший из
вычислителей, как ты нашел такой
вариант? Я пробовал и так и сяк,
но он мне не попадался!
— Слушай же, — молвил жрец.—
Сначала я разобрал случаи, когда
лестницы из разного числа ступенек
заменяются всего одной ступенькой
(рис 2*)). Чтобы числа были попро-
ще, я буду вычислять только пло-
щадь f фигуры между сплошной и
пунктирной линиями, а постоянный
множитель, ширину лестницы, до-
бавлю потом. Не возражаешь? Так
вот, если бы первоначальная лестни-
ца состояла всего из одной ступеньки,
то и наращивать было бы нечего:
/i @-0.
Формула
fr B)= 1,5X3=4,5 дм*
показывает, что лестница заменяется
одной ступенькой, а сначала их было
две (две первые ступеньки лестницы
фараона). Аналогично найдем
/1C)=1,5хЗ+0,7хC+4)=9,4.
Ну а дальше
М4)=9,4+1х C+4+1) = 17,4
/1E)-17,4+1,2хC+4+1+5)=33.
— Все это понятно, — возразил
казначей, — но зачем мне одна сту-
пенька? Ведь фараон просил четыре!
Да и лестница имеет их сейчас не
пять, а куда больше!
— Не торопись! — улыбнулся
жрец. — Пусть теперь новых сту-
пенек станет больше — две. Давай
теперь подсчитаем минимальные пло-
щади при двух ступеньках. f2 A) не
имеет смысла, заменить одну ступень-
ку двумя мы не можем. Чтобы заме-
нить две ступеньки двумя новыми,
наращивать их не придется*.
/. B)=0.
Вот /2 C) подсчитать несколько
сложнее (рис. 3):
/8C)=min{(Ml)+0,7×4),
(/i
•) Жрец рассматривал лестницы лз не-
скольких первых ступенек лестницы фа-
раона.
скобках соответствуют ,о|
двум вариантам: наДо/г!п

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

нарастить или вторую, или первую
ступеньку, а знак mln показывает,
что нужно взять наименьшую из них.
Подставим в фигурные скобки вели-
чины fx{\) и ft B), найденные рань-
ше:
ft О) =
-min {@+0,7×4). D,5+0)}-2,8.
Теперь уже видно, что если в лест-
нице всего три ступеньки, а их число
нужно сократить до двух, то наращи-
вать нужно вторую ступеньку.
— А если бы ступенек было 4?
— Тогда
0,7х4+1хD
<ЫЗ)
(9,4 + 0)} = 5,5,
то есть, если в лестнице было 4 сту-
пеньки, а мы заменяем их двумя, то
первую лучше всего закончить на
второй старой (рис. 4).
— Погоди, я хочу убедиться, что
понял,— прервал его казначей.— Зна-
чит, чтобы найти f2 E), нужно дейст-
вовать так:
М5)-min {@+7,8+1,2 х D+1+5)),
/i B) + 1
= min{@ +
4
X
7,
,5
1
8)
+
>
i
1
4,5+lxl
(9,4+1,2×5), A7,4)} =
A5,4).
min{A9,8),
12,7
A7,4)} = 12,7.
— Воистину, мудрые следят за
казной государства, — польстил
1,5
1
3
2 1
жрец. — А дальше
U F) = min {@ + 19,8 +
+ 1хD+ l + 5
D,5 + 8,2+lx(l+5 + 3)),
(9,4+1,2×5 + 8),
17,4+1×3
, C3 + 0)} =
= min {@ + 32,8), D,5+17,2),
(9,4+14,0),
17,4 + 3
C3 + 0)}- mi n {C2,8), B1,7),
B3,4),
20,4
33} ^ 20,4.
Можно было бы продолжать и найти
}2 G), но в этом нет нужды, как ты
вскоре увидишь. Перейдем теперь к
случаю, когда лестница заменяется
тремя ступеньками.
Начнем с того, что найдем f9 D), то
есть самый разумный вариант нара-
щивания первых четырех ступенек.
Ведь /3 0) и fs B) лишены смысла
(не стоит заменять одну или две сту-
пеньки тремя), a fz C)=0 — нара-
щивание трех ступенек до трех не
требует никакого расхода золота.
Чтобы найти f3 D), посмотрим, где
может кончаться вторая ступенька.
Конечно, или на 2-й, или на 3-й
старой. Значит,
Ы2Н-1Х1
0)}=min{
0+1
B,8 + 0)}= 1.
Следовательно, наращивая 4 сту-
пеньки так, чтобы их стало 3, нужно
окончить новую вторую на второй

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

старой. Двинемся дальше:
/зE) =
= min {(/2 B) + 1 х 1 + 1,2х A + 5)),
(/2C)+ 1.2×5).
«min {@+1-1-7,2). B.8-6),
5.5 + 0
} = 5 5,
(/2C)+ 6+1×8).
/2 D)+1×3
/2 E)-10} «min {@+17,2),
B,8+14),
5,5 + 3
A2,7 + 0)} -8,5.
/3 G) = min {(h B) +17.2 +
+ 0.8 х A+5 + 3 + 4)).
(/2C) + 1.2Х 5 + 1×8 + 9,6),
h D) + 3 + 0.8C + 4)
(/2 E)+ 0.8×4),
<h F) 4-0)}= min {(Or 27.6).
B,8 + 23.6),
5.5 + 8,6
A2.7 + 3,2), B0.4 + 0)} =14,1.
Наконец, как легко подсчитать,
/, (8)=24,3.
Ну а теперь рассмотрим случай
с четырьмя ступенями» Теперь уже
рассматривать /4 D),…,/4 (8) нет нуж-
ды: мы точно знаем, что последняя,
четвертая ступенька кончается на
0,7
1.5
1
3 r
1
CVJ
1
я
\
4
5
,
i
i
старой девятой (иначе бы лестница
имела больше четырех ступенек).
Итак, нам остается найти /4 (9):
/4(9) = min {(/3C)+1,2×5 +
1-1×8 + 0,8х 12 + 1,2 х 16 + 1 X19),
(/3D)+1х3 + 0,8×7 +
1-1.2×11 + 1×14),
(/з E) + 0.8х4+1,2х8 + 1 х 11).
(М6) + К2Х4 + 1X7).
(/3 (8)+ 0)}-min [@ + 61,8),
A+35,8), E.5 + 23.8),
(8.5-11,8).
14.1+3
Рис. 4.
B4,3 + 0)}-17.1.
Значит, всего на лестницу понадобит-
ся 17,1×10=171 (дл8) золота. Л те-
перь давай найдем, где должны рас-
полагаться новые ступеньки. Заме-
тим, что оптимальные варианты всю-
ду взяты в рамку. В последний опти-
мальный вариант вошла стоимость
трех новых ступенек /3 G)—14,1; зна-
чит, третья ступенька должна кон-
чаться на 7-й старой. Теперь вернемся
на шаг назад к определению /3 G)
и увидим, что в /з G) входит стоимость
первых двух ступенек /2 D)=5,5.
Следовательно, вторая ступенька
должна кончаться на 4-й старой. И,
наконец, в выражение для f2 D) вхо-
дит /, B)=4,5. Значит, первую сту-
пеньку новой лестницы нужно окон-
чить на второй ступеньке старой.
Окончательно, самая дешевая лест-
ница изображена на рисунке 5.
Теория динамического
программирования
Мы не знаем, выполнил ли хитро-
умный казначей свое обещание жре-
цу, более того, мы не знаем, случи-
лась ли вообще описанная история
или она вымышлена. Но зато мы зна-
ем, что она вполне могла произойти,
ибо в рассмотренной задаче исполь-
зуются только два арифметических

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

действия — сложение и умножение
(если не считать определения платы
жрецу, где потребовалось вычита-
ние), а они были хорошо известны в
Древнем Египте. Ну и еще немного
используется здравый смысл. А меж-
ду тем здесь применен математиче-
ский аппарат, который получил рас-
пространение лишь лет двадцать на-
зад; он называется динамическим про-
граммированием.
Вдумаемся, почему нам удалось
найти оптимальное решение, не рас-
сматривая всех возможных вариантой
наращивания лестницы (а их очень
много, и для их полного исследова-
ния жрецу действительно не хвати-
ло бы времени). Дело в том, что на
каждом шаге мы разбивали общую
задачу на ряд более простых.
Пусть требуется нарастить лест-
ницу, имеющую Лг ступенек, так,
чтобы она их имела п, где N п, то
есть Л’ намного больше п. Допустим,
что нам уже известно оптимальное
распределение ступенек, когда их в
новой лестнице у, где j^n. Пусть
Sj — номер старой ступеньки, на ко-
торой кончается у-я новая. Очевид-
но, начинается эта /»-я ступенька на
Eу_1+1)-й старой. Добавочная пло-
щадь лестницы, изображенная на ри-
сунке 6 штриховкой, будет зави-
сеть от Sj_i и Sj, то есть от того, где
начинается и где кончается /-я сту-
пенька; обозначим ее через g (S;_,,
Sj). Пусть /;- (Sj) — минимальная
площадь для лестницы из Sj ступенек,
заменяемой на у ступенек, a /;_iEy_,)
минимальная площадь лестницы из
Sj_l-ri ступенек, заменяемой на у—1
ступенек. Установим зависимость
между этими величинами, то есть
найдем такие значения переменных
Sj, которые дают наименьшее зна-
чение добавочной площади:
g(Slt St)+g(Sit S3)+…-r
+g(Sa-i. Sn), Sa=N.
Введем функцию
/,(S,)=min \g(St, 5a)-r-…-r
ss
где
2, Sj.J+gtSj.L Sj)),
/*=1, 2,…, п. Заметим, что
g}y, Sj) не зависит от Slf…,Sj_2.
С1едовательно, g (Sj_lf S-) можно
вынести за знак минимизации по
Si, S2 S;_2 (аналогично тому, как
сносят по оси OY параболу — самая
низкая точка параболы от этого не
изменится):
min
Но второй член в фигурных скоб-
ках мы обозначили через /,-_, (Sy^).
Отсюда получаем
ft(Sj)**min{g(Sj_lt
Это п есть уравнение Р. Беллмана,
которое лежит в основе динамическо-
го программирования. Всмотритесь
в проведенные численные выкладки,
и вы увидите, что мы пользовались им

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

на каждом шаге. Его нужно понимать
так: для отыскания минимума следует
придавать Sj все возможные значе-
ния, начиная с 1, и для каждого най-
ти и запомнить значение 5;-_t, до-
ставляющее наименьшую величину
fj (Sj). А затем, дойдя до последне-
го значения j—n, нужно, «пятясь»,
вернуться назад и найти все опти-
мальные значения S}.

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

Обратим внимание на то, что в
описанном методе не накладывается
никаких условий на вид функций
g (Sj-i> Sj). Этим динамическое
программирование выгодно отлича-
ется от линейного *), в котором тре-
буется, чтобы все рассматриваемые за-
висимости были линейными и пере-
менные изменялись непрерывно. По-
этому уравнение Р. Беллмана и вы-
шеописанный метод используются
сейчас очень широко. Но, разумеет-
ся, не для удовлетворения прихотей
фараонов. Попробуйте без него найти
оптимальное соотношение весов сту-
пеней космической ракеты, опреде-
лить наилучший принцип унифика-
ции деталей, построить расписание,
в котором было бы меньше всего про-
стоев! Вы очутитесь в отчаянном по-
ложении казначея, сникшего перед
обилием возможных вариантов. Ра-
зумеется, вручную с помощью дина-
мического программирования почти
*) См., например, статью: А. Б. К ?-
ток, Экономика и линейные неравенства,
«Квант» ХиМк 3, 4. 1971.
не считают. Зато оно хорошо приспо-
соблено для счета на электронных
вычислительных Машинах, метод лег-
ко программируется и не содержит
всяких «подводных камней», которые,
к сожалению, встречаются в линей-
ном программировании.
Идея метода динамического про-
граммирования витала уже давно.
В какой-то мере ее применял еще
К. Маклорен A698—1746). Однако
окончательно оформилась она в ра-
ботах американского математика Р.
Беллмана и связывается с его именем.
Мы здесь показали применение
динамического программирования к
весьма простои задаче. Сразу же
возникает мысль: а насколько при-
меним этот метод к задачам более
сложным? На него нужно отвечать
с известной осторожностью. Дело в
том, что при этом возникает специфи-
ческая трудность, которую назвали
«проклятием размерности». Прихо-
дится перебирать так много разных
возможностей и запоминать столько
результатов, что метод теряет свои
положительные черты.

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

Звуки битвы то угрожающе нара-
стали, то отдалялись, но было ясно,
что все кончено. В отчаянии сидел
фараон перед своим шатром в окру-
жении понурых придворных. Шата-
ясь, подбежал окровавленный гонец:
— Государь? Подходит подкреп-
ление кочевников! Мы гибнем!
— Придется отступать. Нам нуж-
но поскорее достичь Нила. Они не
посмеют его перейти, — со стоном
выдавил фараон, глядя на карту. —
Но каким путем нам пойти? Скажи
ты! Ты искусен в вычислениях и уже
однажды помог мне, — обратился он
к казначею.
— О, Осирис! — воскликнул каз-
начей. — Но то была совсем другая
задача! А теперь спроси у своих
военачальников!
— Я им не верю. Эти глупцы пред-
рекали мне победу.
«Теперь я пропал»,—подумал каз-
начей, вглядываясь в карту (рис. 7).

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

Рис. 7. Названия пунктов заменены цифрами
в кружках, а числа между ними показывают
дпииы переходов • днях.
Внезапно его осенило: «А ведь ход
мыслей жреца можно использовать и
здесь!»
Рассмотрим сначала пути от места
битвы 1 к ближайшим пунктам 2, 3
и 4, номера которых мы будем писать
в каждом кружочке слева (рис. 8),
а справа покажем длины путей
(красным цветом). Например, что-
бы достигнуть пункта 4 нужно 8
дней.
Теперь рассмотрим все пути из
пунктов 2, 3, 4, не обращая внимания
на пункт 1 (рис. 9). Некоторые пути
уже привели к цели. Так, в пункт 5
привели два пути. Оставим лучший
из них (он занял 18 дней), а худший
исключим, пометив его знаком «ми-
нус». Одновременно исключим путь
в пункт 7 (он занял 21 день), в пункт 6
(он занял 24 дня) и в пункт 2 (на
Рис. 8.
первом шаге у нас был лучший путь
за 2 дня). Осталось проверить всего
3 пункта: 3, 4, о.
Анализ рисунка 10 дает, что луч-
ший путь занимает 16 дней и ведет
через пункты 2, 3, 5.
Заметим, что па последнем этапе
казначей уже не интересовался, ка-
ким образом армия попала в пункты
3, 4 (сравните с задачей о лестнице!).
То есть дальнейший наилучший путь
не зависит от того, как мы оказались
в каком-либо пункте. Это общее пра-
вило носит название «принципа опти-
мальности» и лежит в основе динами-
ческого программирования.

Упражнения

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

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

190 руб. Каждый из последующих станкоп
в этом ряду может заменить любой предыду-
щий, но не наоборот. Например, станок за
100 руб. может обрабатывать те же детали,
которые обрабатывает станок за 40 руб.
Однако директор школы возразил:
— Слишком много типов станков! Нам
будет трудно их обслуживать — ведь для
каждого нужны свои запчасти. Давайте
купим 9 станков, ио всего четырех разных
типов, причем так. чтобы купленные станки
обладали не меньшими возможностями, чем
исходные 9 станков.
— Л какие типы станков мы возьмем?
— Выберем их так, чтобы заплатить
за все 9 станков поменьше. Евгений Ивано-
ннч, вы поможете нам выбрять типы стан-
ков? — обратился он к учителю матема-
тики.
Какие типы станков предложил выбрать
учитель и сколько они стоили?.
2. То, что предложил проделать ди-
ректор в предыдущей задаче, называется
унификацией. Обычно на практике унифи-
кация дает экономическую выгоду. Но как
эту выгоду подсчитать?
Пусть снова имеется 9 станков со стои-
мостями 16, 18, ;9. 22. 23, 24, 24, 28, 33 руб.
Требуется составить из них унифицированные
серии, как это было сделано раньше, считая,
что объединение станков в серии за счет
упрощения обслуживания дает снижение
затрат на серию по следующей таблице:

3. — Ну вот, — сказала Нина старшему
брату Виктору.— Говорила тебе, что не
нужно покупать мороженое! Как теперь
мы доберемся до бабушки? У нас осталось
всего 30 копеек
— Погоди. — возразил Виктор. — Во-
первых, это ты предложила купить моро-
женое. Во-вторых, нам сейчас поможет ди-
намическое программирование. Мы прохо-
дили его в школьном математическом кружке.
И он стал быстро чертить на бумаге
схему маршрутов (рис. 11). Какой путь нужно
избрать Виктору и Нине (ей десять лет),
чтобы попясть к бабушке?
4. Приближался вечер, а Петя еще
не знал, что задано по геометрии. Узнать
это можно, например, у Лены (до ее домя
12 мин), но номера квартиры Петя не знает.
Его знает Вася, но до него 10 мин ходьбы
я еще 6 от Васи до Лены. .Можно пойти к те-
лефону-автомату (это рядом, но там всегда
очередь 3 мин) н позвонить Юре. Но Юра
¦из другого класса, и он может дать только
адреса Лены И1и Зины (она живет в 6 мин
ходьбы от Пети, н только она знает телефон
Лены и может ей позвонить). Хотя нет, это
может еще Саша, который жнвет в 4 мин
от Юры, и Юра знает гле. Есть еще сосед
по парте. Витька, он никогда не знает, что
задано, но ему можно позвонить и попро-
сить сбегать к Лене (от него 8 мин ходьбы
до Лены), а потом позвонить снова. Да.
и еще Зину можно упросить проводить к Люсе
(это займет 5 мин), она тоже знает задание.
Наконец, можно искать Лену, не зная кпар-
тиры (на поиски уйдет 4 мин), или попросить
Витьку позвонить Жене — пусть тот сходит
к Лене (до нее 4 мин) или к Люсе (до нее
6 мин).
Кяк Пете быстрее всего узнать задание,
если считать.что время идет только на ожи-
дание и ходьбу, а все разговоры происходят
мгновенно?

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

 

Статистика


Яндекс.Метрика