ВУЗ:
Составители:
Рубрика:
43
более простой задаче, т.е. редуцирует ее. При этом результирующее
множество подзадач состоит только из одного элемента, т.е. имеем про-
стейший случай замены редуцируемой задачи на ей эквивалентную.
3.8.6. И/ИЛИ-графы. РЕШАЮЩИЙ ГРАФ
Для изображения процесса редукции задач и получающихся при
этом альтернативных множеств подзадач используются обычно графо-
подобные структуры, вершины которых представляют описания за-
дач
/
подзадач, а дуги связывают любую пару вершин, соответствую-
щих редуцируемой задаче и одной из результирующих подзадач, при-
чем стрелки на дугах указывают направление редукции. Пример такой
структуры приведен на рис. 12, а: задача G может быть решена путем
решения либо задач D
1
и D
2
, либо E
1
, E
2
и E
3
, либо задачи F. При этом
ребра, относящиеся к одному и тому же множеству подзадач, связы-
ваются специальной дугой. Чтобы сделать такую структуру более на-
глядной, вводятся дополнительные промежуточные вершины, и каж-
дое множество результирующих задач группируется под своей роди-
тельской вершиной. При этом структура на рис. 12, а преобразуется в
структуру, изображенную на рис. 12, б: для двух из трех альтернатив-
ных множеств подзадач добавлены соответственно вершины D и E.
Если считать, что вершины D и E соответствуют описаниям аль-
тернативных путей решения исходной задачи, то вершину G можно
назвать ИЛИ-вершиной, так как задача G разрешима или способом D,
или способом E, или способом F. Аналогично вершины D и E можно
назвать И-вершинами, поскольку каждый из соответствующих им
способов требует решения всех подчиненных задач, что и обозначает-
ся специальной дугой. По этой причине структуры, подобные структу-
рам, изображенным на рис. 12, б, называются И/ИЛИ-графами.
E
1
E
2
E
3
D
2
D
1
F
G
G
D
F
D
1
D
2
E
E
2
E
3
E
1
а) б)
Рис. 12
Страницы
- « первая
- ‹ предыдущая
- …
- 41
- 42
- 43
- 44
- 45
- …
- следующая ›
- последняя »
