Лекция 15. Динамическое программирование

Содержание лекционного занятия:

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

· Многоэтапные процессы принятия решений

· Принцип оптимальности Р. Беллмана

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

Возникновение динамического программирования свя­зано с исследованием многошаговых процессов, возни­кающих в теории создания запасов. Основная идея, кото­рая привела к созданию вычислительного метода, была сформулирована в начале 50-х гг. прошлого века Р. Беллманом (R. Bellman), сделавшим самый большой вклад в развитие метода, который он назвал «динамиче­ское программирование», но который чаще называют просто метод Беллмана.

Метод не является универсальным в отличие, например, от симплекс-метода Данцига для решения задач линейного программирования. Его реализация для каждого конкретно­го многошагового процесса принятия решений, как прави­ло, требует разработки нового алгоритма. Многие практи­ческие задачи, которые можно решать с помощью этого метода, были рассмотрены его автором совместно с Дрей­фусом (S. Dreyfus).

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

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

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

Рис. 12 Задача поиска оптимального пути.

Заданы затраты на каждый из возможных переходов и требуется найти путь с минимальными суммарными за­тратами из левого нижнего угла сетки (рис. 12, точка А) в правый верхний угол (точка В). Такой путь называется оптимальным.

Узлы сетки пронумерованы так, как показано на рис. 12, где тип задают соответственно вертикальный и горизон­тальный размеры сетки.

Затраты на переход в узел i, j по горизонтали (из узла i, j - 1) составляют g_ij, а по вертикали (из узла i - 1, j) – v_ij. В точке А соответствующие величины равны нулю. Таким образом, исходными данными в этой задаче явля­ются: m, n и все шаговые затраты g_ij и v_ij (i = 0, 1, 2,..., m; j = 0, 1, 2,..., п). Всего n (m + 1) чисел g_ij и m (n + 1) чи­сел v_ij, т.е. всего 2mn + m + n переходов и соответствую­щих им затрат.

Следующая идея состоит в том, чтобы из точки А идти в том направлении, которое требует минимальных затрат на первом шаге (первый ход), не думая о затратах на после­дующих шагах, и так в каждой точке. Т.е. рассматривать только затраты на данном шаге и выбирать тот переход, для которого на данном шаге затраты минимальны. Легко убе­диться в ошибочности этой идеи даже при m = n = 1

Поиск оптимального пути можно рассматривать как многошаговый процесс. На первом шаге находимся в точ­ке А и имеем две возможности: пойти вверх или направо. Сделать выбор нельзя, так как нужно учитывать последст­вия этого выбора. При любом выборе, попадем мы в точку (0,1) или (1,0), встанет та же задача выбора из двух возможностей и опять выбор сделать нельзя и т.д. Однако существуют точки, находясь в которых мы не имеем вы­бора. Эти точки С и D находятся в одном шаге от послед­ней точки В и имеют координаты (m, n-1) и (m-1,n) (рис. 13).

Рис. 13. Выбор на последних шагах

Для каждой из этих точек запомним затраты на остав­шийся путь и рассмотрим предпоследний шаг. В двух шагах от финиша мы можем быть в точках Е, F или G. В точках Е и G выбора нет, и мы просто запомним для каж­дой из них суммарные затраты на весь оставшийся путь. На рис. 13 это 10 для точки Е и 8 для точки G. А что де­лать, если мы в двух шагах от финиша окажемся в точке F? Ответ кажется простым: надо идти в точку С, а не в точку D, так как, несмотря на то что на предпоследнем шаге затраты больше (2 против 1), с учетом затрат на ос­тавшийся путь (4 против 7) суммарные затраты на путь До точки В окажутся меньше (6 против 8). Конечно, из точки F надо идти в точку С, но при одном непременном Условии: ничто не может помешать нам это сделать, нет никакой связи с тем, как мы попали в данную точку или, как говорят, нет «предыстории». В нашей задаче такой связи нет, но в более сложных задачах она вполне воз­можна. Например, могло быть задано дополнительное условие: суммарное количество изменений направления (поворотов) не больше заданного числа. Тогда мы, во-первых, должны знать, сколько было сделано поворотов до попадания в точку F и каким образом (по горизонтали или по вертикали), мы попали в эту точку, т.е. должны знать предысторию. Может оказаться, что мы попали в точку F по горизонтали и уже исчерпали заданный «ли­мит» поворотов, тогда переход из точки F в точку С про­сто невозможен, так как это уже лишний поворот. Полу­чается, что сделать оптимальный выбор в точке F нам может помешать предыстория.

Продолжим поиск оптимального пути в нашей задаче, в которой таких осложнений нет, и предыстория не имеет значения. В точке F мы запомним затраты на весь остав­шийся путь при условии, что выбран оптимальный вари­ант: переход в точку С. Сделав еще шаг назад, т.е. ока­завшись за три шага до финиша, мы увидим, что ситуа­ция полностью аналогична предыдущей. Выбора или нет (точки на крайней верхней или крайней правой стороне сетки), или есть две возможности, но для каждой из них уже известны последствия выбора. Так, оказавшись в точке М, мы выберем не точку F, для которой затраты до конца пути равны 6, а казавшуюся бесперспективной точку Е. Для нее эти затраты равны 10, но суммарные затраты на весь оставшийся путь меньше (13 против 14). При этом выборе мы решаем совсем простую задачу: суммируем затраты на каждый из возможных переходов на данном шаге (в точку Е или в точку F) с уже извест­ными затратами на дальнейший путь по оптимальному для выбранной точки варианту. Поступая аналогичным образом, мы рано или поздно в своем обратном движении придем в начальную точку А (рис. 14). Но при этом уже будут известны последствия для каждого из вариан­тов выбора (пойти по вертикали в точку К или по гори­зонтали в точку L), так как для каждой из них уже вы­числены и записаны затраты на весь оставшийся путь до точки В.

Рис. 14. Выбор на первом шаге

Теперь ничто не мешает нам сделать выбор, куда идти из точки А. Просуммируем затраты из А в К с тем, что записа­но для точки К на весь оставшийся путь от К до В. Затем просуммируем затраты из А в L с тем, что записано для L на путь из L в В, выберем наименьшую из сумм, которая и будет равна суммарным затратам по оптимальному пути. В примере на рис. 14 получаем для точки К 99, а для точки L 100, и, следовательно, теперь ясно, что идти надо в точку К. Но нам нужны не только эти минимальные из всех возмож­ных затраты, но и сам оптимальный путь. Пока мы знаем, куда идти из точки А на первом шаге. А дальше? Дальше знаемтолько затраты на весь оставшийся путь. Чтобы неоказаться в такой ситуации неопределенности, при запи­си затрат на оставшийся путь в каждой из промежуточных точек (С, D, E, F, G, М, и т.д. рис. 13) нужно записывать и сделанный выбор: куда идти из этих точек. Когда из точки А выберем точку К или L, в любой из них уже будет записано, куда идти (по вертикали или по горизонтали, т.е. 1 или 0) и т. д. Обратным разворотом мы дойдем до точки В и вос­становим оптимальный путь.

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

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

Принцип оптимальности Р. Беллмана сформулирован для широкого круга задач управления, распределения ре­сурсов, проектирования и др. и вообще задач принятия ре­шений в многошаговых (многоэтапных) процессах. Если задано начальное (точка А) и конечное (точка В) состояния некоторой системы и переход из начального в конечное со­стояние осуществляется в несколько промежуточных эта­пов, на каждом из которых система может находиться в од­ном из различных состояний, и каждому переходу на каж­дом этапе можно сопоставить некоторые затраты, то задача состоит в том, чтобы выбрать такой путь (т.е. все промежу­точные состояния), при котором некоторая количественная оценка этого пути достигает минимума.

Общее условие применимости принципа оптимальности выражается в требовании отсутствия влияния «предысто­рии». Именно поэтому формулировка этого принципа, при­веденная в разделе 2, начинается со слова «если».

Установить возможность применения принципа Р. Беллмана — значит доказать отсутствие влияния «пре­дыстории». Это влияние может возникать при наличии более сложных целевых функций, чем сумма затрат. Мо­жет оказаться, что даже если удается разбить задачу на ряд последовательных этапов, значение целевой функции можно вычислить только при полностью известной траек­тории (полной последовательности переходов системы от начального состояния к конечному).

Вопросы для самоконтроля:

1.Понятие о динамическом программировании(ДП).

2.Постановка задачи ДП.

Рекомендуемая литература:

1.Ашманов С.А. Линейное программирование. —М.: Наука, 1981.

2.Айсагалиев А.С., Айсагалиева С.С. Лекции по методам оптмизации.-Алматы:Гылым,1996