9.1 Принятие решений в условиях определенности

(Дерево решений в условиях определенности). Суть метода динамического программирования Беллмана. При решении таких задач мы взвешиваем ребра и вершины. Применяем метод динамического программирования Беллмана. Идея метода состоит в следующем: 1. Задача поиска оптимального пути начинается с конца. 2. Исходная задача погружается в множества аналогичных задач с различными начальными вершинами и одной и той же конечной вершиной, при этом предполагается, что в качестве начальной вершины последовательно выступают все без исключения вершины графа. Таким образом в методе Б в каждый момент вр оптимизируется «хвост». Будем продвигаться по графу справа на лево. Взвешивая вершины и указывая оптимальное направление из каждой вершины с помощью одной или нескольких стрелок. Вес каждой вершины будет означать суммарные затраты, которые получаются при движении из вершины выбранной в качестве начальной по оптимальному пути.