Методы исследования операций при принятии решений. Бодров В.И - 9 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Деревья в пространстве состояния могут быть заданы в эксплицидной и имплицидной форме.
Дерево, заданное в эксплицидной форме, представляет собой граф с полным обозначением всех
вершин (состояний) и всех ребер перехода от одного состояния к другому. Если такой граф задан, лю-
бое решение очевидно – его можно показать на графе. Но к сожалению такой граф можно построить
лишь для очень простых задач, т.е. задач с очень малым числом состояний.
Если представить, что состояние – это список букв и знаков русского алфавита, то корневой верши-
ной будет вершина, состояние которой "а". Эта вершина в качестве дочерних имеет вершины, в которых
состояниями будут две буквы аа, аб, ав, ..., ая, а также буква а и знаки – а
∨
, а,, а!, а? и т.п.
Каждая из этих вершин имеет столько же дочерних. Этот гигантский бесконечный граф в качестве
вершин где-то имеет набор – "Анна Каренина", "Преступление и наказание", другая вершина – это поч-
ти "Анна Каренина", отличающаяся, может быть, строкой, или буквой, или ошибкой. Все в этом графе
гениально, в нем еще не написанные рассказы, все мудрые мысли прошлых и будущих мыслителей,
теоремы и их доказательства, изобретения будущих тысячелетий.
Однако, такой граф нельзя построить в явном виде. Обычно дерево состояния строят в имплицид-
ной форме.
Дерево в имплицидной форме считается заданным, если а) определено понятие состояния (форма-
лизованы обозначение каждого состояния); б) задано начальное состояние; в) задан оператор, перево-
дящий одно состояние в дочернее.
Этот оператор обозначается
()
nn
aaF →
−1
, а R(a
n
) – оператор раскрытия вершин, под которым пони-
мают построение всех дочерних вершин для вершины a
n
.
Имея оператор R(a
n
), можно, последовательно применяя его к вершинам, из имплицидного дерева
получить эксплицидное на любую глубину. Применяя последовательно оператор R(a
n
) к оператору
()
nn
aaF →
−1
, формируют одну за другой дочерние вершины для материнской вершины a
n
. При этом опе-
ратор
()
nn
aaF →
−1
формирует новое состояние a
n+1
следующим образом:
а) либо применяя правила переписывания строк, определяющие состояние, например, последова-
тельную запись расположения фигур на шахматной доске K
p
q1, Фf3, ЛФ1 и т.д. Эти правила иногда на-
зываются продукциями;
б) в виде таблицы, в которой заданы вершины, дочерние вершины, стоимость всех связывающих их
ребер;
в) с применением оператора (вычислительной процедуры), который определяет (вычисляет) все па-
раметры дочерних вершин, описывающие их состояние, рассчитывает стоимости соединяющих их ре-
бер. В этом случае говорят, что граф задан алгоритмически (неявно), причем вычисления могут быть
очень сложными.
При формулировке задачи принятия решения необходимо формализовать конечное (целевое) со-
стояние. Например, при игре в шахматы конечным желаемым состоянием является состояние мата ко-
ролю соперника.
В этом случае простейшая задача оптимизации (принятия решения) на графе состояний заключает-
ся в нахождении пути (последовательности состояний) из начального состояния в целевое, при котором
целевая функция принимает минимальное (максимальное) значение.
В качестве целевой функции может выступать число пройденных вершин (это часто тождественно вре-
мени решения) или затраты (прибыль), которые на каждом этапе характеризуются стоимостью ребер,
соединяющих вершины на выбранном пути.
Если конечных состояний много, то необходимо найти такое конечное состояние и такой путь из
начального состояния в конечное, при котором целевая функция будет минимальна.
Если и начальных состояний много, то необходимо найти такое начальное и такое конечное состоя-
ние и такой соединяющий их путь, при котором целевая функция примет минимальное значение.
Методы поиска оптимальных решений
в пространстве состояний
Пусть оператор R(a) задан, этот оператор строит все вершины a
ι
, дочерние вершине а, и устанавли-
вает у каждой из них указатель (стрелку) на ту вершину, которая является материнской. Это позволяет

Страницы