Задача динамического программирования

Динамическое программирование (ДП) - это вычислительный метод для эффективного решения задач с пересекающимися подзадачами. Возникло и сформировалось в 1950 - 1953 гг. благодаря работам Р. Беллмана.

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

Динамическое программирование решает задачу, разбивая её на подзадачи и объединяя их решения. Рекурсивные алгоритмы также делят задачу на независимые подзадачи, эти подзадачи - на более мелкие подзадачи и так далее, а затеи собирают решение основной задачи «снизу вверх». Динамическое программирование применимо тогда, когда подзадачи не являются независимыми, иными словами, когда у подзадач есть общие «подподзадачи». В этом случае при использовании рекурсии будут решаться одни и те же подзадачи несколько раз. Формы алгоритма динамического программирования могут быть разными - общим для них является заполняемая таблица и порядок формирования ее элементов.

Алгоритм, основанный на динамическом программировании, решает каждую из подзадач только один раз и запоминает ответы в специальной таблице. Это позволяет не вычислять заново ответ к уже встречавшейся подзадаче. Типичными для динамического программирования являются задачи оптимизации. У подобных задач может быть много возможных решений а, их «качество» определяется значением какого-то параметра, и требуется выбрать оптимальное решение, при котором значение параметра будет минимальным или максимальным (в зависимости от постановки задачи). В общем случае, оптимум может достигаться для нескольких разных решений.

В задачах динамического программирования (ДП):

- состояние системы на -ом шаге;

- управление системой на -ом шаге;

(; ) - функция прибыли (или затрат перехода системы из начального состояния в конечное) (некая количественная характеристика).

Исходные данные:

Таблица 3.1 - Таблица стоимостей прокладки участков пути