Лекция 5

В процессе вычисления цели пролог проводит перебор вариантов, в соответствии с установленным порядком. Цели выполняются последовательно, одна за другой, а в случае неудачи происходит откат
к предыдущей цели (backtracing).

Однако для повышения эффективности выполнения программы, часто требуется вмешаться в перебор, ограничить его, исключить некоторые цели.

Для этой цели в пролог введена специальная конструкция cut - "отсечение", обозначаемая как "!"
( Читается "cut", "кат").

Cut подсказывает прологу "закрепить" все решения предшествующие появлению его в предложении. Это означает, что если требуется бэктрекинг, то он приведет к неудаче (fail) без попытки поиска альтернатив.

5.1.1 Графическая иллюстрация действия cut.

Графически действие cut можно показать с помощью box-представления логического вывода.

В обычном случае бэктрекинг для правила

G:-A,B,C.

выглядит следующим образом:

Т.е. поиск альтернатив производится для всех целей: G,A,B,C. Заменим B на cut :

Графическая иллюстрация действия cut.

Действие cut заключается в отмене поиска альтернатив для целей A,G, стоящих после "!".

5.1.2 Пример действия cut.

Пусть база данных выглядит следующим

data(one).
data(two).
data(three).

Процедура для проверки:

cut_test_a(X):- data(X).
cut_test_a('last clouse').

Цель:

		?- cut_test_a(X),nl,write(X). one; two; three; last_clouse; no

Теперь поставим cut в правило:

cut_test_b(X):- data(X),!.
cut_test_b('last clouse').

Цель:

		?-cut_test_b(X),nl,write(X). one; no

Происходит остановка бэктрекинга для левого data и родительского

cut_test_b(X).

Теперь поместим cut между двумя целями.

cut_test_с(X,Y):- data(X),
/ !,data(Y).
cut_test_с('last clouse').

Теперь бэктрекинг не будет для для левого data и родительского cut_test_b(X),но будет для правого data,стоящего после !.

		?-cut_test_с(X,Y),nl,write(X-Y). one-one; one-two; one-tree; no

5.1.3 Применение cut при выборе альтернатив.

Рассмотрим функцию Y(X):

         ⌠  0 ,   X < 3

⌠

  Y= <   2 ,  3 = < X < 6

⌠

         ⌠  4 ,  X >= 6

На прологе это запишется через бинарное отношение f(X, Y).

Процедура выглядит:

f(X, 0):- X < 3.
f(X, 2):- 3 =< X, X < 6.
f(X, 4):- 6 =< X.

Зададим вопрос:

		?-f(1,Y),Y>2.

Таким образом последовательно проверяются все три предложения, хотя сразу ясно, что выполняется только одно.
Как убрать неэффективность?
Надо использовать отсечение-cut.
Перепишем

f( X, 0):-X<3, !.
f(X, 2):- 3=<X, X<6, !.
f(X, 4):-6 =<X, !.

! указывает, что возврат из этой точки проводить не надо.

Что произойдет теперь?
Для цели

		?-f(1, Y), Y>2. no

После выполнения цели X<3 цель Y>2, не достигается, но откат не может произойти, так как стоит cut.

Таким образом сокращается перебор.

Аналогично для цели

		?-f(5, Y), Y=0.

Здесь введение cut повышает эффективность программы, сокращая время перебора и объем памяти, не влияет на декларативное чтение программы.

После изъятия ! декларативный смысл не изменится.

Такое применение cut называют "зеленым отсечением".

"Зеленые отсечения" лишь отбрасывают те пути вычисления, которые не приводят к новым решениям.

Бывают и "красные отсечения", при изъятии которых меняется декларативный смысл программы.

5.1.4 Формальное описание действия отсечения.

Рассмотрим предложение

Н:-B1, B2,..., Bm, !,..., Bn.

Это предложение активизируется, когда некоторая цель G, будет сопоставляться с H.

Тогда G называют целью-родителем.

Если B1, B2,..., Bm выполнены, а после !, например в Bi, i>m, произошла неудача и требуется выбрать альтернативные варианты, то для B1, B2,..., Bm такие альтернативы больше не рассматриваются и все выполнение окончится неудачей. Кроме этого G будет связана с головой H, и другие предложения процедуры во внимание не принимаются.

Т.е. отсечение в теле предложения отбрасывает все предложения , расположенные после этого предложения.

Формально действие отсечения описывается так:

Пусть цель -родитель сопоставляется с головой предложения, в теле которого содержится отсечение.

Когда при просмотре целей тела предложения встречается в качестве цели отсечение, то такая цель считается успешной и все альтернативы принятым решениям до отсечения отбрасываются и любая попытка найти новые альтернативы на промежутке между целью-родителем и сut оканчиваются неудачей.
Процесс поиска возвращается к последнему выбору, сделанному перед сопоставлением цели родителя.

5.2 Применение отсечения.

5.2.1 minimum(X, Y, M).

Найти минимальный элемент из двух.

minimum(X, Y, X):- X<=Y, !.
minimum(X, Y, Y):- Y

		?-minimum(2, 5, Y).

5.2.2 Добавление элемента без дублирования.

Чтобы добавить элемент в голову списка достаточно использовать

add(X, L, [X|L]).

Но если возникает необходимость добавлять только, если элемент отсутствует, то можно добавить правило:

add(X, L, L):-member(X, L), !. add(X, L, [X|L]).

Вопрос

		?-add(a, [b, c], L). L=[a, b, c] ?-add(b, [b, c], L). L=[b, c]

Если сечение убрать, то

		?-add(b, [b, c], L) L=[b, c]; L=[b, b, c]

Таким образом, при изъятии отсечения, изменился декларативный смысл программы- отсечение "красное".

5.2.3 Классификация.

Используя отсечение, легко произвести классификацию объектов.

Например, надо классифицировать числа

class(X, plus):-X>0, !.
class(X, minus):-X<0, !.
class(X, zero):-X=0, !.

		?-class(4, Y). Y=plus

5.2.4 Отсечение в численной рекурсии.

Применение отсечения в рекурсии позволяет значительно сократить использование памяти.

Определим факториал

factorial(0, 1):-!.
factorial(N, RES) :-
N1 is N-1, factorial(N1, N1fak), Res is N*N1fak.

5.2.5 Замечания при использовании отсечения.

Применение сечения за счет сокращения перебора позволяет повысить эффективность программы. Кроме этого отсечение упрощает программирование выбора вариантов.

Вместе с тем, часто, при использовании красных отсечений может изменится декларативный смысл программы.

Поэтому отсечение требует осторожности в использовании.

Следует избегать двух ошибок:

отсечения путей вычисления, которые нельзя отбрасывать
и не отсечения тех решений, которые должны были быть отброшены.

5.3 Сортировка списков.

До сих пор средства пролога использовались при записи простых процедур и примеров. Рассмотрим более сложные примеры написания программ на прологе для различных методов сортировки.

5.3.1 Метод наивной сортировки.

В этом методе элементы в списке переставляются ( перемешиваются permutation/2 ),и проверяется отсортирован этот список или нет: sorted/1.
Это записывается:

sortn(L1, L2) :- permutation(L1, L2), sorted(L2), !.

Перестановки определим через append

permutation(L, [H|T]) :- append(V, [H|U], L),
append(V, U, W),
permutation(W, T).
permutation([], []).

Проверка того, что элементы списка расположены в возрастающем порядке выражается через два предложения. Факт означает, что список из одного элемента всегда упорядочен. Правило утверждает, что список упорядочен ,если первые два элемента расположены по порядку и остаток ,начинающийся со второго элемента тоже упорядочен:

sorted([L]).
sorted([X,Y|T]) :- order(X,Y), sorted([Y|T]).
order(X, Y) :- X =< Y.

5.3.2 Метод пузырька.

Это простой и эффективный метод.

Декларативное описание:

Найти в списке L два смежных элемента X и Y, таких, что X > Y, поменять их местами и получить новый список, M, затем отсортировать M. Для поиска таких элементов и перестановки используется процедура swap/2.
Если в списке нет не одной пары смежных элемента X и Y, таких, что X > Y, считать что список отсортирован.

busort(L, S) :- swap(L, M), !, busort(M, S).
busort(L, L) :- !.
swap([X, Y|R], [Y, X|R]) :- order(Y, X).
swap([X|R], [X|R1]) :- swap(R, R1).

5.3.3 Mетод вставки.

Декларативное описание:

Для того чтобы упорядочить непустой список L=[X|T] необходимо:

Упорядочить хвост Т списка L
Вставить голову X списка L в упорядоченный хвост, поместив ее таким образом, чтобы получившийся список остался упорядоченным.

    insort([], []).



    insort([X|L], M) :- insort(L, N), insortx(X, N, M).



    insortx(X, [A|L], [A|M]) :- order(A, X), !, insortx(X, L, M).



    insortx(X, L, [X|L]).



    order(X, Y) :- X =< Y.

5.3.4 Быстрая сортировка quick.

Описание метода:

Убираем первый элемент:

         5 3 7 8 1 4 7 6

получаем: X =5.
и оставшийся список:

         3 7 8 1 4 7 6

Разбиваем новый список на два, помещая в первый элементы меньше X, а во второй - больше X:

  ( X: 3 1 4  )  X:  7 8 7 6

Сортируем оба списка:

   1 3 4        6 7 7 8

Соединим первый список, X, второй список.

      1 3 4 5 6 7 7 8

Декларативное описание:

Удалить из списка голову Х и разбить оставшийся список на два списка Small и Big следующим образом: все элементы большие чем Х помещаются в Big и меньшие X - в Small.
Отсортировать список Small в Small1.
Отсортировать список Big в Big1.
Соединить списки Small1 Х и Big1.

qsort([], []).

qsort([H|Tail], S) :- split(H, Tail, Small, Big),

                           qsort(Small, Small1),

                           qsort(Big, Big1),

                           append(Small1, [H|Big1], S).

order(X, Y) :- X =< Y.

split(H, [A|Tail], [A|Small], Big) :- order(A, H), !,

                                               split(H, Tail, Small, Big).

split(H, [A|Tail], Small, [A|Big]) :- split(H, Tail, Small, Big).

split(_, [], [], []).

(c) M.N.Morozov, 1999.

информация	проекты	публикации
материалы	друзья	студенты
	связи