Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Основные идеи динамического программирования





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

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

Пример 2.8.1. Рассмотрим транспортную сеть (задача о кратчайшем маршруте).

10 7

2 12 5 3 1

5 5

10

1 7 4 4

15 7

13 1

Рис.2.8.1. Задача о кратчайшем маршруте.

Пусть сij – расстояние (или стоимость переезда) от пункта i в пункт j (на рисунке заданы числами у каждой стрелки). Необходимо выбрать такой путь от пункта 1 до пункта 10, для которого его длина (или общая стоимость переезда) является минимальной.

Из пункта 1 можно переехать в пункт 2, 3 или 4; из пункта 2 в пункт 5 или 6 и т.д. Назовем нахождение в пункте – состоянием системы, переезд из пункта в пункт – процессом перехода из одного состояния в другое. Таким образом, переезд из пункта 1 в пункт 3 есть одношаговый процесс, а скажем, из пункта 1 в пункт 10 – многошаговый процесс перехода из состояния 1 в состояние 10.

Выбор процесса перехода из состояния i в состояние j назовем стратегией. Допустим, мы нашли оптимальный (в данном случае минимальный) маршрут и находимся в его промежуточном пункте, тогда, независимо от пути достижения этого пункта (состояния), оптимальный путь из данного пункта до конечного состояния есть часть общего оптимального пути. Этот принцип оптимальности впервые был сформулирован Р.Беллманом в 1953 г. Приведем этот принцип в формулировке Елены Сергеевны Вентцель[5]:

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

Введем следующие обозначения:

fn(s) – стоимость, отвечающая стратегии минимальных затрат для пути от состояния s до конечного состояния, если до него остается n шагов;

х n(s) – решение, позволяющее достичь fn(s).

Т.е. х n(s) соответствует пути минимальной длины от состояния s до конечного состояния, которое достигается за n шагов.

Вернемся к нашему примеру. Рассмотрим последовательно все состояния от последнего до первого.

Имеемf0(10)=0 для х 0(10)= остановка. Затем

f1(8)=1+0=1 для х 1(8)=10,

f1(9)=4+0=4 для х 1(9)=10. Далее

f2(5)=min(7+1,5+4)=8 для х 2(5)=8,

f2(6)=min(3+1,4+4)=4 для х 2(6)=8,

f2(7)=min(7+1,1+4)=5 для х 2(7)=9.

Для третьего (с конца) шага имеем:

f3(2)=min(10+8,12+4)=16 для х 3(2)=6,

f3(3)=min(5+8,10+4,7+5)=12 для х 3(3)=7,

f3(4)=min(15+4,13+5)=18 для х 3(4)=7.

И, наконец, f4(1)=min(2+16,5+12,1+18)=17 для х 4(1)=3.

Мы получили оптимальный путь (наименьшей длины или стоимости) равный 17. Он проходит через события 1-3-7-9-10. (При последовательном рассмотрении всех состояний оптимальные переходы выделялись жирным шрифтом).

Заметим, что на каждом шаге мы пользовались динамическим рекуррентным соотношением:

fn(s)=min"(s,j)sj + fn-1(j)), n=1,2,3,4 (2.8.1)

Очевидно, динамическое программирование здесь более эффективно, чем прямой перебор всех возможных маршрутов, сопровождаемый их оценкой. В данном примере имеется 14 возможных путей; чтобы для каждого определить оценку, придется суммировать четыре числа. Следовательно, для простого перебора потребуется 3´14=42 операции сложения, тогда как мы управились за 16 операций. Преимущество рекуррентного подхода может оказаться огромным при практическом применении, когда полный перебор обычно неосуществим.







Дата добавления: 2015-04-16; просмотров: 429. Нарушение авторских прав; Мы поможем в написании вашей работы!




Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...


Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...


Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...


Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

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

Правила наложения мягкой бинтовой повязки 1. Во время наложения повязки больному (раненому) следует придать удобное положение: он должен удобно сидеть или лежать...

ТЕХНИКА ПОСЕВА, МЕТОДЫ ВЫДЕЛЕНИЯ ЧИСТЫХ КУЛЬТУР И КУЛЬТУРАЛЬНЫЕ СВОЙСТВА МИКРООРГАНИЗМОВ. ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА БАКТЕРИЙ Цель занятия. Освоить технику посева микроорганизмов на плотные и жидкие питательные среды и методы выделения чис­тых бактериальных культур. Ознакомить студентов с основными культуральными характеристиками микроорганизмов и методами определения...

Менадиона натрия бисульфит (Викасол) Групповая принадлежность •Синтетический аналог витамина K, жирорастворимый, коагулянт...

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

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

Studopedia.info - Студопедия - 2014-2025 год . (0.008 сек.) русская версия | украинская версия