Шаг 2.
Динамическое программирование.
Этапы построение алгоритма задач, решаемых методом динамического программирования

    На этом шаге мы рассмотрим этапы построение алгоритма задач, решаемых методом динамического программирования.

    В предыдущем шаге было дано понятие динамического программирования. Но как же строится алгоритм задачи, решаемой этим методом? Как раз этот шаг и посвящен этой проблеме.

Этапы построение алгоритма задач, решаемых методом динамического программирования

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

    Основную часть работы составляют шаги 1-3. Если нас интересует только оптимальное значение параметра, шаг 4 не нужен. Если же шаг 4 необходим, для построения оптимального решения иногда приходится получать и хранить дополнительную информацию в процессе выполнения шага 3.

    На следующем шаге мы рассмотрим вероятностное динамическое программирование.




Предыдущий шаг Содержание Следующий шаг