Динамическое программирование основано на решении. Примеры, решаемых при помощи динамического программирования задач. Прикладные задачи динамического программирования
Допустим, есть задача, которую мы уже решили динамическим программированием, например, извечные числа Фибоначчи.
Давайте немного переформулируем её. Пусть у нас есть вектор , из которого мы хотим получить вектор . Чуть-чуть раскроем формулы: . Можно заметить, что из вектора можно получить вектор 
путем умножения на какую-то матрицу, ведь в итоговом векторе фигурируют только сложенные переменные из первого вектора. Эту матрицу легко вывести, вот она: 
. Назовём её матрицей перехода.
Это значит, что если взять вектор 
и умножить его на матрицу перехода n - 1 раз, то получим вектор , в котором лежит fib[n] - ответ на задачу.
А теперь, зачем всё это надо. Умножение матриц обладает свойством ассоциативности, то есть (но при этом не обладает коммутативностью, что по-моему удивительно). Это свойство даёт нам право сделать так: .
Это хорошо тем, что теперь можно применить метод быстрого возведения в степень , который работает за . Итого мы сумели посчитать N -ое число Фибоначчи за логарифм арифметических операций.
А теперь пример посерьёзнее:
Пример №3: Пилообразная последовательность
Обозначим пилообразную последовательность длины N как последовательность, у которой для каждого не крайнего элемента выполняется условие: он или меньше обоих своих соседей или больше. Требуется посчитать количество пилообразных последовательностей из цифр длины N . Выглядит это как-то так:
Решение
Для начала решение без матрицы перехода:
1) Состояние динамики: dp[n] - количество пилообразных последовательностей длины n , заканчивающихся на цифру last . Причём если less == 0 , то последняя цифра меньше предпоследней, а если less == 1 , значит больше.
2) Начальные значения:
for last in range(10):
dp = 9 - last
dp = last
3) Пересчёт динамики:
for prev in range(10):
if prev > last:
dp[n] += dp
if prev < last:
dp[n] += dp
4) Порядок пересчёта: мы всегда обращаемся к предыдущей длине, так что просто пара вложенных for "ов.
5) Ответ - это сумма dp[N] .
Теперь надо придумать начальный вектор и матрицу перехода к нему. Вектор, кажется, придумывается быстро: все состояния, обозначающие длину последовательности N . Ну а матрица перехода выводится, смотря на формулы пересчёта.
Вектор и матрица перехода
Динамика по подотрезкам
Это класс динамики, в котором состояние - это границы подотрезка какого-нибудь массива. Суть в том, чтобы подсчитать ответы для подзадач, основывающихся на всех возможных подотрезках нашего массива. Обычно перебираются они в порядке увеличения длины, и пересчёт основывается, соответственно на более коротких отрезках.Пример №4: Запаковка строки
Вот Развернутое условие . Я вкратце его перескажу:Определим сжатую строку:
1) Строка состоящая только из букв - это сжатая строка. Разжимается она в саму себя.
2) Строка, являющаяся конкатенацией двух сжатых строк A и B . Разжимается она в конкатенацию разжатых строк A и B .
3) Строка D(X) , где D - целое число, большее 1 , а X - сжатая строка. Разжимается она в конкатенацию D строк, разжатых из X .
Пример: “3(2(A)2(B))C” разжимается в “AABBAABBAABBC” .
Необходимо по строке s узнать длину самой короткой сжатой строки, разжимающийся в неё.
Решение
Решается эта задача, как вы уже наверняка догадались, динамикой по подотрезкам.
1) Состояние динамики: d[l][r] - сжатая строка минимальной длины, разжимающаяся в строку s
2) Начальные состояния: все подстроки длины один можно сжать только в них самих.
3) Пересчёт динамики:
У лучшего ответа есть какая-то последняя операция сжатия: либо это просто строка из заглавных букв, или это конкатенация двух строк, или само сжатие. Так давайте переберём все варианты и выберем лучший.
Dp_len = r - l
dp[l][r] = dp_len # Первый вариант сжатия - просто строка.
for i in range(l + 1, r):
dp[l][r] = min(dp[l][r], dp[l][i] + dp[i][r]) # Попробовать разделить на две сжатые подстроки
for cnt in range(2, dp_len):
if (dp_len % cnt == 0): # Если не делится, то нет смысла пытаться разделить
good = True
for j in range(1, (dp_len / cnt) + 1): # Проверка на то, что все cnt подстрок одинаковы
good &= s == s
if good: # Попробовать разделить на cnt одинаковых подстрок и сжать
dp[l][r] = min(dp[l][r], len(str(cnt)) + 1 + dp[l] + 1)
4) Порядок пересчёта: прямой по возрастанию длины подстроки или ленивая динамика.
5) Ответ лежит в d .
Пример №5:
Динамика по поддеревьям
Параметром состояния динамики по поддеревьям обычно бывает вершина, обозначающая поддерево, в котором эта вершина - корень. Для получения значения текущего состояния обычно нужно знать результаты всех своих детей. Чаще всего реализуют лениво - просто пишут поиск в глубину из корня дерева.Пример №6: Логическое дерево
Дано подвешенное дерево, в листьях которого записаны однобитовые числа - 0 или 1 . Во всех внутренних вершинах так же записаны числа, но по следующему правилу: для каждой вершины выбрана одна из логических операций: «И» или «ИЛИ». Если это «И», то значение вершины - это логическое «И» от значений всех её детей. Если же «ИЛИ», то значение вершины - это логическое «ИЛИ» от значений всех её детей.
Требуется найти минимальное количество изменений логических операций во внутренних вершинах, такое, чтобы изменилось значение в корне или сообщить, что это невозможно.
Решение
1) Состояние динамики: d[v][x] - количество операций, требуемых для получения значения x в вершине v . Если это невозможно, то значение состояния - +inf .
2) Начальные значения: для листьев, очевидно, что своё значение можно получить за ноль изменений, изменить же значение невозможно, то есть возможно, но только за +inf операций.
3) Формула пересчёта:
Если в этой вершине уже значение x , то ноль. Если нет, то есть два варианта: изменить в текущей вершине операцию или нет. Для обоих нужно найти оптимальный вариант и выбрать наилучший.
Если операция «И» и нужно получить «0», то ответ это минимум из значений d[i] , где i - сын v .
Если операция «И» и нужно получить «1», то ответ это сумма всех значений d[i] , где i - сын v .
Если операция «ИЛИ» и нужно получить «0», то ответ это сумма всех значений d[i] , где i - сын v .
Если операция «ИЛИ» и нужно получить «1», то ответ это минимум из значений d[i] , где i - сын v .
4) Порядок пересчёта: легче всего реализуется лениво - в виде поиска в глубину из корня.
5) Ответ - d xor 1] .
Динамика по подмножествам
В динамике по подмножествам обычно в состояние входит маска заданного множества. Перебираются чаще всего в порядке увеличения количества единиц в этой маске и пересчитываются, соответственно, из состояний, меньших по включению. Обычно используется ленивая динамика, чтобы специально не думать о порядке обхода, который иногда бывает не совсем тривиальным.Пример №7: Гамильтонов цикл минимального веса, или задача коммивояжера
Задан взвешенный (веса рёбер неотрицательны) граф G размера N . Найти гамильтонов цикл (цикл, проходящий по всем вершинам без самопересечений) минимального веса.Решение
Так как мы ищем цикл, проходящий через все вершины, то можно выбрать за «начальную» вершину любую. Пусть это будет вершина с номером 0 .
1) Состояние динамики: dp[v] - путь минимального веса из вершины 0 в вершину v , проходящий по всем вершинам, лежащим в mask и только по ним.
2) Начальные значения: dp = 0 , все остальные состояния изначально - +inf .
3) Формула пересчёта: Если i -й бит в mask равен 1 и есть ребро из i в v , то:
dp[v] = min(dp[v], dp[i] + w[i][v])
Где w[i][v] - вес ребра из i в v .
4) Порядок пересчёта: самый простой и удобный способ - это написать ленивую динамику, но можно поизвращаться и написать перебор масок в порядке увеличения количества единичных битов в ней.
5) Ответ лежит в d[(1 << N) - 1] .
Динамика по профилю
Классическими задачами, решающимися динамикой по профилю, являются задачи на замощение поля какими-нибудь фигурами. Причём спрашиваться могут разные вещи, например, количество способов замощения или замощение минимальным количеством фигур.Эти задачи можно решить полным перебором за , где a - количество вариантов замощения одной клетки. Динамика по профилю же оптимизирует время по одной из размерностей до линейной, оставив от себя в экспоненте только коэффициент. Получится что-то такое: .
Профиль - это k (зачастую один) столбцов, являющиеся границей между уже замощённой частью и ещё не замощённой. Эта граница заполнена только частично. Очень часто является частью состояния динамики.
Почти всегда состояние - это профиль и то, где этот профиль. А переход увеличивает это местоположение на один. Узнать, можно ли перейти из одного профиля в другой можно за линейное от размера профиля время. Это можно проверять каждый раз во время пересчёта, но можно и предподсчитать. Предподсчитывать будем двумерный массив can - можно ли от одной маски перейти к другой, положив несколько фигурок, увеличив положение профиля на один. Если предподсчитывать, то времени на выполнение потребуется меньше, а памяти - больше.
Пример №8: Замощение доминошками
Найти количество способов замостить таблицу N x M с помощью доминошек размерами 1 x 2 и 2 x 1 .Решение
Здесь профиль - это один столбец. Хранить его удобно в виде двоичной маски: 0 - не замощенная клетка столбца, 1 - замощенная. То есть всего профилей .
0) Предподсчёт (опционально): перебрать все пары профилей и проверить, что из одного можно перейти в другой. В этой задаче это проверяется так:
Если в первом профиле на очередном месте стоит 1 , значит во втором обязательно должен стоять 0 , так как мы не сможем замостить эту клетку никакой фигуркой.
Если в первом профиле на очередном месте стоит 0 , то есть два варианта - или во втором 0 или 1 .
Если 0 , это значит, что мы обязаны положить вертикальную доминошку, а значит следующую клетку можно рассматривать как 1 . Если 1 , то мы ставим вертикальную доминошку и переходим к следующей клетке.
Примеры переходов (из верхнего профиля можно перейти в нижние и только в них):
После этого сохранить всё в массив can - 1 , если можно перейти, 0 - если нельзя.
1) Состояние динамики: dp - количество полных замощений первых pos - 1 столбцов с профилем mask .
2) Начальное состояние: dp = 1 - левая граница поля - прямая стенка.
3) Формула пересчёта:
dp += dp * can
4) Порядок обхода - в порядке увеличения pos .
5) Ответ лежит в dp.
Полученная асимптотика - .
Динамика по изломанному профилю
Это очень сильная оптимизация динамики по профилю. Здесь профиль - это не только маска, но ещё и место излома. Выглядит это так:
Теперь, после добавления излома в профиль, можно переходить к следующему состоянию, добавляя всего одну фигурку, накрывающую левую клетку излома. То есть увеличением числа состояний в N раз (надо помнить, где место излома) мы сократили число переходов из одного состояния в другое с до . Асимптотика улучшилась с до 
.
Переходы в динамике по изломанному профилю на примере задачи про замощение доминошками (пример №8):
Восстановление ответа
Иногда бывает, что просто знать какую-то характеристику лучшего ответа недостаточно. Например, в задаче «Запаковка строки» (пример №4) мы в итоге получаем только длину самой короткой сжатой строки, но, скорее всего, нам нужна не её длина, а сама строка. В таком случае надо восстановить ответ.В каждой задаче свой способ восстановления ответа, но самые распространенные:
- Рядом со значением состояния динамики хранить полный ответ на подзадачу. Если ответ - это что-то большое, то может понадобиться чересчур много памяти, поэтому если можно воспользоваться другим методом, обычно так и делают.
- Восстанавливать ответ, зная предка(ов) данного состояния. Зачастую можно восстановить ответ, зная только как он был получен. В той самой «Запаковке строки» можно для восстановления ответа хранить только вид последнего действия и то, из каких состояний оно было получено.
- Есть способ, вообще не использующий дополнительную память - после пересчёта динамики пойти с конца по лучшему пути и по дороге составлять ответ.
Небольшие оптимизации
Память
Зачастую в динамике можно встретить задачу, в которой состояние требует быть посчитанными не очень большое количество других состояний. Например, при подсчёте чисел Фибоначчи мы используем только два последних, а к предыдущим уже никогда не обратимся. Значит, можно про них забыть, то есть не хранить в памяти. Иногда это улучшает асимптотическую оценку по памяти. Этим приёмом можно воспользоваться в примерах №1, №2, №3 (в решении без матрицы перехода), №7 и №8. Правда, этим никак не получится воспользоваться, если порядок обхода - ленивая динамика.Время
Иногда бывает так, что можно улучшить асимптотическое время, используя какую-нибудь структуру данных. К примеру, в алгоритме Дейкстры можно воспользоваться очередью с приоритетами для изменения асимптотического времени.Замена состояния
В решениях динамикой обязательно фигурирует состояние - параметры, однозначно задающие подзадачу, но это состояние не обязательно одно единственное. Иногда можно придумать другие параметры и получить с этого выгоду в виде снижения асимптотического времени или памяти.Пример №9: Разложение числа
Требуется найти количество разложений числа N на различные слагаемые. Например, если N = 7 , то таких разложений 5:- 3 + 4
- 2 + 5
- 1 + 7
- 1 + 2 + 4
Динамическое программирование.
При моделировании сетевых структур помимо задач, связанных с существованием потоков в транспортных, электрических, телефонных, компьютерных и прочих видах сетей, возникает целый класс задач, сводимых к задаче о кратчайшем пути. Например, задача о кратчайшем пути всякий раз решается программой - маршрутизатором при нахождении сайта по его имени в сети Интернет.
Задача о кратчайшем пути в ориентированной сети является типичной задачей динамического программирования, поэтому, хотя динамическое программирование, также как и сетевое планирование, связано с развитием процессов во времени, моделирование которых более детально рассмотрено в следующем разделе, рассмотрим уже в этом параграфе метод динамического программирования на примере поиска кратчайшего пути.
Понятие динамического программирования тесно связано с многошаговыми процессами принятия решений. Многошаговый процесс принятия решений можно определить, как процесс принятия последовательных решений, направленных на достижение заданной цели. Многошаговые процессы принятия решений постоянно встречаются в самых различных ситуациях, от ремонта автомобиля в автосервисе до управления космическим аппаратом.
Динамическое программирование можно приблизительно определить, как набор математических процедур, используемых при анализе многошаговых процессов принятия решений. Каждый многошаговый процесс принятия решений представляет собой развитие следующей задачи: найти кратчайший путь в направленной, ациклической сети.
Динамическое программирование можно рассматривать как единую теорию благодаря единому набору идей и приемов, которые используются при математическом анализе различных задач. Эти идеи и приемы и составляют сущность динамического программирования. Беллман одним из первых понял суть принципа оптимальности и стал применять его ко многим оптимизационным задачам, возникающих в математике, технике, исследовании операций и в других областях.
Таким образом, понятие динамического программирования связано с многошаговым процессом принятия решений для достижения определенной цели. Например, перевод летательного аппарата с одной орбиты на другую представляет собой типичную задачу динамического программирования, при условии, если коррекция орбиты осуществляется приложением импульса в дискретные моменты времени, а целью является экономия топлива.
Характеризуя динамическое программирование, как набор математических процедур для оптимального управления дискретной системой, в общем виде задачу оптимального управления можно сформулировать следующим образом. В дискретные моменты времени 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
Суть метода динамического программирования………………………..4
Пример решения задачи методом динамического программирования………………………………………………………...7
Список используемых источников……………………………………...11
Динамическое программирование. Основные понятия.
Динамическое программирование (ДП) втеории вычислительных систем- способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам соптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.
Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.
Динамическое программирование представляет собой математический аппарат, который подходит к решению некоторого класса задач путем их разложения на части, небольшие и менее сложные задачи. При этом отличительной особенностью является решение задач по этапам, через фиксированные интервалы, промежутки времени, что и определило появление термина динамическое программирование. Следует заметить, что методы динамического программирования успешно применяются и при решении задач, в которых фактор времени не учитывается. В целом математический аппарат можно представить как пошаговое или поэтапное программирование. Решение задач методами динамического программирования проводится на основе сформулированного Р. Э. Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения. Из этого следует, что планирование каждого шага должно проводиться с учетом общей выгоды, получаемой по завершении всего процесса, что и позволяет оптимизировать конечный результат по выбранному критерию.
Таким образом, динамическое программирование в широком смысле представляет собой оптимальное управление процессом, посредством изменения управляемых параметров на каждом шаге, и, следовательно, воздействуя на ход процесса, изменяя на каждом шаге состояние системы. В целом динамическое программирование представляет собой стройную теорию для восприятия и достаточно простую для применения в коммерческой деятельности при решении как линейных, так и нелинейных задач.
Динамическое программирование является одним из разделов оптимального программирования. Для него характерны специфические методы и приемы, применительные к операциям, в которых процесс принятия решения разбит на этапы (шаги). Методами динамического программирования решаются вариантные оптимизационные задачи с заданными критериями оптимальности, с определенными связями между переменными и целевой функцией, выраженными системой уравнений или неравенств. При этом, как и в задачах, решаемых методами линейного программирования, ограничения могут быть даны в виде равенств или неравенств. Однако если в задачах линейного программирования зависимости между критериальной функцией и переменными обязательно линейны, то в задачах динамического программирования эти зависимости могут иметь еще и нелинейный характер. Динамическое программирование можно использовать как для решения задач, связанных с динамикой процесса или системы, так и для статических задач, связанных, например, с распределением ресурсов. Это значительно расширяет область применения динамического программирования для решения задач управления. А возможность упрощения процесса решения, которая достигается за счет ограничения области и количества, исследуемых при переходе к очередному этапу вариантов, увеличивает достоинства этого комплекса методов.
Вместе с тем динамическому программированию свойственны и недостатки. Прежде всего, в нем нет единого универсального метода решения. Практически каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения. Кроме того, большие объемы и трудоемкость решения многошаговых задач, имеющих множество состояний, приводят к необходимости отбора задач малой размерности либо использования сжатой информации. Последнее достигается с помощью методов анализа вариантов и переработки списка состояний.
Для процессов с непрерывным временем динамическое программирование рассматривается как предельный вариант дискретной схемы решения. Получаемые при этом результаты практически совпадают с теми, которые получаются методами максимума Л. С. Понтрягина или Гамильтона-Якоби-Беллмана.
Динамическое программирование применяется для решения задач, в которых поиск оптимума возможен при поэтапном подходе, например, распределение дефицитных капитальных вложений между новыми направлениями их использования; разработка правил управления спросом или запасами, устанавливающими момент пополнения запаса и размер пополняющего заказа; разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию; составление календарных планов текущего и капитального ремонтов оборудования и его замены; поиск кратчайших расстояний на транспортной сети; формирование последовательности развития коммерческой операции и т. д.
), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.
Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.
Метод динамического программирования сверху - это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.
История
Словосочетание «динамическое программирование» впервые было использовано в -х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В г. он уточнил это определение до современного. Первоначально эта область была основана, как системный анализ и инжиниринг, которая была признана IEEE . Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана , центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме.
Слово «программирование» в словосочетании «динамическое программирование» в действительности к "традиционному" программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование », которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определенное расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий.
Идея динамического программирования
Нахождение кратчайшего пути в графе из одной вершины в другую, используя оптимальную подструктуру; прямая линия обозначает простое ребро; волнистая линия обозначает кратчайший путь между вершинами, которые она соединяет (промежуточные вершины пути не показаны); жирной линией обозначен итоговый кратчайший путь.
Оптимальная подструктура в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. К примеру, кратчайший путь в графе из одной вершины (обозначим s) в другую (обозначим t) может быть найден так: сначала считаем кратчайший путь из всех вершин, смежных с s, до t, а затем, учитывая веса ребер, которыми s соединена со смежными вершинами, выбираем лучший путь до t (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.
- Разбиение задачи на подзадачи меньшего размера.
- Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм .
- Использование полученного решения подзадач для конструирования решения исходной задачи.
Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).
Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи , и - даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали дважды. Если продолжать дальше и посчитать , то посчитается ещё два раза, так как для вычисления будут нужны опять и . Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решение для задач, которые он уже решал.
Чтобы избежать такого хода событий мы будем сохранять решения подзадач, которые мы уже решали, и когда нам снова потребуется решение подзадачи, мы вместо того, чтобы вычислять его заново, просто достанем его из памяти. Этот подход называется кэширование . Можно проделывать и дальнейшие оптимизации - например, если мы точно уверены, что решение подзадачи нам больше не потребуется, можно выкинуть его из памяти, освободив её для других нужд, или если процессор простаивает и мы знаем, что решение некоторых, ещё не посчитанных подзадач, нам понадобится в дальнейшем, мы можем решить их заранее.
Подводя итоги вышесказанного можно сказать, что динамическое программирование пользуется следующими свойствами задачи:
- перекрывающиеся подзадачи;
- оптимальная подструктура;
- возможность запоминания решения часто встречающихся подзадач.
Динамическое программирование обычно придерживается двух подходов к решению задач:
- нисходящее динамическое программирование: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач.
- восходящее динамическое программирование: все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи. Этот способ лучше нисходящего программирования в смысле размера необходимого стека и количества вызова функций, но иногда бывает нелегко заранее выяснить, решение каких подзадач нам потребуется в дальнейшем.
Языки программирования могут запоминать результат вызова функции с определенным набором аргументов (мемоизация), чтобы ускорить «вычисление по имени». В некоторых языках такая возможность встроена (например, Scheme , Common Lisp , Perl), а в некоторых требует дополнительных расширений (C++).
Известны сериальное динамическое программирование, включённое во все учебники по исследованию операций , и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах.
Обычное динамическое программирование является частным случаем несериального динамического программирования, когда граф взаимосвязей переменных - просто путь. НСДП, являясь естественным и общим методом для учета структуры задачи оптимизации, рассматривает множество ограничений и/или целевую функцию как рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причём эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объём вычислений на каждом этапе может сохраняться в разумных пределах.
Одним из основных свойств задач, решаемых с помощью динамического программирования, является аддитивность . Неаддитивные задачи решаются другими методами. Например, многие задачи по оптимизации инвестиций компании являются неаддитивными и решаются с помощью сравнения стоимости компании при проведении инвестиций и без них.
Классические задачи динамического программирования
Литература
- Беллман Р. Динамическое программирование. - М.: Изд-во иностранной литературы, 1960.
- Кормен, Т. , Лейзерсон, Ч. , Ривест, Р. , Штайн, К. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. - 2-е изд. - М .: Вильямс, 2005. - 1296 с. - ISBN 5-8459-0857-4
- Sanjoy Dasgupta , Christos H. Papadimitriou, Umesh Vazirani Algorithms = Algorithms. - 1-е изд. - McGraw-Hill Science/Engineering/Math, 2006. - С. 336. - ISBN 0073523402
- Акулич И.Л. Глава 4. Задачи динамического программирования // Математическое программирование в примерах и задачах. - М .: Высшая школа, 1986. - 319 с. - ISBN 5-06-002663-9 .
- Bertele U., Brioshi F. Nonserial dynamic programming. - N.Y.: Academic Press, 1972. - 235 pp.
- Щербина О. А. О несериальной модификации локального алгоритма декомпозиции задач дискретной оптимизации // Динамические системы, 2005, вып. 19.
- Щербина О. А. Методологические аспекты динамического программирования // Динамические системы, 2007, вып. 22. - c.21-36.
- Габасов Р., Кириллова Ф. М. Основы динамического программирования. - Мн.: Изд-во БГУ, 1975. - 262 с.
Ссылки
Wikimedia Foundation . 2010 .
Смотреть что такое "Динамическое программирование" в других словарях:
динамическое программирование - — [Е.С.Алексеев, А.А.Мячев. Англо русский толковый словарь по системотехнике ЭВМ. Москва 1993] динамическое программирование Раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные … Справочник технического переводчика
Динамическое программирование - раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные на вычислении последствий каждого решения и выработке оптимальной стратегии для последующих решений.… … Экономико-математический словарь
Раздел математики, посвященный теории и методам решения многошаговых задач оптимального управления. В Д. п. для управляемых процессов среди всевозможных управлений ищется то, к рое доставляет экстремальное (наименьшее или наибольшее) значение… … Математическая энциклопедия
Раздел математики, посвящённый теории и методам решения многошаговых задач оптимального управления (См. Оптимальное управление). В Д. п. для управляемых процессов среди всех возможных управлений ищется то, которое доставляет… … Большая советская энциклопедия
динамическое программирование - dinaminis programavimas statusas T sritis automatika atitikmenys: angl. dynamic programming vok. dynamische Programmierung, f rus. динамическое программирование, n pranc. programmation dynamique, f … Automatikos terminų žodynas
Раздел математич. программирования, изучающий многошаговые процессы поиска оптим. решения сложных задач. Применяется при составлении программ решения таких задач оптимизации, для к рых процесс поиска решения можно представить в виде нек рой… … Большой энциклопедический политехнический словарь
1. Динамическое программирование. Основные понятия…………………2
2. Суть метода динамического программирования………………………..4
3. Пример решения задачи методом динамического программирования………………………………………………………...7
Список используемых источников……………………………………...11
Динамическое программирование. Основные понятия.
Динамическое программирование (ДП) в теории вычислительных систем - способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.
Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.
Динамическое программирование представляет собой математический аппарат, который подходит к решению некоторого класса задач путем их разложения на части, небольшие и менее сложные задачи. При этом отличительной особенностью является решение задач по этапам, через фиксированные интервалы, промежутки времени, что и определило появление термина динамическое программирование. Следует заметить, что методы динамического программирования успешно применяются и при решении задач, в которых фактор времени не учитывается. В целом математический аппарат можно представить как пошаговое или поэтапное программирование. Решение задач методами динамического программирования проводится на основе сформулированного Р. Э. Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения.
Из этого следует, что планирование каждого шага должно проводиться с учетом общей выгоды, получаемой по завершении всего процесса, что и позволяет оптимизировать конечный результат по выбранному критерию.
Таким образом, динамическое программирование в широком смысле представляет собой оптимальное управление процессом, посредством изменения управляемых параметров на каждом шаге, и, следовательно, воздействуя на ход процесса, изменяя на каждом шаге состояние системы.
В целом динамическое программирование представляет собой стройную теорию для восприятия и достаточно простую для применения в коммерческой деятельности при решении как линейных, так и нелинейных задач.
Динамическое программирование является одним из разделов оптимального программирования. Для него характерны специфические методы и приемы, применительные к операциям, в которых процесс принятия решения разбит на этапы (шаги). Методами динамического программирования решаются вариантные оптимизационные задачи с заданными критериями оптимальности, с определенными связями между переменными и целевой функцией, выраженными системой уравнений или неравенств. При этом, как и в задачах, решаемых методами линейного программирования, ограничения могут быть даны в виде равенств или неравенств. Однако если в задачах линейного программирования зависимости между критериальной функцией и переменными обязательно линейны, то в задачах динамического программирования эти зависимости могут иметь еще и нелинейный характер. Динамическое программирование можно использовать как для решения задач, связанных с динамикой процесса или системы, так и для статических задач, связанных, например, с распределением ресурсов. Это значительно расширяет область применения динамического программирования для решения задач управления. А возможность упрощения процесса решения, которая достигается за счет ограничения области и количества, исследуемых при переходе к очередному этапу вариантов, увеличивает достоинства этого комплекса методов.
Вместе с тем динамическому программированию свойственны и недостатки. Прежде всего, в нем нет единого универсального метода решения. Практически каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения. Кроме того, большие объемы и трудоемкость решения многошаговых задач, имеющих множество состояний, приводят к необходимости отбора задач малой размерности либо использования сжатой информации. Последнее достигается с помощью методов анализа вариантов и переработки списка состояний.
Для процессов с непрерывным временем динамическое программирование рассматривается как предельный вариант дискретной схемы решения. Получаемые при этом результаты практически совпадают с теми, которые получаются методами максимума Л. С. Понтрягина или Гамильтона-Якоби-Беллмана.
Динамическое программирование применяется для решения задач, в которых поиск оптимума возможен при поэтапном подходе, например, распределение дефицитных капитальных вложений между новыми направлениями их использования; разработка правил управления спросом или запасами, устанавливающими момент пополнения запаса и размер пополняющего заказа; разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию; составление календарных планов текущего и капитального ремонтов оборудования и его замены; поиск кратчайших расстояний на транспортной сети; формирование последовательности развития коммерческой операции и т. д.
Суть метода динамического программирования.
В основу метода динамического программирования положен принцип оптимальности , сформулированный в 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.10)
Требуется найти оптимальное управление , при котором величина выигрыша (2.10) обращается в максимум.