В чем заключается метод динамического программирования для анализа маршрутов?

Метод динамического программирования для анализа маршрутов заключается в разбиении сложных задач на более простые подзадачи. elar.urfu.ru progress-human.com При объединении решений подзадач получается решение первоначальной задачи. progress-human.com

В основе метода лежит принцип оптимальности Беллмана: каково бы ни было начальное состояние системы перед очередным шагом, управление на этом этапе выбирается так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным. scienceforum.ru Иными словами, оптимальная стратегия зависит только от текущего состояния и цели, и не зависит от предыстории. scienceforum.ru

Вычислительная схема метода динамического программирования состоит из двух процедур: scienceforum.ru

1. Условная оптимизация осуществляется в результате попятного движения от последнего шага исследуемого явления к его первому шагу. scienceforum.ru В процессе этого движения находятся шаговые условно-оптимальные управления. scienceforum.ru
2. Безусловная оптимизация осуществляется в процессе движения в прямом направлении от первого шага к последнему. scienceforum.ru При этом из найденных ранее шаговых условно-оптимальных управлений формируется безусловное оптимальное управление всем данным процессом. scienceforum.ru

Математический аппарат динамического программирования, основанный на пошаговой оптимизации, может быть использован при нахождении кратчайших расстояний, например, на географической карте, представленной в виде транспортной сети. scienceforum.ru