Динамическое программирование в теории графов

Динамическое программирование в теории графов

Рассмотренные выше принцип оптимальности и метод ДП решения задач управления многошаговыми процессами допускают ряд важных и естественных обобщений. В рамках стандартных допущений метода ДП — отсутствия последействия и аддитивности целевой функции — одним из главных направлений обобщения является распространение принципа оптимальности и разработка метода ДП для решения задач, формулируемых на основе понятий теории графов. Такие задачи имеют исключительно широкую сферу приложений в экономике, технике и естествознании. В задачах такого типа, как правило, число шагов при переходе из начального состояния в конечное может меняться, так что непосредственное применение классического метода ДП встречает определенные сложности. Изучению соответствующих обобщений принципа оптимальности для задач теории графов и посвящена настоящая глава.