Пример: решение логической задачи о волке, козе и капусте

Рассмотрим известную логическую задачу о волке, козе и капусте. Фермер должен переправить на другой берег реки волка, козу и капусту. Грузоподъемность лодки такова, что за один раз можно взять на борт что-нибудь одно: или волка, или козу, или капусту. В присутствии старика никто никого не ест. Если же он отлучится, то волк съест козу, а коза — капусту.

Для решения этой задачи организуем два списка. Один список будет отражать содержимое левого берега, второй — правого. Первоначально все находятся на левом берегу. Список левого берега: [wolf, goat, cabbage], список правого берега пустой: [].

Определим предикаты, описывающие задачу.

stuff (wolf). Хперечисление груза stuff (goat), stuff (cabbage).

/ * условия возникновения конфликта * / conflict (X): - member (wolf, X), member (goat, X). conflict (X): - member (goat, X), member (cabbage, X).

/ * Предикаты, описывающие перемещения лодки:

С левого берега на правый* /

go right ([], _).% условие завершения (список левого берега пуст) go right (L, R): -

stuff (X), % выбираем груз, member (X, L), % который есть на левом берегу

excl (X, L, LL), % исключаем из списка левого берега not (conflict (LL) ), % на левом берегу конфликта

нет

incl (X, R, RR), % включаем в список правого берега write (LL, X, " R), % выводим сообщение

go_left (LL, RR) .% гребем назад / * Движение влево возможно в двух вариантах. Если на правом берегу конфликт не возникает, то фермер едет один * / go_left (L, R): -not (conflict (R) ),

write (L, "< .......", R), % выводим сообщение

go_right (L, R). % вызываем предикат движение вправо / * Если на правом берегу возникает конфликт надо кого- нибудь увезти обратно. Это единственная подсказка, которую мы сообщаем программе. В остальном Пролог будет искать решение вполне самостоятельно * / go_left (L, R): -

stuff (X), % выбираем груз,

member (X, R), % который есть на правом берегу

excl (X, R, RR), % исключаем из списка правого берега not (conflict (RR) ), % на правом берегу конфликта

нет

incl (X, L, LL), % включаем в список левого берега write (L, X, ” --"RR), % выводим сообщение

go_right (LL, RR). % гребем назад Вызов цели должен быть следующим: go_right ([wolf, goat, cabbage], []).

Если запустить эту программу, то быстро обнаружится, что первым рейсом старик отвезет на правый берег козу. Вторым рейсом — волка. Оставить волка с козой на правом берегу нельзя, поэтому он отвезет первый попавшийся груз, а им окажется волк, обратно. И так будет возить его бесконечно.

Недостаток данной программы заключается в том, что фермер не помнит, кого он только что привез. Для укрепления его памяти добавим в предикаты go_left и go_right название последнего перевезенного груза. Финальный вариант программы выглядит следующим образом (изменения выделены полужирным шрифтом):

/ * Задача о волке, козе и капусте * / domains % раздел требуется для PDC-Пролога. В SWI-Прологе не нужен

stuff = wolf; goat; cabbage; nil % создаем свой тип

данных (nil - пустое) list = stuff* % тип данных список predicates % раздел требуется для PDC-Пролога.

В SWI-Прологе не нужен member (stuff, list) incl (stuff, list, list) excl (stuff, list, list) conflict (list)

go_right (list, list, stuff) go_left (list, list, stuff) clauses

stuff (wolf).

stuff (goat).

stuff (cabbage).

member (H, [H | _]).

member (X, [H | T]): - member (X, T).

incl (H, T, [H | T]).

excl (H, [H | T], T).

excl (X, [H, T], [H | TT]): - excl (X, T, TT). conflict (X): - member (wolf, X), member (goat, X). conflict (X); - member (goat, X), member (cabbage, X). go_right (L, R, Last): -

stuff (X), % выбираем 2py3j

X <> Last, % но не mom, что везли только что и member (X, L), % который есть на левом берегу

excl (X, L, LL), % исключаем из списка левого берега

not (conflict (LL) ), % на левом берегу конфликта

нет

incl (X, R, RR), % включаем в список правого берега

write (LL, X, " R), % выводим

сообщение

go_left (LL, RR, X) .% гребем назад

/ * Если на правом берегу конфликт не возникает, то едет один * /

go_left (L, R, Last): - not (conflict (R) ),

write (L, "<-------”, R), % выводил! сообщение

go_right (L, R, nil). % вызываем предикат движение

вправо

% niL - значит, не везли ничего / * Если на правом берегу возникает конфликт надо кого- нибудь увезти обратно, но не того, кого везли только что * /

go_left (L, R, Last): -

stuff (X), % выбираем груз,

X о Last, % не тот} что везли только что и member (X, R), % который есть на правом берегу

excl (X, R, RR), % исключаем из списка правого берега not (conflict (RR) ), % на правом берегу конфликта

нет

incl (X, L, LL), % включаем в список левого берега write (L, X, ” RR), % выводим

сообщение

go_right (LL, RR, X). % гребем назад и помним, что

везли X

goal

go_right ( ([wolf, goat, cabbage], [], nil). / * Конец программы * /

Контрольные вопросы

  • 1. Напишите правило для отношения двоюродный брат или сестра. Используйте правила, приведенные в подразд. 1.4.
  • 2. Имеется программа, состоящая из двух экземпляров правила а:

а : - Ь, с, !, d, fail.

а : - е.

Какие предикаты будут вызваны при выполнении правила а, если каждый из предикатов b, с, d, е заканчивается успехом, а предикат fail — стандартный предикат для искусственного вызова неудачи? Что изменится, если убрать предикат отсечения?

3. Имеется предикат

dosomething ([]).

dosomething ([Н | Т]): - member (Н, Т), dosomething (Т).

dosomething ([Н | Т]): - write (Н), dosomething (Т).

Какой результат даст вызов dosomething ([1, 0, 0,1, 2, 0,10])?

4. Какое отсечение, красное или зеленое, стоит в следующем правиле? Обоснуйте.

sister (X, Y): - sibling (X, Y), !, female (X).

5. Правомерно ли использование отсечения в следующем правиле? Почему?

grandfather (X, Y): - father (X, Z), !, parent (Z, Y).

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >