НОВОСТИ   БИБЛИОТЕКА   ЮМОР   КАРТА САЙТА   ССЫЛКИ   О САЙТЕ  




предыдущая главасодержаниеследующая глава

14-8. Эффективность динамического программирования

Постараемся оценить объем направленного перебора при динамическом программировании и сравнить его с прямым перебором. В общей одномерной задаче распределения ресурсов для n отраслей при прямом переборе число вариантов

T=mn;

где m - число дискретных значений, которые могут принимать xi; n - число переменных (отраслей). Если n=2, m=3, т. е. x1(a1, a2, a3), x2(b1, b2, b3), то возможных комбинаций, которые необходимо проверить при прямом переборе, будет a1b1, a1b2, a1b3, a2b1, a2b2, a2b3, a3b1, a3b2, a3b3 - всего 9=32.

Точную формулу для числа перебираемых вариантов при динамическом программировании написать не удается, так как в каждой задаче она своя. Однако можно утверждать, что зависимость числа вариантов от n не экспоненциальная, а примерно линейная.

Для ориентации рассмотрим задачу нелинейного целочисленного программирования в виде


причем ; aj>0; x≥0(xj- целые числа); j=1,.., n.

Для простоты положим aj=1. При определении максимума F необходимо вычислить значения fj(xj) для каждого из b+1 значений, которые может принимать xj. Найдем нижнюю границу числа набора целых значений xj, удовлетворяющих условию


т. е. вместо неравенства рассмотрим строгое равенство. Для случая прямого перебора искомое количество равно числу способов, которыми

можно разместить, например, b одинаковых шаров в n урн. Это число равно числу сочетаний из n+b-1 по b, т. е.


Для N=5 и b=20 получим:


Это означает, что при прямом переборе необходимо вычислить значения F для 10 626 различных комбинаций значений xi. Теперь оценим объем вычислений при направленном переборе в случае динамического программирования. Для определения значений функции Беллмана Sk(х) при заданном х необходимо выполнить х+1 вычисление. Чтобы построить всю таблицу значений функции Sk(x), необходимо осуществить вычисления в количестве


откуда для подсчета всех необходимых значений -k1 функций Sk(х) потребуется


вычислений. Для последней функции Sk требуется найти ее значение Sk(b). Поэтому здесь необходимо вычислить только b+1 значение. Таким образом, общее число вычислений при динамическом программировании определяется формулой


которое при n=5 и b=20 равно 945, что составляет примерно 10% от объема 10 626 вычислений при прямом переборе.

При решении непрерывных задач отыскания экстремума с помощью динамического программирования встает еще проблема интерполяции промежуточных значений функции Sn-1 для подсчета значений Sn в соответствии с функциональным уравнением Беллмана


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

предыдущая главасодержаниеследующая глава








© Злыгостев А.С., 2001-2019
При использовании материалов сайта активная ссылка обязательна:
http://informaticslib.ru/ 'Библиотека по информатике'
Рейтинг@Mail.ru
Поможем с курсовой, контрольной, дипломной
1500+ квалифицированных специалистов готовы вам помочь