На этом шаге мы определим понятие "динамическое программирование".
В настоящее время существует достаточно много задач, которые требуют перебора большого количества (а то и всех) комбинаций данных для выбора оптимального решения. Такие задачи очень трудоемки для памяти персонального компьютера, поэтому существуют методы ограниченного перебора (оптимизация решения задачи в процессе решения). К таким методам относят, например, метод «разделяй и властвуй». Такой алгоритм разделяет задачу на более мелкие подзадачи, а затем собирает решение основной задачи «снизу вверх». Этот метод применим только в случаях, когда подзадачи являются независимыми. Если подзадачи будут взаимозависимыми, то алгоритм «разделяй и властвуй» будет делать лишнюю работу, решая одни и те же подзадачи по несколько раз. В таких случаях применяется метод динамического программирования.
Метод динамического программирования - один из наиболее мощных и широко известных математических методов современной теории управления, был предложен в конце 50-х годов американским математиком Р. Беллманом(Динамическое программирование. М: Издательство. иностр. лит., 1960) и быстро получил широкое распространение, чему способствовали ярко и доходчиво написанные книги самого Беллмана, которые были быстро переведены на русский язык. Вскоре стало ясно, что метод динамического программирования тесно связан с классическим методом Гамильтона-Якоби в аналитической механике (для систем с непрерывным временем) и с последовательным анализом Вальда (для систем с дискретным временем). Однако формулировка метода динамического программирования, данная Беллманом, а также многочисленные приложения метода к разнообразным проблемам теории принятия решения, экономики, экологии и других областей знания способствовали закреплению этого метода как одного из важнейших инструментов теории управляемых процессов.
Динамическое программирование определяет оптимальное решение n-мерной задачи путем ее декомпозиции на n этапов, каждый из которых представляет собой подзадачу относительно одной переменной.
Вычислительное преимущество такого подхода состоит в том, что занимаются решением одномерных оптимизационных задач подзадач вместо большой n-мерной задачи, а затем собираем решение основной задачи «снизу вверх». Динамическое программирование применимо тогда, когда подзадачи не являются независимыми, иными словами, когда у подзадач есть общие «подподзадачи». Алгоритм, основанный на динамическом программировании, решает каждую из подзадач единожды и запоминает ответы в специальной таблице. Это позволяет не вычислять заново ответ к уже встречавшейся подзадаче.
В типичном случае динамическое программирование применяется к задачам оптимизации (optimization problems). У такой задачи может быть много возможных решений; их «качество» определяется значением какого-то параметра, и требуется выбрать оптимальное решение, при котором значение параметра будет минимальным или максимальным (в зависимости от постановки задачи). Вообще говоря, оптимум может достигаться для нескольких разных решений.
Автор динамического программирования Р. Беллман сформулировал принцип оптимальности:
Каково бы ни было начальное состояние на любом шаге и решение, выбранное на этом шаге, последующие решения должны выбираться оптимальными относительно состояния, к которому придет система в конце данного шага [1].
Использование этого принципа гарантирует, что решение, выбранное на любом шаге, является не локально лучшим, а лучшим с точки зрения задачи в целом.
Данный метод усовершенствует решение задач, решаемых, например, с помощью рекурсий или
перебора вариантов.
(1)Статья "Динамическое программирование и жадные алгоритмы" (http://kitnet.altnet.ru/www/metod/ book3/doc1/str1.htm)
На следующем шаге мы рассмотрим этапы построение алгоритма задач, решаемых методом динамического программирования.
