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

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

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

Позднее формулировка понятия была доработана и усовершенствованна до современного вида самим же Беллманом.

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

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

В общем же для начала, неформальное определение понятия динамического программирования может звучать так:

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

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

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

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

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

Неформальное объяснение свойства оптимальности у подзадач может быть продемонстрировано с помощью диаграммы:
Есть задача, которую мы хотим решить при помощи ДП, т.е. найти какой-то план ее решения. Допустим эта задача сложна и сразу решить мы ее не можем. Мы берем малую подзадачу и решаем сначала ее (для x1). Затем используя это малое решение x1 , и не меняя структуру этого решения, решаем следующую задачу уже с x1 и x2 . И т.д.

Рис. 1.1. Неформальное объяснение свойства оптимальности у подзадач

Более подробно неформальное объяснение рассматривается .

Примеры, решаемых при помощи динамического программирования задач

Сначала рассмотрим задачи оптимизации (задачи 1-5):

1. Маршрут оптимальной длины

Пример: Есть некоторая карта дорог, представленная в виде графа. Наша цель: добраться из пункта А в пункт Б . Это сделать надо так, чтобы минимизировать расстояние или потраченное топливо.

Целевой функцией здесь является расстояние от А до Б . Т.е. наша цель — минимизировать расстояние.

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

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

2. Замена машины (минимизация расходов)

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

Целевая функция: минимизация расходов (либо на издержки на поддержку старого автомобиля, либо на покупку нового).

Переменная выбора: каждый год принимать решение продать машину или оставить.

3. Биржевой портфель

Пример: Игра на бирже, приобретение акций каких-либо компаний


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

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

4. Составление плана оптимального производства (логистика)

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


Целевая функция : максимизация прибыли.

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

5. Игры (вероятностные или не вероятностные)

Пример: Участие в различных играх


Целевая функция: максимизация вероятности выигрыша или максимизация среднего выигрыша и т.д.

Переменная выбора здесь зависит от конкретной игры.

Задачи 1 — 5 — это примеры задач оптимизации.

Комбинаторика:

6. Графы и деревья

Пример: Задача на решение того, сколько существует деревьев, у которых определенное число листьев; или сколько существует графов для решения такого-то задания и т.п.

7. Задача о размене монет или количество способов вернуть сдачу

Пример: Есть монеты разного достоинства, какими способами можно вернуть сдачу.

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

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

Неформальное объяснение оптимальности подзадач ДП.

Рассмотрим неформальную идею ДП.

Итак, возьмем пример с заводом, изготавливающим мебель.

Для достижения цели максимизации прибыли необходимо решить множество подзадач:

• сколько стульев произвести — переменная X1 ,
• сколько столов произвести — переменная X2 ,
• сколько нанять работников — переменная X3 ,
• … Хn .

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

Поэтому ДП предлагает следующее:

• берем одну подзадачу с переменной X1 , об остальных подзадачах пока забываем.

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

• После того, как найдем оптимальное решение для первой подзадачи, берем подзадачу для двух переменных Х1 и Х2 , и решаем ее с помощью уже найденного решения для первой подзадачи .
• Получаем решение уже для большей подзадачи, где фигурируют переменные Х1 и Х2 . Затем, используя полученное решение, берем подзадачи, охватывающие X1 , X2 и Х3 .
• И так продолжаем пока не получим решение для всей общей задачи.

Формальная идея ДП

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

Кроме того, может возникнуть такой вопрос: для того чтобы найти, например, минимум или максимум, почему бы нам не найти производную? или не использовать множества Ла-Гранжа, или другие методы аппарата математического анализа? Зачем нужно ДП, если есть большой арсенал средств?

Дело в том, что:

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

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

Важно: По этой причине разделение задачи на подзадачи и решение этих подзадач только один раз (!) , сокращая этим количество общих вычислений — более оптимальный способ, который и заложен в динамическом программировании

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

Простой пример решения задач при помощи ДП

Рассмотрим вариант решения задачи с помощью динамического программирования.

Пример: Необходимо вычислить сумму n чисел: 1 + 2 + 3 + ... + n

В чем состоит якобы «сложность» данной задачи: в том, что необходимо сразу взять большое количество чисел и получить ответ.

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

• Начнем с суммы одного первого элемента, т.е. просто берем первый элемент:
  F(1) = 1
• теперь с помощью решения для первого элемента, решим
  F(2) = F(1) + 2 = 1 + 2 = 3 , т.е. надо взять сумму первого элемента и добавить к нему второй элемент
• F(3) = F(2) + 3 = 6
• по аналогии продолжаем и получаем целевую функцию:
  F(n) = F(n-1) + An

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

Простой пример, где пока неоправданно используется ДП (искусственно), демонстрирует принцип идей ДП.

Рассмотрим еще один пример.

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

Решение:

Рассмотрим самые простые варианты (подзадачи):

Рассмотрим пример из i ступенек

Как мы можем попасть на i ступеньку:

1. с i-1 ступеньки, а на i-1 ступеньку мы могли попасть a i-1 способами
2. с i-2 ступеньки, а на i-2 ступеньку мы могли попасть a i-2 способами

Например, как попасть на 4-ю ступеньку :

Т.о., общее количество способов попасть на i ступеньку:
f(a i) = f(a i-1) + f(a i-2)

Определим начальные значения , с которых следует начинать решать задачу.
Если начинать с 1, то формула соответствует нахождению последовательности чисел Фибоначчи.

Мы видим, что задача по сути комбинаторная (т.е. количество способов сделать что-либо) свелась к вычислению некоторой рекуррентной последовательности.

Задание 1: реализовать пример для первых десяти ступенек (по сути, первые 10 чисел ряда Фибоначчи), используя рекурсию.

Дополните код:

1 2 3 4 5 6 7 8 9 10 11 12 13

var c: integer ; procedure getKolSposob(i, n: integer ) ; begin writeln (i+ n, " " ) ; inc(c) ; if ... then getKolSposob(...,... ) end ; begin c: = 1 ; getKolSposob(0 , 1 ) ; end .

var c:integer; procedure getKolSposob(i,n: integer); begin writeln (i+n," "); inc(c); if ... then getKolSposob(...,...) end; begin c:=1; getKolSposob(0,1); end.

Задание 2:
Решение 15-го типа заданий ЕГЭ (Графы. Поиск количества путей).

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

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

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

Энциклопедичный YouTube

• 1 / 5

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

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

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

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

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

  Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).

  Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи , F 3 = F 2 + F 1 {\displaystyle F_{3}=F_{2}+F_{1}} и F 4 = F 3 + F 2 {\displaystyle F_{4}=F_{3}+F_{2}} - даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали дважды. Если продолжать дальше и посчитать , то F 2 {\displaystyle F_{2}} посчитается ещё два раза, так как для вычисления F 5 {\displaystyle F_{5}} будут нужны опять F 3 {\displaystyle F_{3}} и F 4 {\displaystyle F_{4}} . Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решения для задач, которые он уже решал.

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

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

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

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

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

  Языки программирования могут запоминать результат вызова функции с определенным набором аргументов (мемоизация), чтобы ускорить «вычисление по имени». В некоторых языках такая возможность встроена (например, Scheme , Common Lisp , Clojure , Perl), а в некоторых требует дополнительных расширений (C++).

  Известны сериальное динамическое программирование, включённое во все учебники по исследованию операций , и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах.

  Обычное динамическое программирование является частным случаем несериального динамического программирования, когда граф взаимосвязей переменных - просто путь. НСДП, являясь естественным и общим методом для учета структуры задачи оптимизации, рассматривает множество ограничений и/или целевую функцию как рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причём эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объём вычислений на каждом этапе может сохраняться в разумных пределах.

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

  Классические задачи динамического программирования

  • Задача о наибольшей общей подпоследовательности : даны две последовательности, требуется найти самую длинную общую подпоследовательность.
  • Задача поиска наибольшей увеличивающейся подпоследовательности : дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.
  • Задача о редакционном расстоянии (расстояние Левенштейна) : даны две строки, требуется найти минимальное количество стираний, замен и добавлений символов, преобразующих одну строку в другую.
  • Задача о порядке перемножения матриц : даны матрицы A 1 {\displaystyle A_{1}} , …, A n {\displaystyle A_{n}} , требуется минимизировать количество скалярных операций для их перемножения.
  • Задача о выборе траектории
  • Задача последовательного принятия решения
  • Задача об использовании рабочей силы
  • Задача управления запасами

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

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

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

  История

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

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

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

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

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

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

  Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти 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

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

  4.1. Принцип оптимальности

  Рассмотрим систему

  и функционал

  (4.2)

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

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

  . (4.3)

  Пусть сначала найден минимум (4.2) и соответствующее ему оптимальное управление (рис. 14а):

  а потом – минимум (4.3) и оптимальное управление (рис. 14б):

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

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

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

  (4.6)

  Рис. 14а Рис.14б

  Тогда для первой задачи введем управление

  (4.7)

  и вычислим функционал

  

  При управлении (4.7) функционал (4.2) принимает меньшее значение, чем при (4.4). Но управлениеявляется оптимальным. Поэтому допущение (4.6) неверно.

  A предположение

  

  противоречит тому, что
  - управление, минимизирующее
  (4.3).

  Таким образом, остается, что

  ,

  и если оптимальное управление единственное, то

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

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

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

  . (4.8)

  Если
  - оптимальное управление, то

  .

  Оптимальное управление
  зависит от начального состояния
  в момент
  . Следовательно,является функцией оти:
  , а от управленияи его вариаций функция
  не зависит. Она вполне определяется значениями
  .

  Интервал
  разделим на два интервала
  и
  и выражение (4.8) запишем в виде:

  .

  Согласно принципу оптимальности последний участок также является оптимальным:

  (4.9)

  Обозначим:

  , (4.10)

  где
  - приращение вектора фазовых координат за время
  . Оно определяется согласно уравнениям движения (4.1). Подставляя
  из (4.10) в равенство (4.9), получим:

  .

  Хотя функция
  зависит только от фазовых координат и времени, ее нельзя выносить за знак
  . Значение приращения
  за время
  зависит от управления в интервале
  . Но
  не зависит от управления в интервале
  и ее можно внести под знак
  . Введем
  под знак минимума и разделим на
  :

  .

  Учитывая, что

  ;

  ,

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

  (4.11)

  Это соотношение состоит из двух утверждений:

  
  

  Если
  - управление, минимизирующее выражение
  , то основное уравнение метода динамического программирования

  (4.12)

  Здесь
  зависит от управления по определению, функция же
  не зависит от него. Тем не менее, производнаяот управления зависит. В этом можно убедиться, если ее представить в виде

  

  изаменить согласно системе (4.1):

  .(4.13)

  Подставляя (4.13) в (4.12) получим уравнение Р.Беллмана:

  . (4.14)

  Это уравнение в частных производных относительно
  , которое после подстановки
  становится нелинейным. Согласно определению(4.8) при
  должно выполняться конечное условие

  .

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

  В том случае, когда рассматривается функционал Больца

  (4.15)

  Уравнение (4.12) сохраняет силу, функция v в момент
  должна удовлетворять условию

  . (4.16)

  4.3. Две задачи оптимального управления

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

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

  . (4.17)

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

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

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

  Значительное развитие получила задача синтеза оптимального управления процессами, описываемыми линейной системой дифференциальных уравнений, при минимизации интегральных квадратичных функционалов. Она называется задачей аналитического конструирования оптимальных регуляторов (АКОР), или задачей А.М.Летова.

  4.4. Задача аналитического конструирования оптимальных регуляторов

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

  (4.18)

  Матрицы
  , размерности
  и
  , соответственно, имеют в качестве своих элементов известные функции
  .

  Предполагается также, что состояние системы (4.18) в каждый момент времени известно.

  В качестве критерия оптимальности рассматривается квадратичный функционал Больца

  где
  - симметричные неотрицательно определенные матрицы,
  - положительно определенная матрица; *) - индекс транспонирования.

  Требуется найти оптимальное (минимизирующее функционал 4.19) управление, являющееся функцией текущего состояния
  .

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

  В соответствии с этим методом нужно найти функцию
  , удовлетворяющего уравнению

  . (4.20)

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

  (4.21)

  где
  - есть некоторая, пока неизвестная, квадратичная форма, удовлетворяющая в силу (4.16) конечному условию

  . (4.22)

  Таким образом, для линейных систем задача сводится к отысканию функции
  . Дифференцируя (4.21) с учетом (4.18) получим

  

  Минимизируя (4.23) по
  , получим

  

  (4.24)

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

  Подставляя (4.24) в (4.23), получим

  Квадратичная форма (4.25) равна нулю при любых
  только в том случае, когда равна нулю матрица, ее образующая. Таким образом, получаем уравнение для определения матрицы
  

  (2.26)

  с граничным условием (4.22).

  Интегрируя уравнение (4.26) в обратном направлении, получим
  , а значит и параметры оптимального управления (4.24). Нетрудно показать, что матрица
  - симметричная матрица. Для этого достаточно транспонировать уравнение (4.26). Тогда

  откуда с учетом симметричности матриц следует, что
  .

  Замечание 1 . В том случае, когда система (4.18) стационарна (матрицы A и B – числовые матрицы), матрицы - числовые матрицы,
  (рассматривается установившийся режим). Матрицатоже числовая и удовлетворяет алгебраическому уравнению

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

  4.5. Синтез локально-оптимального управления

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

  Рассмотрим непрерывный управляемый процесс, описываемый системой дифференциальных уравнений (4.18).

  Пусть задан функционал (функция)
  параметрически зависящий от времении определенный на множестве функций
  и
  .

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

  В качестве критерия оптимальности рассмотрим функционал

  матрица удовлетворяют тем же требованиям, что и в параграфе 4.4.

  Нетрудно показать , что локально-оптимальное уравнение
  с необходимостью удовлетворяет условию

  . (4.28)

  Воспользуемся этим условием.

  Тогда, дифференцируя (4.27) в силу (4.18), найдем выражение для определения производной
  

  из условия
  найдем локально-оптимальное управление

  Найденное управление действительно доставляет производной
  , так как

  .

  Из выражения (4.30) следует, что локально-оптимальное управление полностью определяется матрицами
  , а для реализации его необходима полная информация о состоянии процесса
  . Задаваясь различными матрицами весовых функций
  , можно обеспечить те или иные свойства управляемого процесса, в частности свойства устойчивости или асимптотической устойчивости.

  Потребуем, например, чтобы на локально-оптимальном управлении выполнялось условие

  . (4.31)

  Тогда, подставляя (4.30) в (4.29), из (4.31) найдем

  (4.32)

  Из условия (4.32) следует, что оно будет выполнено, если матрица
  будет определена из условия

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

  (4.34)

  Тогда из сравнения формул (4.24), (4.26), (4.22) и (4.30), (4.33), (4.34) следует, что локально-оптимальное управление(4.30) по критерию (4.27) с матрицей
  , определяемой из уравнения (4.33) с условием (4.34) совпадает с управлением (4.24), оптимальным по квадратичному критерию (4.19) на интервале
  .

  5. Оптимальное управление стохастическими системами в условиях неопределенности.

  5.1. Характеристики случайных сигналов

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

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

  Через
  будем обозначать реализацию случайного процесса
  .

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

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

  или -мерная плотность распределения

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

  Часто, особенно в прикладных задачах, для статистического описания случайных процессов используют начальные
  ицентральные
  моменты -гo порядка. Здесь символом
  обозначена операция осреднения (математического ожидания). Наиболее важную роль играют следующие моменты:

  Математическое ожидание (среднее значение)

  ; (5.3)

  Дисперсия случайного процесса

  Второй начальный момент

  где
  - центрированный случайный процесс с нулевым математическим ожиданием;

  Среднеквадратичное отклонение

  . (5.6)

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

  . (5.7)

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

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

  .

  Гауссовский процесс полностью определяется заданием математического ожидания
  и корреляционной функции
  .

  Важной характеристикой стационарного случайного процесса в широком смысле является спектральная плотность
  - плотностьраспределения дисперсии (энергии) по частотам.

  Спектральная плотность
  и корреляционная функция
  связаны прямым и обратным преобразованием Фурье:

  ; (5.8)

  . (5.9)

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

  Наряду со скалярными случайными процессами можно рассматривать и векторные случайные процессы:

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

  Математическое ожидание :

  ; (5.11)

  Дисперсионная матрица
  :

  (5.12)

  с элементами

  ; (5.13)

  Ковариационная матрица
  :

  (5.14)

  с элементами

  ; (5.15)

  Матрица

  с элементами

  . (5.17)

  Здесь
  означает транспонирование.

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

  Матрицы
  ,
  и
  обладают следующими свойствами:

  ; (5.18)

  для всех и (5.I9)

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

  . (5.21)

  Матрица
  обладает следующим свойством:

  (5.22)

  5.2. Математическое описание линейных систем при случайных возмущениях.

  В общем виде уравнение управляемой динамической системы может быть записано в виде:

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

  Если параметр меняется непрерывно, то такую систему будем называть непрерывной; если меняется дискретно, то система называется дискретной.

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

  В данном учебном пособии будут рассматриваться только линейные системы.

  Рассмотрим системы, описываемые дифференциальными уравнениями.

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

  Здесь
  ,
  ,
  - матрицы размерностей соответственно. Элементами этих матриц являются непрерывные функции. Если матрицы
  иявляются постоянными, то управляемаясистема называется стационарной. Уравнения (5.24) обычно называют уравнениями состояния, так как они описывают изменение переменных состояния системы во времени.

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

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

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

  (5.26)

  В интегральной форме решение системы (5.24), в соответствии с формулой Коши, можно представить в следующем виде:

  (5.27)

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

  Относительно системы (5.24), (5.25) сделаем следующие предположения:

  (5.28)

  Из соотношений (5.28) видно, что случайные процессы
  и
  являются процессами типа белого шума. Матрицы
  и вектор считаются известными. Предполагаются известными в каждый момент времени и управляющие воздействия.

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

  а) собственно дискретные системы, такие как ЦВМ, автоматы различных типов и т.д.;

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

  Рассмотрим поведение непрерывной системы с дискретным управлением, которое можно представить в виде кусочно-постоянной вектор-функции (рис. 15), т.е. управляющие воздействия можно записать в следующем виде:

  для (5.29)

  где - последовательность моментов времени, не обязательно равноотстоящих друг от друга.

  Если нас интересует состояние системы только в дискретные моменты времени , то непрерывную систему (5.24) в эти моменты, используя соотношение (5.27), можно записать в следующем виде:

  (5.30)

  Учитывая (5.29), соотношение (5.30) перепишем в виде:

  (5.31)

  Третье слагаемое в соотношении (5.3I) можно рассматривать как некоторую случайную последовательность. В том случае, когда случайный процесс типа белого шума, то справедливо следующее соотношение:

  ,

  где
  - чисто случайная последовательность.

  Вводя обозначения

  (5.32)

  систему уравнений (5.31) запишем в виде:

  Матрицы называются переходными матрицами по состоянию, управлению и возмущению соответственно;
  - дискретное время.

  Уравнение измерений, соответственно, можно записать в виде:

  Иногда систему (5.33) - (5.34) записывают в следующем виде:

  Относительно систем (5.33), (5,34) будем предполагать, что:

  (5.37)

  Пример. Рассмотрим вращательное движение тела вокруг одной из осей под действием возмущающего момента
  . Уравнения движения имеют вид:

  , (5.38)

  где - момент инерция тела;- угол поворота тела в некоторойинерциальной системе координат. Вводя новые переменные

  (5.39)

  получим уравнения движения объекта в нормальной форме:

  (5.40)

  Для этой системы уравнений фундаментальная матрица
  состоит из двух вектор-столбцов решений следующей системы уравнений

  

  с начальными условиями

  

  Отсюда следует, что матрица
  имеет вид:

  (5.41)

  Этот же результат получается, если искать матрицу
  в виде ряда:

  

  Рассмотрим поведение системы (5.40) через равные промежутки времени в моменты , т.е.
  .

  На основании соотношений (5.3I) - (5.33), полагая, что
  постоянно на шаге дискретности, получим следующую эквивалентную дискретную систему:

  (5.43)

  (5.44)

  В дальнейшем необходимо получить зависимость
  не только от и
  , но оти всех предшествующих
  . Используя соотношения (5.33), для различныхможно записать:

  

  Продолжая соответствующие выкладки, можно получить соотношение

  , (5.45)

  где матрица
  определяется следующим образом:

  причем
  при
  .

  Полученные соотношения (5.45), (5.46) будут использованы при статистическом анализе дискретных систем.

  5.3. Уравнения моментов для линейных систем

  Сначала рассмотрим непрерывные системы. Пусть уравнения движения имеют вид;

  . (5.47)

  Относительно возмущающих воздействий
  и начального состояния будем предполагать, что они удовлетворяют условиям (5.28).

  При получении соотношений для математического ожидания состояния системы
  осредним уравнение (5.47):

  

  Учитывая (5.28), получим:

  . (5.48)

  На основании (5.47), (5.48) уравнение для центрированной составляющей
  имеет вид:

  . (5.49)

  Теперь найдем уравнение для дисперсионной матрицы . Дифференцируя по матрицу
  и учитывая, что матрицы
  и
  не случайные, получим:

  (5.50)

  Для вычисления математического ожидания
  используем формулу Коши (5.27):

  . (5.51)

  Умножив выражение (5.51) справа на
  , осредниви учитывая (5.28), получим:

  (5.52)

  С учетом того, что

  , (5.53)

  уравнение (5.50) примет вид;

  с начальным условием
  .

  Теперь пусть поведение системы описывается дискретным уравнением

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

  Осредняя (5.55) и учитывая (5.37), получим:

  Уравнение для центрированной составляющей
  имеет вид:

  Используя (5.57) и (5.37), найдем уравнение для дисперсионной матрицы
  :

  (5.58)

  Определим математическое ожидание
  , используясоотношение (5.45) и свойства (5.37):

  (5.59)

  Аналогично

  .

  Таким образом, уравнение для определения матрицы
  имеет вид:

  5.4. Задача оптимальной фильтрации и ее решение методом Калмана

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

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

  где
  --мерный вектор состояния,
  --мерный вектор возмущающих воздействий,
  и
  матрицы соответствующих размерностей.

  Пусть измерению поддается
  -мерный вектор некоторых комбинаций функций состояния (5.25)

  где
  - погрешность измерения.

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

  Математически задача оптимальной фильтрации ставится как задача отыскания оценки
  состояния системы (5.61)
  на основе имеющейся информации
  .

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

  (5.63)

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

  Так как
  , то всегда будет ошибка оценки

  .

  Тогда для определения искомых матриц
  и
  можно использовать условие несмещенности оценки

  (5.64)

  и условие ее оптимальности

  где
  - симметричная положительно определенная матрица.

  Для того, чтобы использовать условия (5.64) и (5.65) найдем уравнение для ошибки оценивания. Вычитая (5.63) из (5.61) с учетом (5.62), получим

  Если теперь положить, что

  то уравнение для ошибки оценки
  примет вид:

  с начальным условием

  . (5.68)

  Из (5.67), (5.68) следует, что условие несмещенности оценки (5.64) будет выполнено, если положить

  . (5.69)

  Чтобы убедиться в этом, достаточно взять математическое ожидание от выражений (5.67), (5.68)

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

  Остается определить матрицу
  из условия минимума критерия (5.65). Примем для простоты выкладок, что
  - постоянная единичная матрица, тогда

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

  . (5.71)

  Нетрудно показать, что минимизация производной критерия обеспечивает минимум и для самого критерия

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

  . (5.72)

  Подставив в (5.72) выражение для из (5.67) и соответствующее выражение для , получим:

  (5.73)

  Найдем
  , для чего запишем уравнение Коши для (5.67):

  где
  - весовая матричная функция. Тогда

  Используем свойство дельта-функции:

  ,

  если имеетразрыв в точке
  .

  Поскольку
  

  . (5.74)

  Аналогично можно найти
  :

  . (5.75)

  Подставив полученные выражения для
  и соответственно транспонированные выражения для
  в (5.73) получим:

  Следующее тождество легко проверить, раскрыв в правой части скобки и использовав симметрию матрицы
  :

  С учетом тождества приведем уравнение (5.76) к виду:

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

  При этом последний член в уравнении (5.78) обращается в нуль и уравнение приобретает вид

  с начальным значением
  .

  Итак, можем записать уравнение фильтра

  Уравнения (5.79), (5.80), (5.81) представляют собой уравнения фильтра Калмана-Бьюси.

  Система оценивания (фильтр) схематически представлена на рис. 16.

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

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

  Запишем уравнения стационарного фильтра Калмана в следующем виде:

  ; (5.83)

  Один из часто используемых способов решения уравнения (5.84) (обычно с помощью ЦВМ) заключается в решении нестационарного уравнения (5.80) с соответствующими постоянными значениями коэффициентов, из которых составлены матрицы А, С, Q, R, и произвольной неотрицательно определенной матрицей начальных условий для в текущем времени до тех пор, пока полученное решение не достигнет постоянного установившегося значения. Это окончательное значение принимается за искомое решение уравнения (5.84). Такой способ решения удобен тем, что алгоритмы решения дифференциальных уравнений, как правило, эффективнее алгоритмов решения нелинейных алгебраических уравнений.

  Замечание 1.

  Важным свойством полученной ошибки является то, что она некоррелирована с ошибкой оценивания, т.е.

  .

  Замечание 2.

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

  которая может быть представлена в виде (5.62)

  Замечание 3.

  Для управляемых систем, описываемых совокупностью уравнений

  Уравнение фильтра может быть получено аналогично. В этом случае уравнение фильтра будет иметь вид

  где матрица
  , а корреляционная матрица
  , как и раньше, находится из матричного уравнения

  с начальным условием
  .

  Система оценивания (фильтр) схематически представлена на рис. 17.

  5.5. Синтез локально-оптимального управления линейными стохастическими системами при полной и точной информации.

  Пусть управляемое движение в условиях воздействия возмущений описывается системой уравнений

  Случайный процесс
  и начальное состояние будем считать независимыми, обладающими свойствами (5.28). Предполагается, что состояние
  в любой момент времени известно. Будем искать управление
  как некоторую линейную функцию текущего состояния

  . (5.88)

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

  В качестве функционала, характеризующего управляемое движение, возьмем математическое ожидание локального функционала
  (4.27)

  .

  Введем матрицу корреляционных моментов

  . (5.89)

  Используя (5.88), (5.89) функционал можно
  преобразовать к виду

  (5.90)

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

  Найдем уравнение для ее определения. Уравнение управляемого процесса (5.87) с учетом (5.88) можно представить в виде

  

  где матрица

  B соответствии с (5.54) уравнение для матрицы
  будет иметь вид

  или, с учетом (5.91),

  (5.92)

  Начальным условием является, очевидно,

  Из (5.92), (5.93) с учетом предположения о симметричности матриц ,
  непосредственно следует, что матрица
  является симметричной, т.е.
  .

  Таким образом, задача определения оптимального управления свелась к задаче определения матрицы
  из условия минимума
  (5.90). Для нахождения ее воспользуемся условием (4.28). Дифференцируя (5.90) и учитывая (5.92), получим

  

  Выпишем составляющие
  , зависящие от
  :

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

  .

  где
  - произвольная малая вариация матричной функции
  из рассматриваемого класса.

  Приращение
  , вызванное вариацией матрицы
  , будет иметь вид

  Тогда из (5.94) следует, что

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

  Найденное значение
  действительно доставляет минимум
  , так как вторая вариация

  в силу определенной положительности матрицы
  . Здесь.

  Сравнивая (5.88), (5.95) с (4.30), видим, что найденное локально-оптимальное управление полностью совпадает с локально-оптимальным управлением для детерминированного случая.

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

  Аналогичный результат имеет место и при квадратичном критерии качества (4.19).

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

  5.6. Синтез локально-оптимального управления линейными стохастическими системами (теорема разделения).

  Пусть управляемое движение описывается уравнением (5.87), а уравнение измерения – (5.62).

  Рассмотрим задачу синтеза, оптимального по критерию

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

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

  Наряду с системой (5.87) рассмотрим соответствующую ей неуправляемую систему

  с уравнением измерения

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

  (5.98)

  с начальным условием

  

  где матрица
  определяется из уравнений (5.79), (5.80).

  Из уравнений (5.87) и (5.97) следует, что

  , (5.99)

  где
  - фундаментальная матрица решений систем (5.87).

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

  (5.100)

  Из (5.99) и (5.100) следует, что

  Найдем теперь уравнение для определения
  . Для этого дифференцируя (5.100), получим

  

  Учитывая (5.98), найдем

  (5.101)

  

  Тогда уравнение фильтра окончательно запишется в виде (5.85)

  с начальным условием

  , (5.103)

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

  Теорема разделения. Локально-оптимальное управление системой (5.87) по критерию (5.96) имеет вид:

  Здесь
  - заданные матрицы локального функционала, а
  - решение векторного уравнения (5.102) с начальным условием (5.103).

  Доказательство. Рассмотрим функционал (5.96). Учитывая, что оценки
  и ошибка оценки
  не коррелированны для всех, функционал (5.96) можно представить в виде

  ,

  

  Так как на
  не влияет ни
  , ни
  , то задача сводится к минимизациипри условиях (5.102), (5.103). При этом оценка является полностью наблюдаемой.

  Рассмотрим выражение

  

  Учитывая, что , нетрудно показать , что

  Таким образом, в уравнении (5.102) выражение
  можно рассматривать как эквивалентный «белый шум» с корреляционной матрицей
  .

  В результате мы пришли к задаче синтеза локально-оптимального уравнения в системе (5.102), (5.103), возмущаемой «белым шумом» при полном и точном измерении ее состояния, решение которой было дано в предыдущем разделе. Теорема доказана. Можно показать, что теорема разделения справедлива и при синтезе оптимального управления по квадратичному решению.

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

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

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

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

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

  Классической задачей на последовательности является следующая.

  Последовательность Фибоначчи F n задается формулами: F 1 = 1, F 2 = 1,
  F n = F n - 1 + F n - 2 при n > 1. Необходимо найти F n по номеру n .

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

  Int F(int n) { if (n < 2) return 1; else return F(n - 1) + F(n - 2); }
  Используя такую функцию, мы будем решать задачу «с конца» — будем шаг за шагом уменьшать n , пока не дойдем до известных значений.

  Но как можно заметить, такая, казалось бы, простая программа уже при n = 40 работает заметно долго. Это связано с тем, что одни и те же промежуточные данные вычисляются по несколько раз — число операций нарастает с той же скоростью, с какой растут числа Фибоначчи — экспоненциально.

  Один из выходов из данной ситуации — сохранение уже найденных промежуточных результатов с целью их повторного использования:

  Int F(int n) { if (A[n] != -1) return A[n]; if (n < 2) return 1; else { A[n] = F(n - 1) + F(n - 2); return A[n]; } }
  Приведенное решение является корректным и эффективным. Но для данной задачи применимо и более простое решение:

  F = 1; F = 1; for (i = 2; i < n; i++) F[i] = F + F;
  Такое решение можно назвать решением «с начала» — мы первым делом заполняем известные значения, затем находим первое неизвестное значение (F 3), потом следующее и т.д., пока не дойдем до нужного.

  Именно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все F i для i < n ), затем, зная решения подзадач, нашли ответ (F n = F n - 1 + F n - 2 , F n - 1 и F n - 2 уже найдены).

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

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

  Пусть исходная задача заключается в нахождении некоторого числа T при исходных данных n 1 , n 2 , ..., n k . То есть мы можем говорить о функции T (n 1 , n 2 , ..., n k ), значение которой и есть необходимый нам ответ. Тогда подзадачами будем считать задачи
  T (i 1 , i 2 , ..., i k ) при i 1 < n 1 , i 2 < n 2 , ..., i k < n k .

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

  При n < 32 полный перебор потребует нескольких секунд, а при n = 64 полный перебор не осуществим в принципе. Для решения задачи методом динамического программирования сведем исходную задачу к подзадачам.

  При n = 1, n = 2 ответ очевиден. Допустим, что мы уже нашли K n - 1 , K n - 2 — число таких последовательностей длины n - 1 и n - 2.

  Посмотрим, какой может быть последовательность длины n . Если последний ее символ равен 0, то первые n - 1 — любая правильная последовательность длины
  n - 1 (не важно, заканчивается она нулем или единицей — следом идет 0). Таких последовательностей всего K n - 1 . Если последний символ равен 1, то предпоследний символ обязательно должен быть равен 0 (иначе будет две единицы подряд), а первые
  n - 2 символа — любая правильная последовательность длины n - 2, число таких последовательностей равно K n - 2 .

  Таким образом, K 1 = 2, K 2 = 3, K n = K n - 1 + K n - 2 при n > 2. То есть данная задача фактически сводится к нахождению чисел Фибоначчи.

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

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

  Приведем пару формулировок таких задач:

  Задача 2. n *m клеток. Можно совершать шаги длиной в одну клетку вправо или вниз. Посчитать, сколькими способами можно попасть из левой верхней клетки в правую нижнюю.

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

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

  Рассмотрим более подробно задачу 2. В некоторую клетку с координатами (i ,j ) можно прийти только сверху или слева, то есть из клеток с координатами (i - 1, j ) и (i , j - 1):

  

  Таким образом, для клетки (i , j ) число маршрутов A[i][j] будет равно
  A[j] + A[i], то есть задача сводится к двум подзадачам. В данной реализации используется два параметра — i и j — поэтому применительно к данной задаче мы говорим о двумерном динамическом программировании.

  Теперь мы можем пройти последовательно по строкам (или по столбцам) массива A, находя число маршрутов для текущей клетки по приведенной выше формуле. Предварительно в A необходимо поместить число 1.

  В задаче 3 в клетку с координатами (i , j ) мы можем попасть из клеток с координатами
  (i - 1, j), (i , j - 1) и (i - 1, j - 1). Допустим, что для каждой из этих трех клеток мы уже нашли маршрут минимального веса, а сами веса поместили в W[j], W[i],
  W. Чтобы найти минимальный вес для (i , j ), необходимо выбрать минимальный из весов W[j], W[i], W и прибавить к нему число, записанное в текущей клетке:

  W[i][j] = min(W[j], W[i], W) + A[i][j];

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

  На следующем рисунке приведен пример исходных данных и одного из шагов алгоритма.

  

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

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

  Задачи на подпоследовательности

  Рассмотрим задачу о возрастающей подпоследовательности.

  Задача 4. Дана последовательность целых чисел. Необходимо найти ее самую длинную строго возрастающую подпоследовательность.

  Начнем решать задачу с начала — будем искать ответ, начиная с первых членов данной последовательности. Для каждого номера i будем искать наибольшую возрастающую подпоследовательность, оканчивающуюся элементом в позиции i . Пусть исходная последовательность хранится в массиве A. В массиве L будем записывать длины максимальных подпоследовательностей, оканчивающихся текущим элементом. Пусть мы нашли все L[i] для 1 <= i <= k - 1. Теперь можно найти L[k] следующим образом. Просматриваем все элементы A[i] для 1 <= i < k - 1. Если
  A[i] < A[k], то k -ый элемент может стать продолжением подпоследовательности, окончившейся элементом A[i]. Длина полученной подпоследовательности будет на 1 больше L[i]. Чтобы найти L[k], необходимо перебрать все i от 1 до k - 1:
  L[k] = max(L[i]) + 1, где максимум берется по всем i таким, что A[i] < A[k] и
  1 <= i < k .

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

  Чтобы восстановить саму подпоследовательность, можно для каждого элемента также сохранять номер предыдущего выбранного элемента, например, в массив N.

  Рассмотрим решение этой задачи на примере последовательности 2, 8, 5, 9, 12, 6. Поскольку до 2 нет ни одного элемента, то максимальная подпоследовательность содержит только один элемент — L = 1, а перед ним нет ни одного — N = 0. Далее,
  2 < 8, поэтому 8 может стать продолжением последовательности с предыдущим элементом. Тогда L = 2, N = 1.

  

  Меньше A = 5 только элемент A = 2, поэтому 5 может стать продолжением только одной подпоследовательности — той, которая содержит 2. Тогда
  L = L + 1 = 2, N = 1, так как 2 стоит в позиции с номером 1. Аналогично выполняем еще три шага алгоритма и получаем окончательный результат.

  

  Теперь выбираем максимальный элемент в массиве L и по массиву N восстанавливаем саму подпоследовательность 2, 5, 9, 12.

  Еще одной классической задачей динамического программирования является задача о палиндромах.

  Задача 5. Дана строка из заглавных букв латинского алфавита. Необходимо найти длину наибольшего палиндрома, который можно получить вычеркиванием некоторых букв из данной строки.

  Обозначим данную строку через S, а ее символы — через S[i], 1 <= i <= n . Будем рассматривать возможные подстроки данной строки с i -го по j -ый символ, обозначим их через S (i , j ). Длины максимальных палиндромов для подстрок будем записывать в квадратный массив L: L[i][j] — длина максимального палиндрома, который можно получить из подстроки S (i , j ).

  Начнем решать задачу с самых простых подстрок. Для строки из одного символа (то есть подстроки вида S (i , i )) ответ очевиден — ничего вычеркивать не надо, такая строка будет палиндромом. Для строки из двух символов S (i , i + 1) возможны два варианта: если символы равны, то мы имеем палиндром, ничего вычеркивать не надо. Если же символы не равны, то вычеркиваем любой.

  Пусть теперь нам дана подстрока S (i , j ). Если первый (S[i]) и последний (S[j]) символы подстроки не совпадают, то один из них точно нужно вычеркнуть. Тогда у нас останется подстрока S (i , j - 1) или S (i + 1, j ) — то есть мы сведем задачу к подзадаче: L[i][j] = max(L[i], L[j]). Если же первый и последний символы равны, то мы можем оставить оба, но необходимо знать решение задачи S (i + 1, j - 1):
  L[i][j] = L + 2.

  Рассмотрим решение на примере строки ABACCBA. Первым делом заполняем диагональ массива единицами, они будут соответствовать подстрокам S (i , i ) из одного символа. Затем начинаем рассматривать подстроки длины два. Во всех подстроках, кроме S (4, 5), символы различны, поэтому в соответствующие ячейки запишем 1, а в L — 2.

  Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали, ведущей из левого верхнего угла в правый нижний. Для подстрок длины 3 получаются следующие значения: в подстроке ABA первая и последняя буквы равны, поэтому
  L = L + 2. В остальных подстроках первая и последняя буквы различны.

  BAC: L = max(L, L) = 1.
  ACC: L = max(L, L) = 2.
  CCB: L = max(L, L) = 2.
  CBA: L = max(L, L) = 1.

  

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