Задачи динамического программирования,
Допускающие табличное задание рекуррентных соотношений Рассмотрим процесс решения модифицированного варианта задачи (3)-(4), в котором переменные Чтобы не усложнять обозначения, условимся операции целочисленной арифметики записывать стандартным образом, полагая, что промежуточные результаты подвергаются правильному округлению. Так, например, будем считать, что 12/5 = 2. В соответствии с общей схемой вычислительного алгоритма на первом шаге необходимо построить функцию
Поскольку Последняя колонка табл. 5.1 На следующем (втором) шаге приступаем к вычислению функции
где значения берутся из табл. 5.1. В результате вычислений формируется таблица значений
Таблица 5.1
На последующих шагах с номером
Таблица 5.2
На последнем п- омшаге нет необходимости табулировать функцию и т. д. или, в общем виде,
Следует подчеркнуть одно из преимуществ описанного метода с точки зрения его практической реализации в рамках программного обеспечения для ЭВМ: на каждом шаге алгоритма непосредственно используется только таблица, полученная на предыдущем шаге, т. е. нет необходимости сохранять ранее полученные таблицы. Последнее позволяет существенно экономить ресурсы компьютера. Выигрыш, который дает применение рассмотренного алгоритма, может также быть оценен с помощью следующего простого примера. Сравним приблизительно по числу операций (состоящих, в основном, из вычислений целевой функции) описанный метод с прямым перебором допустимых планов задачи (3)-(4) при Количество допустимых планов такой задачи совпадает с количеством целочисленных решений уравнения т. е. равно числу сочетаний с повторениями из п элементов по b. Следовательно, при простом переборе число возможных вариантов составит
В случае применения метода динамического программирования для вычисления таблицы значений функции операций, из чего получаем, что для вычисления всех функций
операций, что при больших п и b существенно меньше, чем в первом случае. Например, если
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|