Баланс подзадач

При проектировании алгоритмов приходится идти на различные компромиссы. Очевидно, что по мере возможности необходимо сбалансировать вычислительные затраты на выполнение различных частей алгоритма.

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

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

Подобно методу «разделяй и властвуй», динамическое программирование решает задачу, разбивая ее на подзадачи и объединяя их решения. Как мы видели в предыдущем параграфе, алгоритмы типа «разделяй и властвуй» делят задачу на независимые подзадачи, эти подзадачи – на более мелкие подзадачи и т.д., а затем собирают решение основной задачи «снизу вверх». Алгоритм с такой последовательностью действий имеет экспоненциальное время выполнения.

Динамическое программирование применимо тогда, когда задачи не являются независимыми, т.е. когда у подзадач есть общие «подподзадачи».

В этом случае алгоритм типа «разделяй и властвуй» будет делать лишнюю работу, решая одни и те же подзадачи по нескольку раз.

Алгоритм, основанный на динамическом программировании, решает каждую из подзадач единожды и запоминает ответы в специальной таблице.

Это позволяет не вычислять заново ответ уже решавшейся подзадачи.

Поскольку зачастую удается получить лишь полиномиальное число подзадач, и если не решать одни и те же подзадачи, то можно получить алгоритм с полиномиальным временем выполнения.

С точки зрения реализации, иногда бывает проще создать таблицу решений всех подзадач, которые нам когда-либо придется решать. Мы заполняем эту таблицу независимо от того, нужна ли нам на самом деле конкретная подзадача для получения общего решения. Заполнение таблицы подзадач для получения решения определенной задачи получило название динамического программирования, это название происходит из теории управления. Динамическим программированием (в наиболее общей форме) называют процесс пошагового решения задач, когда на каждом шаге выбирается одно решение из множества допустимых (на этом шаге) решений, причем такое, которое оптимизирует заданную целевую функцию или функцию критерия. В основе теории динамического программирования лежит принцип оптимальности Беллмана.

В основном динамическое программирование применяется к задачам оптимизации. У такой задачи может быть много возможных решений, их качество определяется значением какого-то параметра, и требуется выбрать оптимальное решение, при котором значение параметра будет минимальным или максимальным. Вообще говоря, оптимум может достигаться для нескольких разных решений.

Как строится алгоритм, основанный на динамическом программировании?

1. Сначала описывается строение оптимальных решений.

2. Выписывается рекуррентное соотношение, связывающее оптимальные значения параметра для подзадач.

3. Двигаясь снизу вверх, вычисляется оптимальное значение параметра для подзадач.

4. На основе полученной информации строится оптимальное решение.

Формы алгоритма динамического программирования могут быть разными – общей их "темой" является лишь заполняемая таблица и порядок заполнения ее элементов. Рассмотрим несколько примеров, иллюстрирующих этот метод.