Пролог Путь Поиск

Question

Если у меня есть следующий предикат door , который объявляет, что между двумя комнатами есть дверь:

door(office, hall).
door(kitchen, office).
door(hall, "dining room").
door(kitchen, cellar).
door("dining room", kitchen).

И предикат doortate , который объявляет состояние двери:

doorstate(hall, office, closed).
doorstate(hall, "dining room", opened).
doorstate("dining room", kitchen, opened).
doorstate(kitchen, office, opened).
doorstate(kitchen, cellar, opened).

Существует путь между двумя комнатами, если все двери между ними открыты.

Как мне написать правило, чтобы выяснить, существует ли такой путь между двумя комнатами?

Answer 1

Ужасный ужас пролога возвращается слишком быстро.

wayopen(Room1,Room2) :- doorstate(Room1, Room2, opened).
wayopen(Room1,Room2) :- doorstate(Room1, RoomX, opened), wayopen(RoomX,Room2).

Так что я не просто делаю твою домашнюю работу для тебя, вот как это понять:

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

Обратите внимание, что эти правила могут проходить через двери только в одном направлении. Ваша домашняя работа - заставить ее работать в обоих направлениях.

Куда мы можем попасть из зала?

?- wayopen(hall, X).
X = diningroom ;
X = kitchen ;
X = office ;
X = cellar ;
false.

Вот все комнаты, из которых вы можете получить:

?- wayopen(Room1,Room2).
Room1 = hall,
Room2 = diningroom ;
Room1 = diningroom,
Room2 = kitchen ;
Room1 = kitchen,
Room2 = office ;
Room1 = kitchen,
Room2 = cellar ;
Room1 = hall,
Room2 = kitchen ;
Room1 = hall,
Room2 = office ;
Room1 = hall,
Room2 = cellar ;
Room1 = diningroom,
Room2 = office ;
Room1 = diningroom,
Room2 = cellar ;
false.

Answer 2

Вам необходимо описать отношение (exists_way/2), которое является симметричным и транзитивным. В Прологе, который поддерживает табулирование (например, XSB ), вы можете выразить эти отношения очень естественным образом, то есть, как они выражены в математических книгах.

:- table exists_way/2.

% Open doors
exists_way(hall, 'dining room').
exists_way('dining room', kitchen).
exists_way(kitchen, office).
exists_way(kitchen, cellar).

% Symmetry
exists_way(R1, R2) :-
    exists_way(R2, R1).

% Transitivity
exists_way(R1, R2) :-
    exists_way(R1, R3),
    exists_way(R3, R2).

В этом случае запрос exists_way(R1, R2) предоставляет ровно 25 уникальных решений.

Answer 3

Вам необходимо описать отношение (exists_way/2), которое является симметричным и транзитивным.

% Base cases
exists_way_(hall, 'dining room').
exists_way_('dining room', kitchen).
exists_way_(kitchen, office).
exists_way_(kitchen, cellar).

% Symmetric
exists_way(R1, R2) :- exists_way_(R1, R2) ; exists_way_(R2, R1).

% Transitive
exists_way(R1, R2) :-
    exists_way_(R1, R3),
    exists_way(R3, R2).

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

Answer 4

В духе обучения: это та же проблема, что и проблема бабушки и дедушки, которую вы, вероятно, решали в первую неделю вашего курса пролога.

Оказывается, довольно много вещей, которые вы будете делать в прологе, будут очень похожи по структуре. Поэтому убедитесь, что вы понимаете идеи о рекурсивных предикатах и ​​о том, как должен выглядеть порядок предложений для исправления и выполнения.

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