ВУЗ:
Составители:
Рубрика:
73
Круглые дуги на графе указывают на отношение И между
соответствующими подзадачами. Задачи более низкого уровня называются
задачами-преемниками.
И/ИЛИ- граф- это направленный граф, вершины которого соответствуют
задачам, а дуги – отношениям между задачами.
Между дугами также существуют свои отношения – это отношения И и
ИЛИ, в
зависимости от того, должны ли мы решить только одну из задач-
преемников или же несколько из них. В принципе из верщины могут
выходить дуги, находящиеся в отношении И вместе с дугами, находящимися
в отношении ИЛИ. Тем не менее, будем предполагать, что каждая верщина
имеет либо только И-преемников, либо только
ИЛИ-преемников, так как в
такую форму можно преобразовать любой И/ИЛИ- граф, вводя в него при
необходимости вспомогательные ИЛИ-вершины. Вершину, из которой
выходят только И- дуги называются И- вершиной; вершину, из которой
выходят только ИЛИ- дуги,- ИЛИ- вершиной.
Решением задачи, представленной в виде И/ИЛИ- графа является
решающее дерево
, так как решение должно включать в себя все подзадачи И-
вершин.
Решающее дерево T определяется следующим образом:
исходная задача P – это корень дерева T;
если P является ИЛИ-вершиной, то в T содержится только один из ее
преемников (из И/ИЛИ-графа) вместе сос своим собственным решающим
деревом;
если P – это И-вершина, то все ее
преемники (из И/ИЛИ-графа) вместе
со своими решающими деревьями содержатся в T.
f-h-z
a-z| d
З
3 4
4
8 3
П2 П1
a-z
a-z
|
f
d
-z
a-f f-z| h
a-f | c
a-f | b
a-
b
-f a-c-f
a-d| c
a-c-
d
Страницы
- « первая
- ‹ предыдущая
- …
- 71
- 72
- 73
- 74
- 75
- …
- следующая ›
- последняя »
