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

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

На небольшом примере объясним важные идеи динамического программирования, а также введем необходимые условные обозначения.

Пример 2.8.1. Рассмотрим транспортную сеть (задача о кратчайшем маршруте).

10 7

2 12 5 3 1

5 5

10

1 7 4 4

15 7

13 1

Рис.2.8.1. Задача о кратчайшем маршруте.

Пусть с_ij – расстояние (или стоимость переезда) от пункта i в пункт j (на рисунке заданы числами у каждой стрелки). Необходимо выбрать такой путь от пункта 1 до пункта 10, для которого его длина (или общая стоимость переезда) является минимальной.

Из пункта 1 можно переехать в пункт 2, 3 или 4; из пункта 2 в пункт 5 или 6 и т.д. Назовем нахождение в пункте – состоянием системы, переезд из пункта в пункт – процессом перехода из одного состояния в другое. Таким образом, переезд из пункта 1 в пункт 3 есть одношаговый процесс, а скажем, из пункта 1 в пункт 10 – многошаговый процесс перехода из состояния 1 в состояние 10.

Выбор процесса перехода из состояния i в состояние j назовем стратегией. Допустим, мы нашли оптимальный (в данном случае минимальный) маршрут и находимся в его промежуточном пункте, тогда, независимо от пути достижения этого пункта (состояния), оптимальный путь из данного пункта до конечного состояния есть часть общего оптимального пути. Этот принцип оптимальности впервые был сформулирован Р.Беллманом в 1953 г. Приведем этот принцип в формулировке Елены Сергеевны Вентцель[5]:

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

Введем следующие обозначения:

f_n(s) – стоимость, отвечающая стратегии минимальных затрат для пути от состояния s до конечного состояния, если до него остается n шагов;

х _n(s) – решение, позволяющее достичь f_n(s).

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

Вернемся к нашему примеру. Рассмотрим последовательно все состояния от последнего до первого.

Имеемf₀(10)=0 для х ₀(10)= остановка. Затем

f₁(8)=1+0=1 для х ₁(8)=10,

f₁(9)=4+0=4 для х ₁(9)=10. Далее

f₂(5)=min(7+1,5+4)=8 для х ₂(5)=8,

f₂(6)=min(3+1,4+4)=4 для х ₂(6)=8,

f₂(7)=min(7+1,1+4)=5 для х ₂(7)=9.

Для третьего (с конца) шага имеем:

f₃(2)=min(10+8,12+4)=16 для х ₃(2)=6,

f₃(3)=min(5+8,10+4,7+5)=12 для х ₃(3)=7,

f₃(4)=min(15+4,13+5)=18 для х ₃(4)=7.

И, наконец, f₄(1)=min(2+16,5+12,1+18)=17 для х ₄(1)=3.

Мы получили оптимальный путь (наименьшей длины или стоимости) равный 17. Он проходит через события 1-3-7-9-10. (При последовательном рассмотрении всех состояний оптимальные переходы выделялись жирным шрифтом).

Заметим, что на каждом шаге мы пользовались динамическим рекуррентным соотношением:

f_n(s)=min_"(s,j)(с_sj + f_n-1(j)), n=1,2,3,4 (2.8.1)

Очевидно, динамическое программирование здесь более эффективно, чем прямой перебор всех возможных маршрутов, сопровождаемый их оценкой. В данном примере имеется 14 возможных путей; чтобы для каждого определить оценку, придется суммировать четыре числа. Следовательно, для простого перебора потребуется 3´14=42 операции сложения, тогда как мы управились за 16 операций. Преимущество рекуррентного подхода может оказаться огромным при практическом применении, когда полный перебор обычно неосуществим.