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

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

1. Прокладка наивыгоднейшего пути между двумя пунктами. Вспомним задачу 4 предыдущего параграфа и решим ее до конца в крайне (и намеренно) упрощенных условиях. Нам нужно соорудить путь, соединяющий два пункта А и В, из которых второй лежит к северо-востоку от первого. Для простоты допустим, что прокладка пути состоит из ряда шагов, и на каждом шаге мы можем двигаться либо строго на восток, либо строго на север; любой путь из А в В представляет собой ступенчатую ломаную линию, отрезки которой параллельны одной из координатных осей (рис. 8). Затраты на сооружение каждого из таких отрезков известны. Требуется проложить такой путь из А в В, при котором суммарные затраты минимальны.

Рис. 8

Как это сделать? Можно поступить одним из двух способов: либо перебрать все возможные варианты пути и выбрать тот, на котором затраты минимальны (а при большом числе отрезков это очень и очень трудно!); либо разделить процесс перехода из А в В на отдельные шаги (один шаг – один отрезок) и оптимизировать управление по шагам. Оказывается, второй способ несравненно удобнее! Тут, как и везде в исследовании операций, сказываются преимущества целенаправленного, организованного поиска решения перед наивным "слепым" перебором.

Продемонстрируем, как это делается, на конкретном примере. Разделим расстояние от А до В в восточном направлении, скажем, на 7 частей, а в северном – на 5 частей (в принципе дробление может быть сколь угодно мелким). Тогда любой путь из А в В состоит из т = 7 + 5 = 12 отрезков, направленных на восток или на север (рис. 9). Проставим на каждом из отрезков число, выражающее (в каких-то условных единицах) стоимость прокладки пути по этому отрезку. Требуется выбрать такой путь из А в В, для которого сумма чисел, стоящих на отрезках, минимальна.

Рис. 9

Будем рассматривать сооружаемый путь как управляемую систему S, перемещающуюся под влиянием управления из начального состояния А в конечное В. Состояние этой системы перед началом каждого шага будет характеризоваться двумя координатами: восточной х и северной у, обе – целочисленные (0х7, 0у5). Для каждого из состояний системы (узловой точки прямоугольной сетки на рис. 9) мы должны найти условное оптимальное управление: идти нам из этой точки на север (управление с) или на восток (управление в). Выбирается это управление так, чтобы стоимость всех оставшихся до конца шагов (включая данный) была минимальна. Эту стоимость мы по-прежнему будем называть "условным оптимальным выигрышем" (хотя в данном случае это не "выигрыш", а "проигрыш") для данного состояния системы S перед началом очередного шага.

Процедуру условной оптимизации будем разворачивать в обратном направлении – от конца к началу. Прежде всего произведем условную оптимизацию последнего, 12-го шага. Рассмотрим отдельно правый верхний угол нашей прямоугольной сетки (рис. 5). Где мы можем находиться после 11-го шага? Только там, откуда за один (последний) шаг можно попасть в В, т.е. в одной из точек В₁ или В₂. Если мы находимся в точке В₁, у нас нет выбора (управление вынужденное): надо идти на восток, и это обойдется нам в 10 единиц. Запишем это число 10 в кружке у точки В₁, а оптимальное управление покажем короткой стрелкой, исходящей из В₁ и направленной на восток. Для точки В₂ управление тоже вынужденное (север), расход до конца равен 14, мы его запишем в кружке у точки В₂. Таким образом, условная оптимизация последнего шага сделана, и условный оптимальный выигрыш для каждой из точекВ₁, В₂ найден и записан в соответствующем кружке.

Рис. 10

Рис. 11

Теперь давайте оптимизировать предпоследний (11-й) шаг. После предпоследнего (10-го) шага мы могли оказаться в одной из точек С₁, С₂, С₃ (рис. 6). Найдем для каждой из них условное оптимальное управление и условный оптимальный выигрыш. Для точки С₁ управление вынужденное: идти на восток; обойдется это нам до конца в 21 единицу (11 на данном шаге, плюс 10, записанных в кружке при B₁). Число 21 записываем в кружке при точке С₁. Для точкиС₂ управление уже не вынужденное: мы можем идти как на восток, так и на север. В первом случае мы затратим на данном шаге 14 единиц и от В₂ до конца – еще 14, всего 28 единиц. Если пойдем на север, затратим 13 + 10, всего 23 единицы. Значит, условное оптимальное управление в точке С₂ – идти на север (отмечаем это стрелкой, а число 23 записываем в кружке у С₂). Для точки С₃ управление снова вынужденное (с), обойдется это до конца в 22 единицы (ставим стрелку на север, число 22 записываем в кружке при С₃).

Рис. 12

Аналогично, "пятясь" от предпоследнего шага назад, найдем для каждой точки с целочисленными координатами условное оптимальное управление (с или в), которое обозначим стрелкой, и условный оптимальный выигрыш (расход до конца пути), который запишем в кружке. Вычисляется он так: расход на данном шаге складывается с уже оптимизированным расходом, записанным в кружке, куда ведет стрелка. Таким образом, на каждом шаге мы оптимизируем только этот шаг, а следующие за ним – уже оптимизированы. Конечный результат процедуры оптимизации показан на рис. 12.