Принцип оптимальности, уравнение Беллмана

1. траектория Adоптимальная, переход совершен оптимальным образом

2. Целевая функция аддитивна, т.е. W_AD=w_AB+w_BC+w_CD

Всякий отрезок оптимальной траектории – оптимален.

Оптимизация многошагового процесса:

W(S_n) – эффективность движения из S_n в S_N (конечное). Рассчитывают для каждого состояния, двигаясь из конечного в начальное. W(S_N)=0, n=N..0. Правило носит название уравнения Беллмана: , W_n=j_n(S_n-1,S_n) – шаговый эффект. Задаем S_n-1 и ищем такое S_n в которое нам эффективней двигаться и ищем W(S_n-1). Уравнение Беллмана нужно решать столько раз, сколько N. На каждом шаге столько, сколько состояний.

.