1. траектория Adоптимальная, переход совершен оптимальным образом
2. Целевая функция аддитивна, т.е. WAD=wAB+wBC+wCD
Всякий отрезок оптимальной траектории – оптимален.
Оптимизация многошагового процесса:
W(Sn) – эффективность движения из Sn в SN (конечное). Рассчитывают для каждого состояния, двигаясь из конечного в начальное. W(SN)=0, n=N..0. Правило носит название уравнения Беллмана: , Wn=jn(Sn-1,Sn) – шаговый эффект. Задаем Sn-1 и ищем такое Sn в которое нам эффективней двигаться и ищем W(Sn-1). Уравнение Беллмана нужно решать столько раз, сколько N. На каждом шаге столько, сколько состояний.
.