Организация поиска в глубину

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

Пролог – мощное средство решения интеллектуальных задач. Опишем общую процедуру поиска в глубину.

Введем предикаты:

1. decision(S,List,N)

S – глобальная БД, которую можно получить во время поиска.

List – список правил, которые надо применить для получения глобальной БД S.

N – специальный параметр типа integer, который задает глубину поиска (N≥0).

2. Для описания преобразования глобальной БД с помощью правил введем предикат rule(S,List,S1,List1), в котором S, List – глобальная БД и список правил до применения правил, S1,List1 – после применения правила.

3. goal(S) – для определения того, является ли текущая БД целевой.

Запишем процедуру поиска в глубину:

clauses

decision(S,List,N):- goal(S), вывод необходимой информации,!.

decision(S,List,N):-

(N≥0),

rule(S,List,S1,List1),

N1=N-1,

decision(S1,List1,N1).

rule(S,List,S1,List1):-

add_el(“Правило1”,List,List1),

rule1(S,S1).

rule(S,List,S1,List1):-

add_el(“Правило1”,List,List1),

rule2(S,S2).

…

…

…

Цель: decision(S0,[],N)

S0 – исходная БД

N – глубина поиска

Приведем пример использования данной процедуры. Сформулируем задачу нахождения гамильтонова пути (включающего все вершины) с помощью систем продукций, то есть определим структуру глобальной БД, ее начальное и целевое состояния, правила ее преобразования. Тестирование программы проведем для графа, изображенного на рисунке 4.1.

Будем искать гамильтонов путь из вершины a. Такой путь существует, и его можно представить в виде списка вершин [a,b,c,d,e] или [e,d,c,b,a], то есть для описания глобальной БД можно использовать списковую структуру. В начальный момент в этом списке только одна вершина [a]. Преобразование данной глобальной БД заключается в том, что можно добавлять к текущей БД S некоторую вершину X, если она не принадлежит списку S, и если последняя вершина из данного списка Y соединена с вершиной X.

Пространство поиска нахождения гамильтонова пути данного графа:

/*Процедура нахождения гамильтоновых путей*/

domains

lst=symbol*

decision(lst,integer)

rule(lst,lst)

lined(symbol, symbol) /*предикат, описывающий соединение вершин в графе

image(symbol,lst)

belong(symbol,lst)

clauses

decision(S,0):-write(S),!.

decision(S,N):-

rule(S,S1),

N1=N-1,

decision(S1,N1).

rule(S,S1):-

S=[X|Tail],

lined(X,Y),

not(belong(Y,S)),

S1=[Y|S].

lined(X,Y):-

image(X,List), /*предикат, указывающий, в данном случае, на образ вершины a

belong(Y,List).

image(a,[b,e]).

image(b,[a,c,d,e]).

image(c,[b,d]).

image(d,[c,b,e]).

image(e,[a,b,d]).

belong(X,[X|Tail]).

belong(X,[Y|Tail]):-

belong(X,Tail).

goal

decision([a],4)