Динамическое программирование (Динамическое планирование), страница 4

Пример. Задача о рюкзаке. Итак, максимальная стоимость V(4,5)=37. Мы можем найти состав оптимального подмножества, отслеживая вычисления этого элемента таблицы. Поскольку V(4,5)≠V(3,5), предмет 4 был включен в оптимальное решение вместе с оптимальным подмножеством, заполняющим оставшиеся 5-2=3 единицы емкости рюкзака. Последние представлены элементом V(3,3). Поскольку V(3,3)=V(2,3), элемент 3 не является частью оптимального подмножества. Далее, так как V(2,3)≠V(1,3), предмет 2 также является частью оптимального выбора, после чего элемент V(1,3-1) остается в качестве определения оставшейся части подмножества.

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

Пример. Задача о рюкзаке. Аналогично, так как V(1,2) ≠ V(0,2), делаем вывод, что предмет 1 является последней частью оптимального решения, которое представляет собой множество {Предмет 1, Предмет 2, Предмет 4}. Как временная, так и пространственная эффективность данного алгоритма равна Θ(n*W). Время, требующееся для поиска состава оптимального подмножества, равно Θ(n+W).

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

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

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

Неприятной стороной такого подхода является то, что решения ряда задач меньшего размера могут быть не нужны для получения решения исходной задачи. Поскольку нисходящий подход лишен этого недостатка, представляется естественным попытаться объединить сильные стороны нисходящего и восходящего подходов. Цель заключается в том, чтобы получить метод, который позволяет решать только необходимые подзадачи и только один раз. Такой метод существует, он основан на функциях с запоминанием (memory functions).

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

Этот метод решает поставленную задачу в нисходящем направлении, но, кроме того, поддерживает таблицу такого же вида, как и используемые в восходящих алгоритмах динамического программирования. Изначально все записи таблицы инициализируются специальным значением NULL, которое указывает, что данное значение не было вычислено. Затем, когда требуется вычислить новое значение, данный метод сначала проверяет, не было ли оно уже вычислено ранее. Если соответствующая запись в таблице не равна NULL, то из таблицы просто извлекается уже вычисленное значение; в противном случае оно вычисляется при помощи рекуррентного вызова, и полученный результат записывается в таблице.

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

Пример. Задача о рюкзаке. Таблица динамического программирования с использования функций с запоминанием Емкость j i 0 1 2 3 4 5 0 0 0 0 0 0 0 w1=2, v1=12 1 0 0 12 - 12 12 w2=1, v2=10 2 0 - 12 22 - 22 w3=3, v3=20 3 0 - - 22 - 32 w4=2, v4=15 4 0 - - - - 37 Вычислены только 10 из 20 нетривиальных значений. Только одно нетривиальное значение, V(1,2), было повторно выбрано из таблицы.

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

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

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

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