4. Лабораторная работа № 3. «применение пролога для решения интеллектуальных задач»
4.1 Организация поиска в глубину
Рассмотрим общую модель работы интеллектуальной системы. Суть этой модели заключается в том, что решение интеллектуальных задач можно представить как некоторый вычислительный процесс, осуществляемый над некоторой структурой данных (глобальной БД) с помощью вычислительных операций (продукций). Правила продукции применяются к исходной БД S0 последовательно, видоизменяя ее. Итогом вычислений должно быть получение БД, которая удовлетворяет целевому условию. При этом каждое правило продукции может быть применено к текущей БД Si только в том случае, если эта БД удовлетворяет заранее известному условию применения правила.
Пролог – мощное средство решения интеллектуальных задач. Опишем общую процедуру поиска в глубину.
Введем предикаты:
decision(S,List,N)
S– глобальная БД, которую можно получить во время поиска.
List– список правил, которые надо применить для получения глобальной БД S.
N– специальный параметр типаinteger, который задает глубину поиска (N≥0).
Для описания преобразования глобальной БД с помощью правил введем предикат rule(S,List,S1,List1), в которомS,List– глобальная БД и список правил до применения правил, S1,List1 – после применения правила.
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)