русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Понятия о динамическом программировании


Дата добавления: 2013-12-23; просмотров: 803; Нарушение авторских прав


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

Пусть эффективность операции характеризуется критерием W, который будем называть "выигрышем". Предположим, что W за всю операцию складывается из выигрышей на отдельных шагах:

m

W =wi, (7.28)

i=1

где wi - выигрыш на i-ом шаге. Если W обладает таким свойством, то его называют "аддитивным критерием".

Операция представляет собой управляемый процесс, складывающийся из совокупности управлений на каждом шаге, то есть Х= (х1,х2,..., xm). Требуется найти такое управление Х, при котором выигрыш W обращается в максимум, т.е.:

m

W =wi → max. (7.29)

i=1

То управление Х°, при котором этот максимум достигается, будем называть оптимальным управлением. Оптимальное управление состоит из совокупности оптимальных пошаговых управлений: Х° = (х1°, х2°,..., хm°).

Любую пошаговую задачу можно решать различными путями:

· искать сразу все элементы решения на всех m шагах;

· строить оптимальное управление шаг за шагом, на каждом этапе оптимизируя только один шаг. Именно этот вариант нашел наибольшее применение, поэтому, далее, он и рассматривается.

Осваивая метод динамического пошагового программирования, важно понять четыре основных момента:

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

2. Управление на i-ом шаге выбирается не так, чтобы выигрыш именно на данном шаге был максимален, а так, чтобы была максимальна сумма выигрышей на всех оставшихся до конца шагах плюс данный. Исключением является лишь последний шаг;



3. Нахождение частных пошаговых оптимальных решений начинается с последнего шага и завершается на первом;

4. Суммарный выигрыш в целом за операцию определяется после предыдущего пункта путем суммирования пошаговых выигрышей, начиная от первого шага и завершая последним.

Задача "о прокладке наивыгоднейшего пути". Пусть необходимо соорудить путь между двумя пунктами А и Б, причем любой путь из А в В возможен по ломанной линии, отрезки которой параллельны одной из координатных осей. Затраты на сооружение каждого из таких отрезков известны. Требуется проложить такой маршрут, при котором суммарные затраты минимальны.

Прямой перебор вариантов при большом числе отрезков физически неосуществим. Поэтому ищутся пошаговые решения начиная от пункта А к пункту Б. Последовательно "пятясь" вычисляются оптимальный выигрыш и в соответствии с ним, - трасса искомого маршрута.

Задача "о загрузке автомобиля". Пусть имеется набор предметов (каждый в единственном экземпляре); известны их веса q1,q2,..., qn и стоимости c1,c2,..., cn. Грузоподъемность автомобиля равна Q. Требуется определить - какие из предметов нужно взять в автомобиль, чтобы их суммарная стоимость (при суммарном весе ≤ Q) была максимальна.

Процесс загрузки автомобиля представим себе как бы состоящим из n шагов; на каждом шаге мы отвечаем на вопрос: брать данный предмет в машину или не брать? Управление на i-ом шаге равно 1 если мы данный (i-ый) предмет берем, и 0 - если не берем.

Состояние системы перед очередным шагом будем характеризовать весом S, который еще остался в нашем распоряжении после того, как предыдущие шаги выполнены (какие то предметы загружены в машину). Для каждого из значений S мы должны найти Wi(S) - суммарную максимальную стоимость предметов, которыми можно "догрузить" машину при данном значении S, и положить xi = 1, если мы данный i-ый предмет берем в автомобиль, и xi = 0, если не берем.

Сказанное проиллюстрируем числовым примером: имеется 6 предметов, веса и стоимости которых представлены в таблице 7.5. Суммарная грузоподъемность машины Q = 35 единиц веса. Требуется указать номера предметов, которые нужно включить в груз, чтобы их суммарная стоимость была максимальна.

 

Таблица 7.5

Номер предмета
Вес qi Стоимость сi

 

Результаты условной оптимизации решения показаны в таблице 7.6, где в каждой строке для соответствующего номера шага (номера предмета) приведены:

· - условное оптимальное управление xi (0 или 1);

· - условный оптимальный выигрыш Wi (стоимость всех оставшихся предметов при оптимальном управлении на всех шагах).

Из таблицы 7.6 следует, что оптимальный выигрыш = 57 достигается при следующих пошаговых управлениях: x1°= 0, x2°= 1, x3° = 0, x4° = 1, x5° = 1, x6° = 0 (т.е. загрузить автомобиль надо предметами 2, 4 и 5, суммарный вес которых 35 единиц).

 

Таблица 7.6

S i = 6 i = 5 i = 4 i = 3 i= 2 i =1
xi Wi xi Wi xi Wi xi Wi xi Wi xi Wi
  0°  

 

Способ формирования таблицы 7.6 здесь не раскрывается, однако он понятен из логики динамического программирования. Таблица заполняется слева направо, сверху вниз. В правых двух столбцах заполнена только одна строка, так как состояние системы перед началом первого шага нам в точности известно. Оптимальные решения в таблице помечены значком "°".

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

Ниже перечислены основные этапы и практические рекомендации начинающим исследователям при постановке и решении задач динамического программирования.

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

2. Расчленить операцию на этапы (шаги).

3. Выяснить набор шаговых управлений xi для каждого шага и налагаемые на них ограничения.

4. Определить, какой выигрыш приносит на i-ом шаге управление xi, если перед этим система была в состоянии S, то есть записать "функции выигрыша":

 

wi=fi(S,xi). (7.30)

 

5. Определить, как изменяется состояние S системы под влиянием управления xi на i-ом шаге: оно переходит в новое состояние:

 

S'=fi(S,xi). (7.31)

 

6. Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш Wi(S)(начиная с i-го шага и до конца) через уже известную функцию Wi+1(S):

 

Wi(S) =max{fi(S,xi) +Wi+1 [fi(S,xi)]}. (7.32)

xi

Этому выигрышу соответствует условное оптимальное управление на i-ом шаге xi(S)(подчеркнем, что в уже известную функцию Wi+1(S) надо вместо S подставить измененное состояние S' =fi(S,xi)).

7. Произвести условную оптимизацию последнего (m-го) шага, задаваясь гаммой состояний S, на которых можно за один шаг дойти до конечного состояния, вычисляя для каждого из них условный оптимальный выигрыш по формуле:

 

Wm(S) =max{fm(S,xm)}, (7.33)

xm

и находя условное оптимальное управление xm(S), для которого этот максимум достигается.

8. Произвести условную оптимизацию (m- 1)-го, (m- 2)-го и так далее шагов по формуле (7.32), полагая в ней i= (m- 1), (m- 2),... и для каждого из шагов указать условное оптимальное управление xi(S), при котором максимум достигается. Заметим, что если состояние системы в начальный момент известно (а это обычно бывает так), то на первом шаге варьировать состояние системы не нужно - прямо находим оптимальный выигрыш для данного начального состояния So. Это и есть оптимальный выигрыш за всю операцию =W1(So).

9. Произвести безусловную оптимизацию управления, читая соответствующие рекомендации на каждом шаге. Взять найденное оптимальное управление на первом шаге x1°=x1(So); изменить состояние системы по формуле (6.31); для вновь найденного состояния найти оптимальное управление на втором шаге x2° и т.д. до конца.

10. Перечисленные рекомендации пригодны не только для аддитивных критериев, но и для так называемых мультипликативных критериев, выражаемых формулой:

m

Ww i

i=1

(если только выигрыши wi положительны). В таких задачах в основном уравнении (6.32) вместо знака "+" надо ставить знак "умножить", т.е:

Wi(S) =max{fi(S,xi)·Wi+1[fi(S,xi)]}.

хi

 

 




<== предыдущая лекция | следующая лекция ==>
Графическое решение задач линейного программирования | Основные понятия теории игр


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.054 сек.