Trouver Prolog Path

Question

Si je le prédicat suivant porte , qui déclare qu'il ya une porte entre les deux chambres:

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

Et le prédicat doorstate qui déclare l'état d'une porte:

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

Il y a un chemin entre deux chambres si toutes les portes entre eux sont ouverts.

Comment puis-je écrire une règle pour découvrir s'il y a une telle voie entre deux chambres?

Answer 1

L'horreur abjecte de Prolog retourne trop rapidement.

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

Je ne suis pas seulement faire vos devoirs pour vous, voici comment le comprendre:

• La voie est ouverte entre les deux chambres si elles sont reliées par une porte et la porte est ouverte.
• La voie est ouverte entre deux chambres, si la première voie a une porte ouverte à une autre pièce, et il y a un moyen de l'autre chambre à la deuxième chambre.

Notez que ces règles ne peuvent passer par des portes dans une direction. Votre devoirs est de le faire fonctionner dans les deux sens.

Où peut-on arriver à de la salle?

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

Voici toutes les chambres, vous pouvez obtenir à partir et à:

?- 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

Vous devez décrire une relation (exists_way/2) qui est symétrique et transitive.

% 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).

Ce code génère des solutions sur-bien. Donc, vous devez filtrer les doublons plus tard.

Answer 3

Vous devez décrire une relation (exists_way/2) qui est symétrique et transitive. Dans un Prolog qui prend en charge le dépôt (comme XSB ), vous pouvez exprimer ces relations d'une manière très naturelle, à-dire qu'ils sont exprimés dans les livres de mathématiques.

:- 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).

Dans ce cas, la requête de exists_way(R1, R2) offre exactement 25 solutions uniques.

Answer 4

Dans l'esprit de l'apprentissage. Ceci est le même problème que le problème de grand-parent vous avez probablement fait dans la première semaine de votre cours Prolog

Il se trouve que beaucoup des choses que vous ferez dans Prolog sera tout à fait similaire dans sa structure. Donc, assurez-vous saisir les idées sur prédicats récursifs, et comment l'ordre dans lequel les clauses doivent aller, pour la correction et la performance.

Par exemple, vous devriez éviter non-queue récursion si possible.