Полная версия

Главная arrow Психология arrow Искусство решать сложные задачи. Системный подход

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Динамическое программирование

  • 1. Область применения. Используется для решения задач математического программирования, позволяющих представлять их в виде нескольких менее сложных подзадач с одной целевой функцией, иначе говоря — проводить декомпозицию задачи. Такое представление должно дать возможность провести поэтапное решение на основе рекуррентных процедур (рекуррентными называются процедуры, когда значение целевой функции на одном этапе вычислений определяется с использованием известного значения этой функции, полученного на предыдущем этапе). Требования к виду целевой функции и ограничениям рассматриваются при выборе методов решения частных подзадач.
  • 2. Сущность. Основным принципом, положенным в основу метода динамического программирования, является принцип оптимальности, суть которого заключается в том, что каждое последующее решение строится оптимальным образом независимо от решений, полученных на всех предыдущих этапах, кроме последнего. Чтобы реализовать этот принцип, необходимо в исходной задаче определить: этапы решения (иначе — подзадачи, на которые она декомпозируется); управляемые переменные (или варианты решений) на каждом этапе; информацию для решения задачи на каждом этапе; рекуррентные вычислительные процедуры, связывающие соседние этапы. Проще говоря, в методе динамического программирования искусственно создаются условия для независимой оптимизации на отдельном этапе по результатам только предыдущего, причём с гарантией того, что полученное решение будет находиться в области допустимых решений. Последовательность этапов может устанавливаться произвольно, за исключением случаев порождения подзадач в установленном хронологическом порядке. Первое прохождение этапов может быть как прямым, так и обратным, а методы оптимизации на отдельных этапах могут отличаться друг от друга.
  • 3. Особенности применения. Метод динамического программирования особенно эффективен для задач, условия которых в принципе позволяют составить сетевой график перехода от этапа к этапу, где узлы сети будут соответствовать различным значениям переменных, а дуги — допустимым вариантам решения. Увеличение количества переменных вызывает значительный рост числа возможных вариантов решения для каждого этапа. Это влечёт за собой увеличение не только времени вычислений, но и необходимого объёма памяти компьютера, что является серьёзным препятствием для решения задач динамического программирования уже даже средней размерности.
  • 4. Наиболее употребительные методы. Различают алгоритмы прямой и обратной прогонки в зависимости от направления прохождения этапов при решении задачи. Они могут отличаться друг от друга различным представлением переменной и видом рекуррентных соотношений. Обычно алгоритм обратной прогонки является более эффективным, особенно в задачах с нумерацией в хронологическом порядке. С техникой применения метода динамического программирования можно ознакомиться в /52/.
 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>