Если выбирать оптимальное управление на первом шаге, то
необходимо предвидеть все его последствия на последующих шагах.
Поэтому описание алгоритма метода динамического программирования
часто начинают с описания выбора управления на последнем шаге,
ведущем в одно из завершающих процесс состояний. При этом ссылаются
на «педагогическую практику», которая свидетельствует, что аргументация
при описании алгоритма от завершающего состояния к начальному
состоянию легче воспринимается, поскольку опирается на как бы уже
сложившиеся к началу рассматриваемого шага условия, в то время как
возможные завершения процесса также определены.
???? Рис. 5. К существу метода динамического программирования.
Анализ переходов.
В соответствии с этим на рис. 5 анализируются возможные переходы в
завершающее множество состояний «3» из каждого возможного состояния
в ему предшествующем множестве состояний «2», будто бы весь
предшествующий путь уже пройден и осталось последним выбором
оптимального шагового управления завершить весь процесс. При этом для
каждого из состояний во множестве «2» определяются всеполные
выигрыши как сумма = «оценка перехода» + «оценка завершающего
состояния». Во множестве «2» из полученных для каждого из состояний, в
нём возможных полных выигрышей, определяется и запоминается
максимальный полный выигрыш и соответствующий ему переход
(фрагмент траектории). Максимальный полный выигрыш для каждого из
состояний во множестве «2» взят в прямоугольную рамку, а
соответствующий ему переход отмечен стрелкой. Таких оптимальных
переходов из одного состояния в другие, которым соответствует одно и то
же значение полного выигрыша, в принципе может оказаться и несколько.
В этом случае все они в методе неразличимы и эквивалентны один другому
в смысле построенного критерия оптимальности выбора траектории в
пространстве параметров, которыми описывается система.
После этого множество «2», предшествовавшее завершающему
процесс множеству «3», можно рассматривать в качестве завершающего,
поскольку известны оценки каждого из его возможных состояний
(максимальные полные выигрыши) и дальнейшая оптимизация
последовательности шаговых управлений и выбор оптимальной траектории
могут быть проведены только на ещё не рассмотренных множествах,
предшествующих множеству «2» в оптимизируемом процессе (т.е. на
множествах «0» и «1»).