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

Обновлено 22 октября 2019г. в 19:25: Убраны битые ссылки, исправлены мелкие опечатки.
Недавно столкнулся с одним развесёлым мнением (забавно, что от программиста), дескать "Теорию множеств" знать не обязательно, можно до всего допереть самостоятельно. И это говорил человек, ежедневно в своей работе использующий операции конъюнкции и дизъюнкции ("и" и "или"), булевы функции (множественные условия), кванторы («для любого…», «существует…»), предикаты (функция дающая в результате "0" или "1", назовите её логическим выражением, если хотите).
В определённой степени человек прав, можно и вправду не знаю всего этого программировать. Но что на выходе?
1393671711_193794874.jpg
Может и со строительством так же? Ну его в пень - этот сопромат, я и без него высотку построю... Ну вот с теорией множеств всё точно так же - это язык на котором говорит математика. Ну её в пень... Итак, о чём собственно разговор. В ДОТУ описывается математический аппарат теории управления. Ссылается он на некий учебник: “Курс теории автоматического управления” (автор Палю де Ла Барьер: французское издание 1966 г., русское издание — “Машиностроение”, 1973 г.), в котором подробно изложен весь необходимый для понимания метода объём знаний. Возвращаемся к описанию метода динамического программирования:
1. Сущность метода

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

Хn+1 = f(Xn,Un,n)

(6)

где Хn обозначает положение системы в момент n; Un — значение управления в момент n.

Обозначим через H пространство состояний (Xn Є H), а через Kn(Xn) —множество допустимых значений Un в момент n, если система находится в состоянии Xn(Un Є Hn(Xn)). Если Kn(Xn) является фиксированным, то мы его обохначим через K. Последовательность U0,U1,...,Un (конечная или бесконечная) (где Un Є Hn(Xn)) называется управлением.

Зная управление и начальное состояние системы, мы можем определить при помощи уравнения (6) её последующие состояния. Последовательность X0,X1,...,Xn,... называется траекторией системы, соответствующей управлению U0,U1,...,Un,... Наоборот, любая последовательность X0,X1,...,Xn,... называется допустимой траекторией, если она реализуется одной или несколькими управлениями. Число N рассматриваемых шагов будем называть горизонтом. Будем считать его конечным. Задача теперь заключается в том, чтобы для заданного начального состояния найти такое управление, которое реализовало бы максимум критерия вида v0(X0, U0) + v1(X1, U1) + ... +
vn-1(Xn-1, Un-1) +
vn(Xn).
Правила хорошего оформления книг гласит: если в книге больше трёх формул - её читать не будут. В одном только приведённом фрагменте таких формул почти два десятка. Кто это будет читать? Надо отдать должное ВП, в ДОТУ число формул заметно меньше и читается, соответственно полегче. Однако полностью уйти от аппарата теории множеств не получилось (взять хотя бы "вектора"). Напрашиваются два варианта решения задачи понимания указанного отрывка:
  1. изучение "Теории множеств";
  2. попытаться изобрести свою собственную "Теорию множеств" без страшных формул (та сказать шагнуть на пару тройку веков в прошлое, когда уравнения с неизвестными писались прописью на пол страницы... без использования специальных символов).
Если честно, изложение теории множеств в указанном учебнике просто ужасно. Автор ужасен в своей занудности. На сегодняшний день выпущен оогромное множество простых в освоении учебных пособий по теории множеств. Гораздо быстрее получится скачать с какого-нибудь студенческого ресурса современный учебник.

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

Взглянем ещё разок на метод. Условно, его можно разделить на три этапа:

  1. Формализовать имеющуюся задачу
  2. Заполнить входные данные
  3. Произвести расчёт

Рассмотрим первые два этапа.

Описание системы задаётся согласно рекуррентному соотношению Xn+1 = f (Xn, Un, n). Понимать эту формулу следует так: чтобы определить состояние системы на следующем этапе (Xn+1) нужно к текущему состоянию системы (Xn) применить управление (Un). Чтобы понимать подобного рода "закорючки" настоятельно рекомендую ознакомиться с основами теории множеств, например из указанной ранее книги.

Далее нам нужно определить входные данные для использования метода. Приведу описание из книги Палю де Ла Барьера с некоторым и комментариями:
параметр пояснение Контекст
1 n рассматриваемый шаг  
2 Xn Состояние системы в момент n Состояние системы описывается в виде значения набора параметров. Например: (а1 = 10; а2 = 3; а3 = 0) записывается просто как (10; 3; 0).
3 Un Управление в момент n Управление описывается в виде значений набора параметров. Например (у1 = 4; у2 = 5; у3 = 7) записывается просто как (4; 5; 7). Управление должно переводить одно состояние системы в другое.
4 H Пространство состояний Xn Речь идёт о построении всевозможных состояний системы. Именно эта потребность хранить много данных в указанном методе в своё время похоронила повсеместное его внедрение. В конце концов, если состояние системы описывается доброй сотней параметров, а число всевозможных состояний забегает за тысячу, что вполне допустимо в рамках больших производств, возникают серьёзные проблемы с дисковым пространством.
5 Kn(Xn) Множество допустимых значений управлений (Un) в момент рассматриваемый момент (n) Построив указанные связи (состояние такое-то может перейти в такие то состояния) мы как раз и получаем граф.
6 K Фиксированное множество допустимых значений управлений (Kn(Xn))/ Понятно, что на практике бесконечные граф нас не интересуют. В наших силах решать только конечные задачи, поэтому, когда мы построим граф с состояниями системы в его вершинах и управлениями в качестве рёбер мы сможем зафиксировать множество допустимых управлений.
7 U0,U1,...,Un,… управление Одно шаговое управление переводит систему из одного состояния в другое. Цепочка таких шаговых управлений приведёт нас из одной вершины графа в другую.
8 X0,X1,...,Xn,… Траектория системы, соответствующая управлению U0,U1,...,Un,… Выполняя последовательно управления из, указанной в предыдущем пункте, цепочки шаговых управлений мы последовательно будем проходить вершины графа. Последовательность пройденных нами вершин и будет траекторией системы.
Отдельно подчеркну, что каждая вершина - это набор конкретных значений. Например. мы имеем начальное состояние системы (1; 3; 2; 0) и цепочку из трёх шаговых управлений (1;1;0;1), (2;0;0;1) и (0;0;3;2). Наша траектория системы будет следующей: (1; 3; 2; 0),(2; 4; 2; 1),(4; 4; 2; 2),(4; 4; 5; 4). (Операция сложения в качестве управляющего воздействия выбрана только в качестве примера).
9 N Горизонт Число рассматриваемых шагов.
Данные заполнены. Можно переходить к расчёту.

Выполнив первые два шага мы имеем что-то вроде этого:
 

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

В книге Палю де Ла Барьера эти числа появляются вот здесь:

Задача теперь заключается в том, чтобы для заданного начального состояния найти такое управление, которое реализовало бы максимум критерия вида
v0(X0, U0) + v1(X1, U1) + ... + vn-1(Xn-1, Un-1) + vn(Xn).

Здесь идёт речь о затратах на шаговое управление. Смысл в том, что перевод системы из одного состояния системы в другое требует затрат. В качестве оценки затрат можно использовать любой из параметров управления. Управление, напоминаю - это набор значений (у1=1; у2 =1; у3 = 4; и т.д.), а можно поставить совокупный параметр затрат связанный с этими значениями. В нашем случае я поставил числа наобум.

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

В нашем случае оптимальной с точки зрения максимума указанной суммы будет следующая траектория: (0;1;4), (1;3;5), (2;1;5).

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