Приключения в опасной пещере

Допустим вы путешественник, который слышал о том, что в подземелье

зарыт клад с золотом. До вас многие пытались найти этот клад, но безус-

пешно. Подземелье состоит из лабиринта коридоров, которые связывают между

собой отдельные пещеры полные разных опасностей в виде чудовищ и грабите-

лей. Единственным плюсом является то, что все золото спрятано в одной пе-

щере. Какой маршрут позволит вам добыть золото и вернуться целым и невре-

димым?

Вход притон (hell) ------ русалка (mermaid)

| \ | / /

| \ | / /

| \ | / /

| \------ фонтан -------------- разбойники (robbers)

| \ | /

| \ | /

| \ | /

| \ пища (food) | /

| | | /

| | -------|---/

monsters (чудовища) | / |

\ | / \

\ | / \

\ ----- золото -------------\ выход

Рис. 18.2.

Вы можете с помощью Турбо Пролога ввести эту карту в программу и по-

пытаться с ее помощью проложить безопасный маршрут. Каждый коридор предс-

тавлен в виде отдельного факта. Правила заданы с помощью предикатов go и

route. Давайте введем в программу целевое утверждение.

go(entry,exit).

Ответ будет содержать список пещер, которые нужно пройти, чтобы до-

быть сокровище и вернуться невредимым.

Важной особенностью этой программы является то, что пройденные пеще-

ры заносятся в список. Это достигается с помощью предиката route, который

определен рекурсивно. Если достигнут выход, то третий параметр предиката

содержит список всех пройденных пещер. Если в этот список входит пещера с

золотом gold _treasure, то наша цель достигнута. В противном случае спи-

сок пройденных дополняется Nextroom, при условии,что перед этим вы не по-

бывали ни в одной из опасных пещер.

/* Program CH18EX03.PRO */

domains

room = symbol

roomlist = room*

predicates

gallery(room, room) /* Это проход между двумя комнатами */

neighborroom(room, room)

/* Necessary because it does not matter */

/* which direction you go along a gallery */

avoid(roomlist)

go(room, room)

route(room, room, roomlist)

/* This is the route to be followed. */

/* roomlist consists of a list of rooms already visited. */

member(room, roomlist)

clauses

gallery(entry, monsters). gallery(entry,fountain).

gallery(fountain, hell). gallery(fountain, food).

gallery(exit, gold_treasure). gallery(fountain, mermaid).

gallery(robbers, gold_treasure). gallery(fountain, robbers).

gallery(food, gold_treasure). gallery(mermaid, exit).

gallery(monsters, gold_treasure). gallery(gold_treasure,exit).

neighborroom(X, Y) :- gallery(X, Y).

neighborroom(X, Y) :- gallery(Y, X).

avoid([monsters, robbers]).

go(Here, There) :- route(Here, There, [Here]).

go(_, _).

route(Room, Room, VisitedRooms) :-

member(gold_treasure, VisitedRooms), write(VisitedRooms), nl.

route(Room, Way_out, VisitedRooms) :-

neighborroom(Room, Nextroom),

avoid(DangerousRooms),

not(member(NextRoom, DangerousRooms)),

not(member(NextRoom, VisitedRooms)),

route(NextRoom, Way_out, [NextRoom|VisitedRooms]).

member(X, [X|_]).

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

После того, как программа нашла решение, в ответ на целевое утверж-

дение

go(entry,exit).

возможно вы захотите добавить еще несколько коридоров, например

gallery(mermaid,gold_treasure)

или же можете добавить опасности, которые необходимо избежать.

Даже если имеется несколько решений данной задачи, наша программа

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

решения мы должны использовать поиск с возвратом после того, как будет

найдено первое решение. Это может быть достигнуто за счет добавления пре-

диката fail в первое правило для route:

route(Room, Room, VisitedRooms) :-

member(gold_treasure,VisitedRooms),

write(Visited Rooms), nl, fail.

Для аккуратного оформления результатов вы должны использовать преди-

кат write_a_list, обеспечивающий вывод списка пещер без квадратных скобок

и запятых. Однако в списке пройденных пещер VisitedRooms они содержатся в

обратном порядка, т.е. exit (выход) стоит первым, а entry ("вход") - пос-

ледним. Поэтому необходимо доработать write_a_list таким образом, чтобы

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