Определение разрешимых вершин

• 1. Заключительные вершины, соответствующие элементарным целям, разрешимы тогда и только тогда, когда указанные ограничения и условия выполнены.
• 2. Вершина, не являющаяся заключительной и имеющая дочерние вершины типа «ИЛИ», разрешима тогда и только тогда, когда выполняется условие, ей соответствующее, и разрешима, по крайней мере, одна из дочерних вершин.
• 3. Вершина, не являющая заключительной и имеющая дочерние вершины типа «И», разрешима тогда и только тогда, когда условие выполнено и разрешимы все ее дочерние вершины.

Определение неразрешимых вершин

• 1. Заключительные вершины неразрешимы тогда и только тогда, когда указанные ограничения и/или условия не выполнены.
• 2. Вершина, не являющаяся заключительной и имеющая дочерние вершины типа «ИЛИ», неразрешима тогда и только тогда, когда соответствующее ей условие не выполнено, и/или неразрешимы все ее дочерние вершины.
• 3. Вершина, не являющая заключительной и имеющая дочерние вершины типа «И», неразрешима тогда и только тогда, когда условие не выполнено, и/или неразрешима, по крайней мере, одна из ее дочерних вершин.

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

Введем пересчитанный коэффициент значимости у; вершины (цели) ?, который является аргументом эвристической функции:

где условие 1 — для вершин типа «ИЛИ», а также для вершин типа «И», если между вершинами типа «И» не определены отношения; условие 2 — для вершин типа «И», между которыми определено хотя бы одно отношение;

У;е ]0,10]; И.Пк, Я21к, В31к, Я41к е ]0, 10], ?=1,...,М, где М — число вершин в И/ИЛИ-графе.

Если отношения Я1 и Я2 или ЯЗ и Я4 не определены в условии 2, то^ЯПк = 0 и ^Я21к = 1 или ^Я31к = 0 и ^ Я41к = 1. Если опре-

к к к к

делено хотя бы одно отношение II1 и отношения Я2 не определены, то ^Я21к = 1. Если определено хотя бы одно отношение 112 и отно- к

шения Я1 не определены, то ]ГЯПк = 1. Аналогично для отношений

к

ЯЗ и Я4.

Примечание. Если пересчитанные коэффициенты значимости дочерних вершин совпадают, то на раскрытие выбирается самая левая вершина.

Отметим, что если цель 1 способствует достижению других целей в группе «И», то и такие цели раскрываются в первую очередь.

В противном случае, если цель препятствует достижению целей, то

ViCVi.

Зададим эвристическую функцию ЙО), которая минимизируется при нахождении иаилучшего пути достижения корневой цели: Ь(0=>ппп.

где условие 1 — для заключительных вершин; условие 2 — для вершин, имеющих дочерние вершины типа «ИЛИ»; условие 3 —

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

Примечания:

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

Отличием И/ИЛИ-графа от И/ИЛИ-дерева является то, что вершина может иметь более одной родительской вершины. В алгоритме поиска это учитывается следующим образом: необходимо проверять, была ли разрешима или неразрешима вершина по другому альтернативному пути; если да — делаем переразметку вершин. Если вершина 0-го уровня разрешима, то СТОП с успехом, если нет — продолжение поиска.