Алгоритм нахождения наилучшего пути достижения поставленной цели

Приведем алгоритм нахождения наилучшего пути достижения поставленной цели, положенный в основу метода построения блока целеполагания ИС. Разработанный алгоритм является алгоритмом поиска «в глубину» с эвристической функцией (2.1). Он состоит из следующих шагов.

1. но
2. Если у вершины пет нераскрытых дочерних вершин, то переход в и. 8. Определить тип нераскрытых дочерних вершин, ?=?+1.
3. Если нераскрытые дочерние вершины входят в две или более групп типа «И», то переход к п. 5а. Если нераскрытые дочерние вершины типа «ИЛИ», то переход к п. 56.
4. Если нераскрытые дочерние вершины входят в одну группу типа «И», то переход к п. 6.
5а. Определить группу вершин типа «И» па раскрытие в соответствии с эвристической функцией 11(1)=>т1п и перейти к п. 6.
56. Определить вершину на раскрытие среди дочерних вершин типа «ИЛИ» в соответствии с эвристической функцией Ь(0=>тт и перейти к п. 7.
6. Определить вершину на раскрытие среди дочерних вершин типа «И», образующих группу вершин типа «И», в соответствии с эвристической функцией: Ь(1)=>тт.
7. Если вершина не является заключительной, то переход к п. 10.
8. Если вершина разрешима, то пометить ее как разрешимую и выполнить следующие условия:
- а) если вершина входит в группу «И» и есть нераскрытые вершины в группе «И», то определить вершину на раскрытие в соответствии с эвристической функцией Ь(0=>гшп и переход к п. 10;
- б) если вершина входит в группу «И» и все вершины в группе «И» раскрыты, то ?=?-1 (переход к ее родительской вершине);
- в) если вершина является дочерней вершиной типа «ИЛИ», то 1=1-1 (переход к ее родительской вершине);
- г) если ?=0, то СТОП — вершина 0-го уровня разрешима и наилучший путь достижения цели найден; в противном случае переход к п. 8.
9. Если вершина неразрешима, то пометить ее как неразрешимую и выполнить следующие действия:
- а) если вершина входит в группу «И», то пометить, что данная группа вершин неразрешима и ?=?-1, и если есть нераскрытые группы вершин типа «И», то переход к п. 10;
- б) если вершина является дочерней вершиной типа «ИЛИ», то 1=1—1, и если есть нераскрытые дочерние вершины, то переход к п. 10;
- в) если 1=0, то СТОП — вершина 0-го уровня неразрешима.
10. Переход к п. 2.

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

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