Как можно использовать принцип оптимальности в динамическом программировании?

Принцип оптимальности в динамическом программировании позволяет строить оптимальное решение постепенно, шаг за шагом. studizba.com spravochnick.ru На каждом шаге оптимизируется решение только этого шага, но с учётом последствий. studizba.com spravochnick.ru

Принцип оптимальности гласит: каково бы ни было начальное состояние на любом шаге и решение, выбранное на этом шаге, последующие решения должны выбираться оптимальными относительно состояния, к которому придёт система в конце данного шага. studizba.com

Использование этого принципа гарантирует, что решение, выбранное на любом шаге, является не локально лучшим, а лучшим с точки зрения задачи в целом. studizba.com

На основе принципа оптимальности Беллмана строится схема решения многошаговой задачи, которая состоит из двух частей: spravochnick.ru

1. Обратный ход. spravochnick.ru От последнего шага к первому получают множество возможных оптимальных («условно-оптимальных») управлений. spravochnick.ru
2. Прямой ход. spravochnick.ru От известного начального состояния к последнему из полученного множества «условно-оптимальных» управлений составляется искомое оптимальное управление для всего процесса в целом. spravochnick.ru