Дерево решения

Обобщим понятие дуги пространства состояний.

Опр. 3. Дугу от вершины типа «ИЛИ» к ее преемнику будем называть унарной связкой (1-связка), k дуг от вершины типа «И» к ее преемникам будем называть k-связкой.

Рассмотрим процесс построения решающего дерева. Выйдем из исходной вершины. Для продолжения движения будем выбирать ровно одну связку. Процесс заканчивается, когда ВСЕ вершины-преемники окажутся терминальными вершинами.

Пространство состояний — частный случай И-ИЛИ графа, т.к. в нем все вершины типа «ИЛИ», и все связки унарные. Для решения «ИЛИ» вершины нужно перейти ровно в одного преемника, поэтому мы получаем путь. Для решения «И» вершины мы должны решить все подзадачи, т.е. перейти в k ее вершин-преемников, поэтому мы получаем дерево. Построение решающего дерева по И-ИЛИ графу — это дело стратегии, т.е. системы управления (глубина, ширина, эвристический поиск). Построим И-ИЛИ граф и выделим в нем дерево решения для нашего примера (рис. 15):

Рисунок 15. «И-ИЛИ» граф для разложимой системы продукций

Штриховой линией обведена та часть И-ИЛИ графа, которая является деревом решения.

Контрольные вопросы.

1. Что такое системы продукций? Каковы их отличия от иерархической вычислительной системы?

2. Что такое разложимые системы продукций? Что является представлением задачи, описываемой разложимой системой продукций?

3. В чем состоит основное отличие И-ИЛИ графа от пространства состояний?

4. Как построить дерево решения на И-ИЛИ графе?

Стратегии управления поиском на И-ИЛИ графах