Метод динамического программирования для анализа маршрутов заключается в разбиении сложных задач на более простые подзадачи. 35 При объединении решений подзадач получается решение первоначальной задачи. 5

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

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

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

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