Лекция 8

 

 

 

Операции в Прологе. Поиск.

 

 

Cодержание

1 Операции (Операторы).

1.1 Приоритет оператора

1.2. Тип оператора

1.3.Объявление операций

2 Поиск.

2.1 Поиск в Прологе

2.2 Поиск в глубину

2.3 Поиск в ширину

2.4 Резюме Поиска

1. Операции (Операторы).

Как вы помните для некоторых структур, имеющих размерность /2, функтор может быть записан между компонентами. Например
+(1,2)

можно записать как

1 + 2 .

При этом структуру легче воспринимать в программе и водить.

Пролог предоставляет возможность использовать наряду с встроенными операторами и дополнительные операторы для структур с арностью /2 и /1.

Для этого достаточно объявить эту структуру оператором используя встроенный предикат op/3.

op(Приоритет,Тип,Имя).

Имя оператора любой атом.

1.1 Приоритет оператора.

Приоритет оператора задает порядок выполнения операций в выражениях, содержащих более одного оператора.

Приоритет задается приоритетным номером - числом обычно в диапазоне 1-1500 (в нашем случае до 1200).

Вычисления начинаются с оператора имеющего наименьший номер и заканчиваются наибольшим номером.

Например, в выражении x + y * 2 приоритет * больше + и вычисления производятся как x + (y * 2). Приоритетный номер скобки равен нулю.(Самый высокий приоритет)

Поэтому скобки могут использоваться для изменения ассоциативности.

1.2. Тип оператора.

Тип задает позицию и ассоциативность оператора.

Позиция оператора указывает, где он записывается по отношению к своим аргументам.

Для арности 2 оператор может быть только инфиксным и располагать между аргументами.

Например 2 > 1 или Р;Q

Для арности 1 оператор может быть

Ассоциативность оператора показывает, какая операция выполняется первой в выражении, содержащем два или более оператора с одинаковым приоритетом.

Тип может принимать одно из следующих значений

Здесь

Для простоты следует запомнить что yfx имеет левую ассоциативность.

Например + определен как
op( 500, yfx, +).
+ обладает левой ассоциативностью.
Т.е. A + B + C + D выполняется как +(+(+(A,B),C),D)
Представляется как дерево растущее в низ и налево:

 

Наоборот xfy имеет правую ассоциативность.

Например , (êîíúþíêöèÿ целей) определен как
op( 1100, xfy, ,).
, обладает правой ассоциативностью.
Т.е. A , B , C , D выполняется как ,(A, ,(B, ,(C,D)))
Представляется как дерево растущее в низ и направо:

 

xyx - инфиксная операция, не обладающая свойством ассоциативности

Примером может служить операция mod.

Поэтому

?- X is 120 mod 50 mod 5

является недопустимой.

Встроенные операторы для SWI-prolog представлены в таблице.

(Все операторы могут быть переопределены пользователями)

1.3 Объявление операций.

Если объявляется 2 или 1 арная процедура то для удобства использования

с т.з. читабильности программы ее можно объявить как операцию.

(Для SWI-prolog op включается в программу как цель, а не как факт).
Например

 

:-op(1500,xfx, love).

bob love mary.

pam love sam.

 

?- bob love Y.

Y = mary.

Еще один пример 

 
   ?- X=join(a,b),write(X),nl,op(500,yfx,join),
        write(X).
Дает    join(a, b)
        a join b
 
        X = a join b

2. Поиск.

Напомним что:

Пролог использует быстрый, но глупый(неэффективный) метод поиска. Написание программы своего поиска не так сложно.

Семейное Дерево.

% - parent ( A, B) истина, если A является родителем B

parent( p1, p2 ).

parent ( p3, p2 ).

parent ( p2, p4 ).

parent ( p4, p5 ).

2.1 Поиск в Прологе.

Основные стратегии поиска:

Поиск в глубину ( исследуется первый путь до конца перед переходом на следующий путь )

Поиск в ширину ( исследуются сначала все самые близкие пути)

Наиболее лучшего ( использует величину "оценки")

2.2 Поиск в глубину.

Отслеживайте узлы, которые еще не исследовались (т.н " " открытые " " узлы ). 

 
search(X, X, T).
 
search(X, Y, T) :- (edge(X, Z); edge(Z, X)),
not(member(Z, T)),
search(Z, Y, [Z|T]).
 
 
member(X, [X|_]) :- !.
member(X, [_|Y]) :- member(X, Y).
 
 
edge(a,b).
edge(a,c).
edge(a,d).
edge(b,e).
edge(e,f).
edge(e,g).
edge(d,h).
edge(d,i).
edge(i,j).
 

Другой вариант 

 
 depth_first(Start, Answer ) :-
                depth_star(/*Open*/ [Start], Answer ),!.
        
   depth_star( [X|_], X ).
   depth_star( [X|Open1], Y ) :-
       children(X, Children),
       append( Children, Open1, Open2 ),
       depth_star( Open2, Y ).
 
/*children(A,Bs) is true if A*/
/*is parent of each child in Bs*/
        children(a, [b,c,d]).
        children(b, [e]).
        children(e, [f,g]).
        children(d, [h,i]).
        children(i, [j]).
 
/* a f */

Обратите Внимание: открытый список хранится ,как стек.

Обратите Внимание на представление:

То есть мы можем представлять граф, как

%-- children(A,Bs) истина если A

%-- является родителем каждого ребенка в Bs

children(p1, [p2]).

children(p3, [p2]).

children(p2, [p4]).

children(p4, [p5]).

Мы можем также представить обратное отношение

parents(p2, [p1, p3]).

parents(p4, [p2]).

parents(p5, [p4]).

2.3 Поиск в ширину.

Подобен поиску в глубину , но хранит открытый список, как очередь. 

 
  breadth_first( Start,Answer ) :-
        breadth_star(/*Open*/ [Start],
                     Answer ).
 
  breadth_star( [X|_], X ).
  breadth_star( [X|Open1], Y ) :-
       children(X, Children),
       append( Open1, Children, Open2 ),
       breadth_star( Open2, Y ).
 
        children(a, [b,c,d]).
        children(b, [e]).
        children(e, [f,g]).
        children(d, [h,i]).
        children(i, [j]). 
 

2.4 Резюме Поиска.

Поиск в Прологе использует самую простую (самый дешевую) стратегию.

Другие алгоритмы поиска можно написать на Прологе.

Эффективность - частая проблема в поиске .

Чем меньше узлов Вы посетите,тем лучше.

(c) M.N.Morozov, 1999.

информация

проекты

публикации

материалы

друзья

студенты

 

связи

 

 

Hosted by uCoz