Краткая теория. Динамическое программирование – метод оптимизации, приспособленный, к задачам, в которых процесс принятия решения может быть разбит на отдельные этапы (шаги)

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

Характерные особенности задач динамического программирования:

1) Неоднозначность решения.

2) Возможность деления вычислительного процесса на этапы.

3) Общий критерий – сумма частных критериев на этапах.

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

Метод динамического программирования состоит в том, что опти­мальное управление строится постепенно. На каждом этапе оптимизируется управление только этого этапа, причем управление выбирается с учётом последствий, т.е. оптимальное управление для данного этапа должно учитывать весь последующий ход процесса, для чего необходимо знать все управления на последующих этапах. Поскольку процесс заканчивается на последнем этапе, оптимальное решение не должно учитывать последующего управления. Таким образом, процесс вычисления протекает в обратном направлении, от конца к началу.