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

1. Динамическое программирование. Основные понятия…………………2

2. Суть метода динамического программирования………………………..4

3. Пример решения задачи методом динамического программирования………………………………………………………...7

Список используемых источников……………………………………...11

1. Динамическое программирование. Основные понятия.

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

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

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

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

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

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

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

Для процессов с непрерывным временем динамическое программирование рассматривается как предельный вариант дискретной схемы решения. Получаемые при этом результаты практически совпадают с теми, которые получаются методами максимума Л. С. Понтрягина или Гамильтона-Якоби-Беллмана.

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

Суть метода динамического программирования.

В основу метода динамического программирования положен принцип оптимальности , сформулированный в 1957 г. американским математиком Ричардом Беллманом: «Оптимальное поведение обладает тем свойством, что каковы бы ни были первоначальные состояние и решение в начальный момент времени, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения».

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

Рассматривается следующая общая задача. Имеется некоторая физическая система, в которой происходит какой-то процесс, состоящий из n шагов. Эффективность процесса характеризуется некоторым показателем W , который называют выигрышем . Пусть общий выигрыш W за все n шагов процесса складывается из выигрышей на отдельных шагах

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

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

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

В модели динамического программирования процесс на каждом шаге находится в одном из состояний s множества состояний S . Считается, что всякому состоянию сопоставлены некоторые шаговые управления. Эти управления таковы, что управление, выбранное в данном состоянии при любой предыстории процесса, определяет полностью следующее состояние процесса. Обычно выделены два особых состояния: s 0 - начальное и s w - конечное.

Итак, пусть каждому состоянию поставлено множество допустимых шаговых управлений , и каждому шаговому управлению , соответствует - состояние, в которое процесс попадает из s i в результате использования шагового управления u . Пусть процесс находится в начальном состоянии s 0 . Выбор переводит процесс в состояние s 1 = σ(s 0 ,u 1), выбор - в состояние s 2 = σ(s 1 ,u 2) и т.д. В результате получается траектория процесса, которая состоит из последовательности пар

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

конечны и U s для различных s не пересекаются.

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

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

Тот максимальный выигрыш, который достигается при этом управлении обозначим W max :

W max = max U {W (u )}. (2.5)

Рассмотрим на примере задачи о рюкзаке, что понимается под шагом, состоянием, управлением и выигрышем.

Загрузку рюкзака можно представить себе как процесс, состоящий из n шагов. На каждом шаге требуется ответить на вопрос: взять данный предмет в рюкзак, или нет? Таким образом, шаг процесса - присваивание переменной x i значения 1 или 0.

Теперь определим состояния. Очевидно, что текущее состояние процесса характеризует остаточная грузоподъёмность рюкзака - вес, который остался в нашем распоряжении до конца (до полной укладки рюкзака). Следовательно, под состоянием перед i -м шагом понимается величина

(2.6)

при этом s 0 является начальным состоянием, которому соответствует величина b - исходная грузоподъемность рюкзака.

Управление на i -м шаге означает присваивание двоичной переменной x i значения 0 или 1. Значит, на каждом шаге имеем всего два управления. Причем допустимость управления u i , устанавливающего x i = 1, определяется условием

(2.8)

Шаговый выигрыш можно определить как . Поэтому

(2.10)

Требуется найти оптимальное управление , при котором величина выигрыша (2.10) обращается в максимум.

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

Задание . Инвестор выделяет средства в размере 5 тыс. ден. ед., которые должны быть распределены между тремя предприятиями.

Требуется, используя принцип оптимальности Беллмана, построить план распределения инвестиций между предприятиями, обеспечивающий наибольшую общую прибыль, если каждое предприятие при инвестировании в него средств x тыс. ден. ед. приносит прибыль p;(x) тыс. ден. ед. (i=1, 2 и 3) по следующим данным:

Решение . Составим математическую модель задачи.

1.Число шагов равно 3.

2.Пусть s - количество средств, имеющихся в наличии перед данным шагом, и характеризующих состояние системы на каждом шаге.

3. Управление на i-ом шаге (i=1,2,3) выберем x i - количество средств, инвестируемых в i- ое предприятие.

4. Выигрыш p i (x i) на i-ом шаге - это прибыль, которую приносит i-ое предприятие при инвестировании в него средств xi. Если через выигрыш в целом обозначить общую прибыль W, то W=p 1 (x 1)+ p 2 (x 2)+ p 3 (x 3).

5. Если в наличии имеются средства в количестве s тыс. ден. ед. и в i-ое предприятие инвестируется x тыс. ден. ед, то для дальнейшего инвестирования остается (s-x) тыс. ден. ед. Таким образом, если на i-ом шаге система находилась в состоянии s и выбрано управление x, то на (i+1)-ом шаге система будет находится в состоянии (s-x), и, следовательно, функция перехода в новое состояние имеет вид: f i (s, x) = s-x.

6.На последнем (i=3) шаге оптимальное управление соответствует количеству средств, имеющихся в наличии, а выигрыш равен доходу, приносимым последним предприятием: x 3 (s)=s, W 3 (s)=p 3 (s).

7.Согласно принципу оптимальности Беллмана, управление на каждом шаге нужно выбирать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до конца процесса шагах, включая выигрыш на данном шаге. Основное функциональное уравнение примет вид

W 2 (s) = max{p 2 (x) + W 3 (s - x)}

Проведем пошаговую оптимизацию, по результатам которой заполним таблицу.

s	i=3	i=2	i=1
	x 3 (s)	W 3 (s)	x 2 (s)	W 2 (s)	x i (s)	W i (s)
		4,27		4,27
		7,64		7,64
		10,25		10,97
		15,93		15,93
		16,12		19,26		19,26

В первой колонке таблицы записываются возможные состояния системы, в верхней строке - номера шагов с оптимальным управлением и выигрышем на каждом шаге, начиная с последнего. Так как для последнего шага i=3 функциональное уравнение имеет вид x 3 (s)=s, W3(s)=p3(s), то две колонки таблицы, соответствующие i=3, заполняются автоматически по таблице исходных данных.

На шаге i=2 основное функциональное уравнение имеет вид

W 2 (s) = max{p 2 (x) + W 3 (s - x)}

Поэтому для проведения оптимизации на этом шаге заполним таблицу для различных состояний s при шаге i=3.

s	x	s-x	p 2 (x)	W 3 (s-x)	p 2 (x)+W 3 (s-x)	W 2 (s)
				4,27	4,27	4,27
		3,33		3,33
				7,64	7,64	7,64
		3,33	4,27	7,6
		4,87		4,87
				10,25	10,25	10,97
		3,33	7,64	10,97
		4,87	4,27	9,14
		5,26		5,26
				15,93	15,93	15,93
		3,33	10,25	13,58
		4,87	7,64	12,51
		5,26	4,27	9,53
		7,34		7,34
				16,12	16,12	19,26
		3,33	15,93	19,26
		4,87	10,25	15,12
		5,26	7,64	12,9
		7,34	4,27	11,61
		9,49		9,49

На шаге i=1 основное функциональное уравнение имеет вид

W x (s) = max{ p x (x) + W 2 (s - x)}

а состояние системы перед первым шагом s=5, поэтому для проведения оптимизации на этом шаге заполним таблицу.

s	x	s-x	p i (x)	W 2 (s-x)	p i (x)+W 2 (s-x)	Wi(s)
				19,26	19,26	19,26
		3,22	15,93	19,15
		3,57	10,97	14,54
		4,12	7,64	11,76
			4,27	8,27
		4,85		4,85

Видно, что наибольшее значение выигрыша составляет 19,26. При этом оптимальное управление на первом шаге составляет x 1 (s 1)=0 (s 1 =5), на втором шаге x 2 (s 2) =1 (s 2 =s 1 -x 1 =5) и на третьем шаге x 3 (s 3) =4 (s 3 =s 2 -x 2 =4).

Это означает, что (0, 1, 4) - оптимальный план распределения инвестиций между предприятиями.

Таким образом, для получения наибольшей общей прибыли в размере 19,26 тыс. ден. ед., необходимо вложить 1 тыс. ден. ед. во второе предприятие и 4 тыс. ден. ед. в третье предприятие.

Список используемых источников

1. Беллман Р., Динамическое программирование, пер. с англ., М., 1960

2. Болтянский В. Г.,Математические методы оптимального управления, М., 1966

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ, раздел оптимального управления, посвящённый теории и методам решения многошаговых задач. В задачах оптимального управления среди возможных управлений ищется то, при котором достигается экстремальное (наименьшее или наибольшее) значение так называемой целевой функции - некоторой числовой характеристики процесса. В динамическом программировании под многошаговостью понимают либо многоступенчатую структуру процесса, либо то, что управление разбивается на ряд последовательных этапов (шагов), соответствующих, как правило, различным моментам времени. Иногда многошаговость проистекает из существа процесса, но она может вводиться и искусственно для того, чтобы обеспечить возможность применения методов динамического программирования. Под программированием в динамическом программировании понимают принятие решений (планирование), а слово «динамическое» указывает на существенную роль времени и порядка выполнения операций. Методы динамического программирования являются составной частью методов, используемых в исследовании операций, и применяются в задачах оптимального планирования (например, в задачах об оптимальном распределении ресурсов, в теории управления запасами, в задачах замены оборудования) и при решении многих технических проблем (например, в задачах управления последовательными химическими процессами, в задачах оптимальной прокладки дорог).

Пусть процесс управления некоторой системой Х состоит из m шагов (этапов); на i-м шаге управление y i переводит систему из состояния x i-1 , в котором она находилась после (i - 1)-го шага, в новое состояние x i . При этом задана функция f i (х, у), и новое состояние определяется по этой функции значениями x i-1 , y i так, что x i = f i (x i-1 , y i), i = 1, 2,..., m. Таким образом, управления у 1 , у 2 , ..., у m переводят систему из начального состояния х 0 ∈ Х 0 в конечное состояние х m ∈ Х m , где Х 0 и Х m - совокупности допустимых начальных и конечных состояний системы Х.

Одна из возможных постановок задач динамического программирования состоит в следующем. При заданном начальном состоянии х 0 требуется выбрать управления у 1 , у 2 , ..., у m таким образом, чтобы система Х перешла в допустимое конечное состояние и при этом заданная целевая функция F(х 0 , у 1 , х 1 ,..., у m , х m) достигла максимального значения F*, т. е.

где максимум берётся по всем управлениям у 1 , ..., у m , для которых х m ∈ Х m .

В динамическом программировании обычно предполагается, что целевая функция является аддитивной. В рассмотренном примере это означает, что

Кроме того, в динамическом программировании предполагается, что в задаче отсутствует последействие: решения (управления), принимаемые на шаге i, оказывают влияние только на состояние x i системы в момент i. Оба упомянутых ограничительных условия можно ослабить, но только за счёт существенного усложнения метода.

В основе динамического программирования лежит принцип оптимальности, сформулированный Р. Беллманом. Пусть выбраны некоторые управления у 1 , у 2 , ..., y k и тем самым траектория х 0 , х 1 , ...,x k состояний и требуется завершить процесс, т. е. выбрать у k+1 , ..., у m (а значит, и x k+1 , ..., х m).

Если завершающая часть процесса не будет оптимальной в смысле достижения максимума функции

то и весь процесс не будет оптимальным. Пользуясь принципом оптимальности Беллмана, можно получить основное функциональное соотношение динамического программирования, которое состоит в следующем. Пусть ω m (х) = 0,

k = 1, 2, ..., m, где максимум берётся по всем управлениям у, допустимым на шаге k. Соотношение, определяющее зависимость ω k-1 от ω k , называется уравнением Беллмана. Смысл этих функций достаточно ясен: если система на шаге k-1 оказалась в состоянии х, то ω k-1 (х) есть максимально возможное значение функции F k . Одновременно с построением функций ω k-1 (х) находятся условные оптимальные управления y k (х) на каждом шаге, т. е. значения оптимального управления при всевозможных предположениях о состоянии х системы на шаге k-1. Окончательно оптимальные управления находятся последовательным вычислением величин ω 0 (х 0) = F*, у 1 , х 1 , у 2 , ..., у m , x m .

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

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

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

Лит.: Беллман Р. Динамическое программирование. М., 1960; Математическая теория оптимальных процессов. М., 1961; Ховард Р. А. Динамическое программирование и марковские процессы. М., 1964; Хедли Дж. Нелинейное и динамическое программирование. М., 1967; Хедли Дж., Уайтин Т. Анализ систем управления запасами. М., 1969.

Динамическое программирование - тема, которой в рунете посвящено довольно мало статей, поэтому мы решили ею заняться. В этой статье будут разобраны классические задачи на последовательности, одномерную и двумерную динамику, будет дано обоснование решениям и описаны разные подходы к их реализации. Весь приведённый в статье код написан на Java.

О чём вообще речь? Что такое динамическое программирование?

Метод решения задачи путём её разбиения на несколько одинаковых подзадач, рекуррентно связанных между собой. Самым простым примером будут числа Фибоначчи - чтобы вычислить некоторое число в этой последовательности, нам нужно сперва вычислить третье число, сложив первые два, затем четвёртое таким же образом на основе второго и третьего, и так далее (да, мы слышали про замкнутую формулу).

Хорошо, как это использовать?

Решение задачи динамическим программированием должно содержать следующее:

И что, мне для решения рекурсивный метод писать надо? Я слышал, они медленные.

Конечно, не надо, есть и другие подходы к реализации динамики. Разберём их на примере следующей задачи:

Вычислить n-й член последовательности, заданной формулами:
a 2n = a n ­+ a n-1 ,
a 2n+1 = a n — a n-1 ,
a 0 = a 1 = 1.

Идея решения

Здесь нам даны и начальные состояния (a 0 = a 1 = 1), и зависимости. Единственная сложность, которая может возникнуть - понимание того, что 2n - условие чётности числа, а 2n+1 - нечётности. Иными словами, нам нужно проверять, чётно ли число, и считать его в зависимости от этого по разным формулам.

Рекурсивное решение

Очевидная реализация состоит в написании следующего метода:

Private static int f(int n){ if(n==0 || n==1) return 1; // Проверка на начальное значение if(n%2==0){ //Проверка на чётность return f(n/2)+f(n/2-1); // Вычисляем по формуле для чётных индексов, // ссылаясь на предыдущие значения }else{ return f((n-1)/2)-f((n-1)/2-1); // Вычисляем по формуле для нечётных //индексов, ссылаясь на предыдущие значения } }

И она отлично работает, но есть нюансы. Если мы захотим вычислить f(12) , то метод будет вычислять сумму f(6)+f(5) . В то же время, f(6)=f(3)+f(2) и f(5)=f(2)-f(1) , т.е. значение f(2) мы будем вычислять дважды. Спасение от этого есть - мемоизация (кеширование значений).

Рекурсивное решение с кэшированием значений

Идея мемоизации очень проста - единожды вычисляя значение, мы заносим его в какую-то структуру данных. Перед каждым вычислением мы проверяем, есть ли вычисляемое значение в этой структуре, и если есть, используем его. В качестве структуры данных можно использовать массив, заполненный флаговыми значениями. Если значение элемента по индексу N равно значению флага, значит, мы его ещё не вычисляли. Это создаёт определённые трудности, т.к. значение флага не должно принадлежать множеству значений функции, которое не всегда очевидно. Лично я предпочитаю использовать хэш-таблицу - все действия в ней выполняются за O(1) , что очень удобно. Однако, при большом количестве значений два числа могут иметь одинаковый хэш, что, естественно, порождает проблемы. В таком случае стоит использовать, например, красно-чёрное дерево .

Для уже написанной функции f(int) кэширование значений будет выглядеть следующим образом:

Private static HashMap cache = new HashMap(); private static int fcashe(int n){ if(!cache.containsKey(n)){//Проверяем, находили ли мы данное значение cache.put(n, f(n)); //Если нет, то находим и записываем в таблицу } return cache.get(n); }

Не слишком сложно, согласитесь? Зато это избавляет от огромного числа операций. Платите вы за это лишним расходом памяти.

Последовательное вычисление

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

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

Суть метода в следующем: мы создаём массив на N элементов и последовательно заполняем его значениями. Вы, наверное, уже догадались, что таким образом мы можем вычислять в том числе те значения, которые для ответа не нужны. В значительной части задач на динамику этот факт можно опустить, так как для ответа часто бывают нужны как раз все значения. Например, при поиске наименьшего пути мы не можем не вычислять путь до какой-то точки, нам нужно пересмотреть все варианты. Но в нашей задаче нам нужно вычислять приблизительно log 2 (N) значений (на практике больше), для 922337203685477580-го элемента (MaxLong/10) нам потребуется 172 вычисления.

Private static int f(int n){ if(n<2) return 1; //Может, нам и вычислять ничего не нужно? int fs = int[n]; //Создаём массив для значений fs=fs=1; //Задаём начальные состояния for(int i=2; i

Ещё одним минусом такого подхода является сравнительно большой расход памяти.

Создание стека индексов

Сейчас нам предстоит, по сути, написать свою собственную рекурсию. Идея состоит в следующем - сначала мы проходим «вниз» от N до начальных состояний, запоминая аргументы, функцию от которых нам нужно будет вычислять. Затем возвращаемся «вверх», последовательно вычисляя значения от этих аргументов, в том порядке, который мы записали.

Зависимости вычисляются следующим образом:

LinkedList stack = new LinkedList(); stack.add(n); { LinkedList queue = new LinkedList(); //Храним индексы, для которых ещё не вычислены зависимости queue.add(n); int dum; while(queue.size()>0){ //Пока есть что вычислять dum = queue.removeFirst(); if(dum%2==0){ //Проверяем чётность if(dum/2>1){ //Если вычисленная зависимость не принадлежит начальным состояниям stack.addLast(dum/2); //Добавляем в стек queue.add(dum/2); //Сохраняем, чтобы //вычислить дальнейшие зависимости } if(dum/2-1>1){ //Проверяем принадлежность к начальным состояниям stack.addLast(dum/2-1); //Добавляем в стек queue.add(dum/2-1); //Сохрнаяем, чтобы //вычислить дальнейшие зависимости } }else{ if((dum-1)/2>1){ //Проверяем принадлежность к начальным состояниям stack.addLast((dum-1)/2); //Добавляем в стек queue.add((dum-1)/2); //Сохрнаяем, чтобы //вычислить дальнейшие зависимости } if((dum-1)/2-1>1){ //Проверяем принадлежность к начальным состояниям stack.addLast((dum-1)/2-1); //Добавляем в стек queue.add((dum-1)/2-1); //Сохрнаяем, чтобы //вычислить дальнейшие зависимости } } /* Конкретно для этой задачи есть более элегантный способ найти все зависимости, здесь же показан достаточно универсальный */ } }

Полученный размер стека – то, сколько вычислений нам потребуется сделать. Именно так я получил упомянутое выше число 172.

Теперь мы поочередно извлекаем индексы и вычисляем для них значения по формулам – гарантируется, что все необходимые значения уже будут вычислены. Хранить будем как раньше – в хэш-таблице.

HashMap values = new HashMap(); values.put(0,1); //Важно добавить начальные состояния //в таблицу значений values.put(1,1); while(stack.size()>0){ int num = stack.removeLast(); if(!values.containsKey(num)){ //Эту конструкцию //вы должны помнить с абзаца о кешировании if(num%2==0){ //Проверяем чётность int value = values.get(num/2)+values.get(num/2-1); //Вычисляем значение values.add(num, value); //Помещаем его в таблицу }else{ int value = values.get((num-1)/2)-values.get((num-1)/2-1); //Вычисляем значение values.add(num, value); //Помещаем его в таблицу } }

Все необходимые значения вычислены, осталось только написать

Return values.get(n);

Конечно, такое решение гораздо более трудоёмкое, однако это того стоит.

Хорошо, математика - это красиво. А что с задачами, в которых не всё дано?

Для больше ясности разберём следующую задачу на одномерную динамику:

На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных «маршрутов» мячика с вершины на землю.

Идея решения

На первую ступеньку можно попасть только одним образом - сделав прыжок с длиной равной единице. На вторую ступеньку можно попасть сделав прыжок длиной 2, или с первой ступеньки - всего 2 варианта. На третью ступеньку можно попасть сделав прыжок длиной три, с первой или со втрой ступенек. Т.е. всего 4 варианта (0->3; 0->1->3; 0->2->3; 0->1->2->3). Теперь рассмотрим четвёртую ступеньку. На неё можно попасть с первой ступеньки - по одному маршруту на каждый маршрут до неё, со второй или с третьей - аналогично. Иными словами, количество путей до 4-й ступеньки есть сумма маршрутов до 1-й, 2-й и 3-й ступенек. Математически выражаясь, F(N) = F(N-1)+F(N-2)+F(N-3) . Первые три ступеньки будем считать начальными состояниями.

Реализация через рекурсию

private static int f(int n){ if(n==1) return 1; if(n==2) return 2; if(n==3) return 4; return f(n-1)+f(n-2)+f(n-3); }

Здесь ничего хитрого нет.

Исходя из того, что, по большому счёту, простое решение на массиве из N элементов очевидно, я продемонстрирую тут решение на массиве всего из трёх.

Int vars = new int; vars=1;vars=2;vars=4; for(int i=3; i

Так как каждое следующее значение зависит только от трёх предыдущих, ни одно значение под индексом меньше i-3 нам бы не пригодилось. В приведённом выше коде мы записываем новое значение на место самого старого, не нужного больше. Цикличность остатка от деления на 3 помогает нам избежать кучи условных операторов. Просто, компактно, элегантно.

Там вверху ещё было написано про какую-то двумерную динамику?..

С двумерной динамикой не связано никаких особенностей, однако я, на всякий случай, рассмотрю здесь одну задачу и на неё.

В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть способов у игрока попасть в правую нижнюю клетку.

Идея решения

Логика решения полностью идентична таковой в задаче про мячик и лестницу - только теперь в клетку (x,y) можно попасть из клеток (x-1,y) или (x, y-1) . Итого F(x,y) = F(x-1, y)+F(x,y-1) . Дополнительно можно понять, что все клетки вида (1,y) и (x,1) имеют только один маршрут - по прямой вниз или по прямой вправо.

Реализация через рекурсию

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

Private static int f(int i, int j) { if(i==1 || j==1) return 1; return f(i-1, j)+f(i, j-1); }

Реализация через массив значений

int dp = new int; for(int i=0; iКлассическое решение динамикой, ничего необычного - проверяем, является ли клетка краем, и задаём её значение на основе соседних клеток.

Отлично, я всё понял. На чём мне проверить свои навыки?

В заключение приведу ряд типичных задач на одномерную и двумерную динамику, разборы прилагаются.

Взрывоопасность

При переработке радиоактивных материалов образуются отходы двух видов - особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N определить количество возможных типов безопасных стопок.

Решение

Ответом является (N+1)-е число Фибоначчи. Догадаться можно было, просто вычислив 2-3 первых значения. Строго доказать можно было, построив дерево возможных построений.

Каждый основной элемент делится на два - основной (заканчивается на B) и побочный (заканчивается на A). Побочные элементы превращаются в основные за одну итерацию (к последовательности, заканчивающейся на A, можно дописать только B). Это характерно для чисел Фибоначчи.

Реализация

Например, так:

//Ввод числа N с клавиатуры N+=2; BigInteger fib = new BigInteger; fib=fib=BigInteger.ONE; for(int i=2; i

Подъём по лестнице

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

Решение

Очевидно, что сумма, которую мальчик отдаст на N-ой ступеньке, есть сумма, которую он отдал до этого плюс стоимость самой ступеньки. «Сумма, которую он отдал до этого» зависит от того, с какой ступеньки мальчик шагает на N-ую - с (N-1)-й или с (N-2)-й. Выбирать нужно наименьшую.

Реализация

Например, так:

Int Imax; //*ввод с клавиатуры числа ступенек* DP = new int; for(int i=0; i

Калькулятор

Имеется калькулятор, который выполняет три операции:

• Прибавить к числу X единицу;
• Умножить число X на 2;
• Умножить число X на 3.

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

Решение

Наивное решение состоит в том, чтобы делить число на 3, пока это возможно, иначе на 2, если это возможно, иначе вычитать единицу, и так до тех пор, пока оно не обратится в единицу. Это неверное решение, т.к. оно исключает, например, возможность убавить число на единицу, а затем разделить на три, из-за чего на больших числах (например, 32718) возникают ошибки.

Правильное решение заключается в нахождении для каждого числа от 2 до N минимального количества действий на основе предыдущих элементов, иначе говоря: F(N) = min(F(N-1), F(N/2), F(N/3)) + 1 . Следует помнить, что все индексы должны быть целыми.

Для воссоздания списка действий необходимо идти в обратном направлении и искать такой индекс i, что F(i)=F(N) , где N - номер рассматриваемого элемента. Если i=N-1 , записываем в начало строки 1, если i=N/2 - двойку, иначе - тройку.

Реализация

int N; //Ввод с клавиатуры int a = new int; a= 0; { int min; for(int i=2; i1){ if(a[i]==a+1){ ret.insert(0, 1); i--; continue; } if(i%2==0&&a[i]==a+1){ ret.insert(0, 2); i/=2; continue; } ret.insert(0, 3); i/=3; } } System.out.println(a[N]); System.out.println(ret);

Самый дешёвый путь

В каждой клетке прямоугольной таблицы N*M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).

Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол.

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

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

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

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

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

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

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

Характеризуя динамическое программирование, как набор математических процедур для оптимального управления дискретной системой, в общем виде задачу оптимального управления можно сформулировать следующим образом. В дискретные моменты времени t = 1, 2,..., N система находится в одном из множеств s i состояний, характеризуемых вектором состояния x (t) . Переход между последовательными состояниями осуществляется с помощью вектора управления u (t) по закону:

x ( t ) = g ( t ) (x ( t ) , u ( t )) ; t = 1, 2,..., N

Управления u (t) выбираются из множества допустимых управлений и образуют последовательность допустимых управлений u (0) ,u (1) ,…,u (N) . Последовательность допустимых управлений при заданном начальном состоянии х (0) определяет траекторию системы х (0) ,х (1) ,х (2) ,…,х (N) .

Всякой траектории соответствует свое значение критерия оптимальности F , или целевой функции управления, слагающегося из отдельных вкладов на каждом этапе управления:

Задачa оптимального управления заключается в нахождении среди множества последовательностей управления такой, которая достигает минимального значения F. Такая последовательность называется оптимальной последовательностью управлений и определяет оптимальную траекторию.

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

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

Метод динамического программирования хорошо иллюстрируется на примере поиска кратчайшего пути между крайними узлами ориентированной сети. Рассмотрим некоторую ориентированную сеть, насчитывающую 12 узлов, которую нужно пройти от начального узла (1) до конечного узла (12) за четыре шага, передвигаясь с каждым шагом от узла к узлу.

Рис. 6.4.1. Прохождение ориентированной сети по кратчайшему пути.

Числа, указанные при дугах (i,j ) равны длинам дуг l ij между узлами i и j (в условных единицах). Возможные состояния системы s i в данном случае связаны с нахождением в i -м узле, управление u (t) связано с выбором направления пути на каждом шаге управления. Четыре шага управления u (1) ,...,u (4) последовательно переводят систему из начального состояния s 1 в конечное состояние s 12 и, таким образом, образуют некоторую траекторию, которую необходимо отыскать. В роли критериея оптимальности F в данном случае выступает длина траектории L , слагающаяся из длин отдельных дуг:

Если поиски кратчайшего пути, т. е. оптимальной траектории, начинать не с начала, а сконца сети и двигаться в обратном направлении к началу, то в этом случае мы имеем алгоритм «обратной прогонки». В данном случае при реализации алгоритма обратной прогонки движение осуществляется от конечного состояния s 12 к начальному состоянию s 1 .

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

Таблица 6.4.1

i t	s 1	s 2	s 3	s 4	s 5	S 6	s 7	s 8	s 9	s 10	s 11
									12	12 6
						10	11 10
			5
1

Заполненные клетки таблицы разбиты пополам. В верхнюю часть заполненной клетки заносится управление u (t) , т. е. в данном случае номер узла, в который осуществляется переход. В нижнюю часть заполненной клетки заносится то значение вклада L t в общее значение критерия оптимальности L , которое было получено при переходеиз соответствующего этой клетке узла в конечный узел.

Заполнение таблицы начинается с первой строки, где хранится информация о последнем шаге пути. Последний, в данном случае четвертый шаг пути определен однозначно при переходе из любого предпоследнего состояния, которым может быть любое из трех возможных: s 9 , s 10 , s 11 . Поэтому оптимальное управление на последнем шаге очевидно. В зависимости от предпоследнего состояния вклад в критерий оптимальности L 4 (9) = 12, L 4 (10) = 6, либо L 4 (11) = 7. Эти значения вклада в L записываются в нижней части клеток первой строки табл. 6.4.1.

Перед предпоследним – в данном случае третьим - шагом множество возможных состояний системы есть {s 5 , s 6 , s 7 , s 8 }. Применим теперь принцип Беллмана для определения траектории на третьем и четвертом шаге. Он заключается в том, что независимо от первых двух шагов управления отрезок траектории на последних двух шагах сам по себе является оптимальной траекторией, т.е. дает минимум вклада L 3 в критерий оптимальности.

Если состояние системы перед предпоследним шагом есть состояние s 8 , то на последних шагах вклад в L определяется соотношением

L 3 (s 5)=min{ }.

Поскольку из s 5 возможны переходы в s 9 и s 11 .т.е.:

g(s 5 ,9) = s 9 ; ; L 4 (s 9) = 12,

g(s 5 ,11) = s 11 ; ; L 4 (s 11) = 7,

L 3 (s 5) = min{6+12, 4+7} = 11 и u (3) = 11.

Это означает, что если система находится в состоянии s 5 , то оптимальное управление заключается сначала в переходе в состояние s 11 , затем в состояние s 12 . Длина дуги из s 5 в s 12 при этом оказывается равна 11 единиц.

Рассчитывая вклад в L аналогично для переходов из состояний s 6 , s 7 , s 8 , получим следующие вклады:

L 3 (s 6)=min{7+12, 6+6)=12 , u (3) =10;

L 3 (s 7)=min{5+6, 3+7)=10, u (3) =11;

L 3 (s 8)=min{10+6, 12+7)=16, u (3) =10;

Полученные четыре пары чисел записываются во вторую строку Табл. 6.4.1.

На втором шаге управления вклад в критерий оптимальности в зависимости от исходного состояния есть

L 2 (s 2) = min{ } = min{11+11, 14+10} = 22, u (2) = 5;

L 2 (s 3) = min{ } = min{7+11, 9+12} = 18, u (2) = 5;

L 2 (s 4) = min{ } = min{2+16, 3+12, 6+10} = 15, u (2) = 6;

Полученные три пары чисел записываются в третью строку Табл.6.4.1.

Начальное состояние s 1 определено однозначно, поэтому в последней строке таблицы заполняется единственная клетка, куда носятся значения 3 и 24 поскольку:

L 1 (s 1) = min{ } = min{5+22, 6+18, 11+15} = 24, u (1) = 3.

Теперь можно окончательно определить последовательность оптимального многошагового управления. На первом шаге u (1) = 3, т.е. из узла 1 переходим в узел 3, на втором шаге u (2) = 5, т.е. переходим в узел 5, далее после управления u (3) = 11 - в узел 11 и, наконец, в узел 12. Окончательно получаем, что кратчайший путь по сети, изображенной на Рис. 6.4.1, проходит по последовательности состояний s 1 →s 2 →s 5 →s 11 →s 12 , а его протяженность составляет 24 условных единиц.

Поиск кратчайшего пути можно также осуществлять из начала сети, реализуя при этом алгоритм прямой прогонки, который выполняет в сущности те же операции сложения и сравнения, но в несколько иной последователь­ности.

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

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

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

1. Исходная задача погружается во множество оптимизационных задач; при этом для каждого узла решается своя задача.

2. Множество решений оптимизационных задач описывается функциональным уравнением, представляющим собой систему уравнений, которые связывают несколько оптимизационных задач. В такой системе каждое уравнение соответствует одному узлу и содержит обычно операторы типа min, mах или minimax справа от знака равенства, а переменные типа g i , и g j - по обе стороны от него.

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

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

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

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

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

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

Множество S возможных (или наблюдаемых) состояний назы­вается пространством состояний, а элемент s из S определяет конкретное состояние. С каждым состоянием s связано множество D (s ) . Элемент d из множества D (s ) называется решением. Правило, согласно которому определяется допустимое решение для каждого состояния, называется стратегией d.

Фактически страте­гия d ставит в соответствие каждому состоянию s некоторый эле­мент d(s ) из множества D (s ). Набор всех таких d образует про­странство стратегий D. Последнее означает, что выбор решения в некотором состоянии не ограничивает выбор во всех других состояниях. По существу, D представляет собой декартово произведение множеств D (s ) по s .

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

Выражение «используя стратегию d» означает, что в состоянии s выбирается решение d(s ); затем предполагается, что процесс перешел в состояние s " , т. е. реализуется состояние s ", в котором выбирается решение d(s "), и т. д. Функция прибыли имеет доволь­но сложную структуру, поскольку она зависит от последователь­ности состояний и решений, от вознаграждений, которые связаны с этими состояниями и решениями, а также от способа агрегиро­вания вознаграждений.

Состояние представляет собой описание предыстории процесса со степенью подробности, позволяющей провести оценку текущих альтернативных решений. Основным свойством состояний является то, что состояние является краткой записью предыстории процесса, причем степень детализации позволяет определить локальную функцию дохода.Иными словами, локальная функция дохода может зависеть лишь от s , d и v.

В следующей главе будут более подробно рассмотрены цепи Маркова, имеющие большое значение для моделирования временной эволюции производственных и технических систем. Существуют также Марковские модели принятия решений, в которых состояние s определяется некоторой парой чисел (n,i ) , решением является зависящая от них функция k , а локальная функция дохода определяется выражением типа h [(n , I ) , k, v ] = R k i (n ) + å j P k ij (n )v (n+ 1,j ) (n).

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

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

Контрольные вопросы к главе 6.

1. Из каких компонентов состоит ориентированная сеть?

1. Как строится матрица пропускных способностей сети?

1. Как образуется матрица потока в сети?

1. Для чего вычитаются матрицы пропускных способностей и потоков?

1. Что такое и для чего служит сетевой график?

1. Как определяются времена раннего начала и раннего окончания работ?

1. Что представляет собой общий резерв времени для некоторого события на сетевом графике?

1. Как определяется критический путь?

1. Что называется вектором состояния некоторой системы?

1. Что представляет собой траектория системы в пространстве состояний?

1. В чем заключается задача оптимального управления?

1. Как формулируется критерий оптимальности?

1. Что представляет собой динамическое программирование?

1. Сформулируйте принцип оптимальности Беллмана.

1. В чем сущность алгоритмов прямой и обратной прогонки при поиске кратчайшего пути?

Варианты заданий к главе 6.

Для сетей в каждом из вариантов:

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

1) Полагая, что дуги (1)®(2), (1)®(3) и т. д. определяют некоторые работы, минимальная и максимальная продолжительность которых заданы числами, указанными при соответствующих дугах, найти критический путь от начального события (1) до конечного;

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

X 4

Для выбора оптимального решения при выполнении задач программирования иногда требуется перебирать большое количество комбинаций данных, что нагружает память персонального компьютера. К таким методам относится, например, метод программирования «разделяй и властвуй». В данном случае алгоритмом предусмотрено разделение задачи на отдельные мелкие подзадачи. Такой метод применяется только в тех случаях, когда мелкие подзадачи независимы между собой. Для того чтобы избежать выполнения лишней работы в том случае, если подзадачи взаимозависимы, используется метод динамического программирования, предложенный американцем Р.Беллманом в 50-х годах.

Суть метода

Динамическое программирование заключается в определении оптимального решения n-мерной задачи, разделяя ее n отдельных этапов. Каждый из них является подзадачей по отношению к одной переменной.

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

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

Задача динамического программирования оптимизации. Автором этого метода Р. Беллманом был сформулирован принцип оптимальности: каким бы ни являлось начальное состояние на каждом из шагов и решение, определенное на этом шаге, все следующие выбираются оптимальными по отношению к тому состоянию, которое принимает система в конце шага.

Метод усовершенствует выполнение задач, решаемых с помощью перебора вариантов или рекурсий.

Построение алгоритма задачи

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

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

Применение метода

Динамическое программирование применяется при наличии двух характерных признаков:

• оптимальность для подзадач;
• наличие в задаче перекрывающихся подзадач.

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

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

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