Управляемые процессы

 

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

В модели динамического программирования процесс находится на каждом шаге в одном из состояний s множества состояний S, и «управляющий процесса» принимает решение q, учитывая номер этого шага и состояние. В зависимости от q (а зависимость от s спрятана в самом решении, будем считать, что q Î Qs и множества Qs для различных s не пересекаются) процесс переходит в новое состояние s(q). Процесс продолжается до тех пор, пока он не попадет в специальное терминальное состояние St  или не кончится ресурс времени. Так получается траектория процесса, которая состоит из последовательности пар  , заканчивающейся терминальным состоянием. Для единообразия добавим множество Qst из одного терминального решения, оставляющего процесс в том же терминальном состоянии, и положим

Предположим, что на множестве таких последовательностей задана функция  f(τ), АМ-тивная, т. е. существуют такие функции  φ,ψ:Q→R, что

 

f(τ)=φ(head τ)+ψ(head τ)×f(tail τ),

 

если строка непустая и задано значение  f({St})

Функция f вводится как целевая функция процесса; «управляющий» стремится выбирать решения так, чтобы построить траекторию с минимальным (для определенности) значением f.

Пример. Задача о кратчайшем пути. Требуется построить в графе <M,N>  кратчайший путь от начальной вершины i0 до заданной вершины it. Здесь множеством состояний является М, а в каждом состоянии i Î М, кроме терминального состояния it, множество возможных решений — это множество дуг, начинающихся в i:

 

 Q={uºN, beg u=i}

 

Каждому решению и Î Qi сопоставляется новое состояние  σ(u)=end u, конец дуги и. Целевая функция в этой задаче аддитивна, мы минимизируем сумму длин дуг, входящих в путь, так что φ(u)=l[u].

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

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

Будем теперь варьировать начальное состояние s0. Обозначим через v(s) минимальное значение целевой функции для процесса с начальным состоянием s0 = s, т. е.

 

v(s)=min {f(τ)|q0, q1,…}

 

У нас получилась некоторая функция от s, которую принято называть функцией Беллмана. Минимум в приведенной формуле берется по всем допустимым последовательностям решений  q0, q1, Его можно представить как последовательный минимум: «внешний» минимум по q0, а «внутренний», при фиксированном q0, по оставшейся последовательности   q1, q2,…

 

 v(s)={ min {f(τ)|q0, q1q2,…}}

 

 

Цель такого расщепления понятна, мы сейчас воспользуемся свой­ством АМ-тивности целевой функции

 

v(s)={ min{ φ(head τ)+ψ(head τ)×f(tail τ)|q0, q1q2,…}}

 

 

Слагаемое  φ(head τ) и неотрицательный множитель ψ(head τ) не зависят от параметров, по которым берется внутренний минимум, поэтому их можно вынести за минимум (поскольку, очевидно,

 

min {a+b*g(x)|x}=a+b*min{g(x)|x}

 

 если b > 0), получая

 

 v(s)={ min{ φ(head τ)+ψ(head τ)×f(tail τ’)|s0 (τ’)=σ(q0 )}}

 

Теперь видно, что выражение для внутреннего минимума является в соответствии с определением функции v значением для v(σ(q0 )), так  что мы получаем

 

 v(s)={φ(s,q0)+ψ(s,q0)|v(σ(q0))}

 

Это и есть уравнение Беллмана для общей задачи динамического программирования.

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

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

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