На этом шаге мы рассмотрим случаи, когда применимо динамическое программирование.
Существует два признака, характерных для задач, решаемых методом динамического программирования:
- Оптимальность для подзадач.
- В задаче имеются перекрывающиеся подзадачи.
Рассмотрим более подробно эти признаки.
Оптимальность для подзадач
При решении оптимизационной задачи с помощью динамического программирования необходимо сначала описать структуру оптимального решения. Будем говорить, что задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит оптимальные решения ее подзадач. Если задача обладает этим свойством, то динамическое программирование может оказаться полезным для ее решения.Как только свойство оптимальности для подзадач установлено, обычно становится ясно, с каким именно множеством подзадач будет иметь дело алгоритм. Например, для задачи о перемножении последовательности матриц подзадачами будут задачи о перемножении кусков этой последовательности.
Перекрывающиеся подзадачи
Второе свойство задач, существенное при использовании динамического программирования, - небольшое число различных подзадач. Благодаря этому при рекурсивном решении задачи многократно выходят на одни и те же подзадачи. В таком случае говорят, что у оптимизационной задачи имеются перекрывающиеся подзадачи. В типичных случаях количество подзадач полиномиально зависит от размера исходных данных.Алгоритмы, основанные на динамическом программировании, используют перекрытие подзадач следующим образом: каждая из подзадач решается только один раз, и ответ заносится в специальную таблицу; когда эта же подзадача встречается снова, программа не тратит время на ее решение, а берет готовый ответ из таблицы.
Таким образом, рассмотрены два признака использования использования динамического
программирования.
На следующем шаге мы рассмотрим динамическое программирование "сверху вниз" и "снизу вверх".
