Поиск в И/ИЛИ-графах
Простейший способ организовать поиск в И/ИЛИ-графах средствами Пролога - это использовать переборный механизм, заложенной в самой пролог-системе. Оказывается, что это очень просто сделать, потому что процедурная семантика Пролога это и есть не что иное, как поиск в И/ИЛИ-графе. Например, И/ИЛИ-граф задачи на рис. 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.
За простоту такого метода программирования приходится расплачиваться: мы не получаем явно решающего дерева. Но этот недостаток исправим - надо определить собственную процедуру поиска в глубину для И/ИЛИ-дерева.
