На этом шаге мы рассмотрим этапы построение алгоритма задач,
решаемых методом динамического программирования.
В предыдущем шаге было дано понятие динамического программирования. Но как же строится алгоритм задачи, решаемой этим методом? Как раз этот шаг и посвящен этой проблеме.
Этапы построение алгоритма задач, решаемых методом динамического программирования
- Найти такое разбиение задачи на две или более подзадач, чтобы оптимальное решение задачи содержало оптимальное решение всех подзадач, которые в нее входят.
- Написать рекуррентное соотношение (если разбиваем задачу на подзадачи, значит, можем выразить качество решения задачи либо через ее подзадачи, либо элементарным образом).
- Вычислить оптимальное значение параметра для всей задачи.
- Если необходимо получить не только значение качества оптимального решения, но и найти само решение, то на шаге 3 нужно также запоминать некоторую дополнительную информацию о ходе решения – решение каждой подзадачи. Этот шаг иногда еще называют обратным ходом.
Основную часть работы составляют шаги 1-3. Если нас интересует только оптимальное значение параметра, шаг 4 не нужен. Если же шаг 4 необходим, для построения оптимального решения иногда приходится получать и хранить дополнительную информацию в процессе выполнения шага 3.
На следующем шаге мы рассмотрим вероятностное динамическое программирование.
