а дерево. Такое решающее дерево

Следовательно, это уже не путь, а дерево. Такое решающее дерево Т определяется следующим образом:

исходная задача Р - это корень дерева Т;

если Р является ИЛИ-вершиной, то в Т содержится только один из ее преемников (из И / ИЛИ-графа) вместе со своим собственным решающим деревом;

если Р - это И-вершина, то все ее преемники (из И / ИЛИ-графа) вместе со своими решающими деревьями содержатся в Т.

Рис. 13. 4. (а) Пример И / ИЛИ-графа: d, g и h - целевые вершины;

a - исходная задача. (b) и (с) Два решающих дерева, стоимости

которых равны 9 и 8 соответственно. Здесь стоимость решающего

дерева определена как сумма стоимостей всех входящих в него дуг.

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

Однако мы не обязательно должны измерять степень оптимальности решения, базируясь на стоимостях дуг. Иногда более естественным окажется приписывать стоимость не дугам, а вершинам, или же и тем, и другим одновременно.

Подведем итоги:

И / ИЛИ-представление основано на философии сведения задач к подзадачам.

Вершины И / ИЛИ-графа соответствуют задачам; связи между вершинами - отношениям между задачами.

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

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

При заданном И / ИЛИ-графе конкретная задача специфицируется заданием

        стартовой вершины и

        целевого условия для распознавания

Содержание  Назад  Вперед

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий