Искусственный интеллект и экспертные системы

       

Поиск в И/ИЛИ-графах


Простейший способ организовать поиск в И/ИЛИ-графах средствами Пролога - это использовать переборный механизм, заложенной в самой пролог-системе. Оказывается, что это очень просто сделать, потому что процедурная семантика Пролога это и есть не что иное, как поиск в И/ИЛИ-графе. Например, И/ИЛИ-граф задачи на рис. 2.7 можно описать при помощи следующих предложений (предикат a-z соответствует задаче "найти путь из a в z", предикат a-z/f соответствует задаче "найти путь из a в z через f" и т.д.):

a-z:-a-z/f.        % задача a-z - ИЛИ-вершина с двумя преемниками

a-z:-a-z/g.       % a-z через f и a-z через g

a-z/f:- a-f,f-z.  % задача a-z/f - И-вершина с двумя преемниками a-f и f-z

a-z/g:-a-g,g-z.

a-f:-a-f/b.

a-f:-a-f/c.

a-f/b:-a-b,b-f.

a-f/c:-a-c,c-f.

b-f:-b-d,d-f.

c-f:-c-e,e-f.

f-z:-f-z/h.

f-z:-f-z/i.

f-z/h:-f-h,h-z.

f-z/i:-f-i,i-z.

/* пропущены правила

   для a-g и g-z

*/

a-b. b-d. d-f. a-c. c-e. e-f. f-h. h-z. f-i. i-z. % "тривиальные" задачи

 

Для того чтобы узнать, имеет ли эта задача решение, нужно просто спросить:

?- a-z.

Получив этот вопрос, пролог-система произведет поиск в глубину в И/ИЛИ-дереве и, после того как найдет решающее дерево, ответит Yes.

За простоту такого метода программирования приходится расплачиваться: мы не получаем явно решающего дерева. Но этот недостаток исправим - надо определить собственную процедуру поиска в глубину для И/ИЛИ-дерева.



Содержание раздела