Динамическое программирование начнем с простого игрового примера. Предположим, что нам нужно соорудить путь, соединяющий два пункта А и В, из которых второй лежит к северо-востоку от первого. Для простоты допустим, что прокладка пути состоит из ряда шагов, и на каждом шаге мы можем двигаться либо строго на восток, либо строго на север; любой путь из А в В представляет собой ступенчатую ломаную линию, отрезки которой параллельны одной из координатных осей (рисунок).
Север В
А Восток
Затраты на сооружение каждого из таких отрезков заранее известны (они разные). Требуется проложить такой путь из отрезка А в В, при котором суммарные затраты минимальны.
Как это сделать? Можно поступить одним из двух способов; либо перебрать все возможные варианты пути, и выбрать тот, на котором затраты минимальны (даже при небольшом числе отрезков это очень трудно – слишком много вариантов); либо разделить процесс перехода из А в В на отдельные шаги (один шаг – один отрезок) и оптимизировать управление по шагам, начиная с последнего. Оказывается, что второй способ гораздо удобнее. Здесь, как и везде в исследовании операций, сказываются преимущества целенаправленного, организованного поиска решения перед «слепым» перебором.
Рассмотрим этот способ решения на примере. Любой путь из А в В состоит из m=7+5=12 отрезков, направленных только на восток или на север. Проставим на каждом из отрезков известное число, выражающее стоимость прокладки пути по этому отрезку (рисунок). Требуется выбрать такой путь из А в В, для которого сумма чисел (затрат), стоящих на всех отрезках пути, минимальна.
Будем рассматривать сооружаемый нами путь как управляемую систему S, перемещающуюся под влиянием управления из начального состояния А в конечное В. Нужно найти оптимальное управление системой. Состояние этой системы перед началом каждого шага будет характеризоваться двумя координатами: восточной (х) и северной (y), обе – целочисленные (0 ≤ х ≤ 7, 0 ≤ y ≤ 5). Для каждого из состояний системы (узловой точки прямоугольной сетки) необходимо найти условное оптимальное управление: идти нам из этой точки на север (управление «с») или на восток (управление «в»). Выбирается это управление так, чтобы стоимость всех оставшихся до конца шагов (включая данный) была минимальна.
Процедуру оптимизации будем разворачивать в обратном направлении – от конца к началу. Прежде всего, произведем оптимизацию последнего 12-го шага. Рассмотрим отдельно правый верхний угол нашей прямоугольной сетки (рисунок).
Где мы можем находиться после 11-го шага? Только там, откуда за 1 (последний) шаг можно попасть в В, то есть в одной из точек В1 или В2. Если мы находимся в точке В1, у нас нет выбора (управление вынужденное): надо идти на восток, и это обойдется нам в 10 единиц (условные оптимальные затраты последнего шага). Запишем это число 10 в кружочке у точки В1, а оптимальное управление покажем короткой стрелкой, исходящей из В1и направленной на восток. Для точки В2 управление тоже вынужденное (север), расход (условные оптимальные затраты) до конца равен 14. Запишем его в кружке у точки В2 со стрелкой. Таким образом, условная оптимизация последнего шага сделана, и условные оптимальные затраты для каждой из двух возможных точек В1 и В2 найдены и записаны в соответствующем кружке (рисунок).
Теперь оптимизируем предпоследний (11-й) шаг. После предпоследнего (10-го) шага мы могли оказаться в одной из точек С1, С2, С3 (рисунок).
Найдем для каждой из них условное оптимальное управление и условные оптимальные затраты. Для точки С1 управление вынужденное: идти на восток; обойдется это нам до конца пути в 21 единицу (11 на данном шаге, плюс 10, записанных в кружке при В1). Число 21 записываем в кружке С1. Для точки С2 управление уже не вынужденное: мы можем идти как на восток, так и на север. В первом случае мы затратим на данном шаге 14 единиц и от В2до конца – еще 14, всего 28 единиц. Если пойдем на север, то затратим 13+10, всего 23 единицы. Значит, если мы в точке С2, то условное оптимальное управление – идти на север (отмечаем это направление стрелкой, а число 23 – условные оптимальные затраты – записываем в кружке у С2). Для точки С3 управление снова вынужденное («с»), обойдется оно до конца пути в 22 единицы (ставим стрелку на север, число 22 записываем в кружке у С3).
Аналогично «пятясь» от предпоследнего шага назад, найдем для каждой точки (всего их 7·5=35 с двумя возможными направлениями в каждой точке) условное оптимальное управление («с» или «в»), которое обозначим стрелкой, и условный оптимальный расход до конца пути, который запишем в кружке. Вычисляется он так: расход на данном шаге складывается с уже оптимизированным будущим расходом, записанным в кружке, куда ведет стрелка. Таким образом, на каждом шаге мы оптимизируем только один шаг, а следующие за ним – уже оптимизированы. Конечный результат процедуры оптимизации показан на рисунке.
Таким образом, условная оптимизация уже выполнена: в какой бы из узловых точек мы ни находились, мы уже знаем, куда идти (стрелка) и во что нам по – минимуму обойдется путь до конца (число в кружке). В том числе, если мы находимся в точке А: в кружке при точке А записан оптимальный расход (цена) на сооружение всего пути из А в В: W*=118.
Теперь остается прочитать безусловное оптимальное управление – траекторию, ведущую из А в В самым дешевым способом. Для этого нужно только «идти по стрелкам». Такая оптимальная траектория отмечена на рисунке дважды обведенными кружками. Соответствующее безусловное оптимальное управление будет:
х*=(с, с, с, с, в, в, с, в, в, в, в, в),
то есть первые четыре шага мы должны сделать на север, следующие два на восток, затем опять один на север, и остальные пять на восток. Задача решена.
Заметим, что в ходе условной оптимизации мы можем столкнуться со случаем, когда оба управления для какой-то точки на плоскости являются оптимальными, то есть приводят к одинаковому расходу средств от этой точки до конца. Например, в точке с координатами (5;1) оба управления «с» и «в» являются оптимальными, то есть дают минимальный расход до конца равный 62. Из них мы произвольно выбираем любое (в нашем случае мы выбрали «с»). Такие случаи неоднозначного выбора оптимального управления постоянно встречаются в динамическом программировании. От выбора одного из них, разумеется, может зависеть оптимальное управление всем процессом, но не оптимальный расход средств.
А теперь вернемся к началу и попробуем решить задачу «наивным» способом, выбирая на каждом шаге, начиная с первого, самое выгодное (для этого шага) направление (если таких два – выбираем любое). Таким способом мы получим управление:
х=(с, с, в, в, в, в, с, в, в, в, с, с).
Подсчитаем расходы для этой траектории. Они будут равны W=10+12+8+10+11+13+15+8+10+9+8+14=128, что, безусловно, больше, чем W*=118. Причина в том, что «шагнув» в очередной раз по самому дешевому отрезку, мы можем попасть в точку, откуда любой следующий шаг и весь оставшийся путь весьма дороги. В данном случае разница не очень велика, но в других она может быть существенной.
В решенной выше задаче условия были намеренно до крайности упрощены. Разумеется, никто не будет вести железнодорожный путь «по ступенькам», перемещаясь только строго на север или строго на восток. Такое упрощение было сделано для того, чтобы в каждой точке выбирать только из двух управлений «с» или «в». Можно было бы вместо двух возможных направлений ввести их несколько и, кроме того, взять шаги помельче; принципиального значения это не имеет. Разумеется, усложняет и удлиняет расчеты, но для ЭВМ подобное усложнение несущественно.
Заметим, что задачи, сходные с рассмотренной выше, очень часто встречаются на практике. Например, при выборе наискорейшего пути между двумя точками или наиболее экономного (в смысле общего расхода горючего) набора заранее определенных скорости и высоты летательным аппаратом.
Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс «проходится» дважды: первый раз – от конца к началу, в результате чего находятся условные оптимальные управления и условные оптимальные выигрыши за оставшийся «хвост» процесса; второй раз – от начала к концу, когда нам остается только «прочитать» уже готовые рекомендации и найти безусловное оптимальное управление х*, состоящее из оптимальных шаговых управлений х1*, х2*,…, хm*.
Рассмотрим ряд типовых задач, где применим метод динамического программирования и которые «внешне» совершенно не похожи на рассмотренный выше пример.
