comment exactement un atome/1 prédicat fonctionne dans prolog?

Question

J'ai essayé de résoudre un problème de pathfinding dans Prolog.where les prédicats sont

edge(a,b).
edge(a,c).
edge(b,d).
edge(c,d).
edge(d,e).
edge(d,f).
edge(f,g).

les règles est
edge(X,Y) :- edge(X,Z), edge(Z,Y).
puis lorsque j'ai compilé et exécuté la requête | ?- edge(a,X). il montre Fatal Error: local stack overflow (size: 8192 Kb, environment variable used: LOCALSZ) alors j'ai cherché la solution et a trouvé que comprenant atom(x)., atom(y). dans notre règle peut résoudre le problème de débordement de pile. à savoir la nouvelle règle est

edge(X,Y) :- atom(X), atom(Y), edge(X,,Z), edge(Z,Y). et oui, il avait résolu le problème de débordement de pile .mais, je voudrais savoir comment exactement ce (atome/1) prédicat résout mon problème ici? et que fait-il à notre variables X,Y pour résoudre le problème StackOverflow? Je suis un débutant à Prolog toute aide serait appréciée merci. :)

Answer 1

Tout d'abord, le nom edge/2 ne décrit pas très bien votre prédicat. Vous voulez probablement vraiment path/2 qui consiste en un ou plusieurs bords.

Est-ce que atom/1 résout vraiment votre problème? En d'autres termes, edge(X, Y) fournit-il vraiment toutes les bonnes solutions à une requête? Tout ce que fait atom/1 est de s'assurer que son argument est un atome, donc il ne peut pas être une variable non liée. Donc edge(X, Y) ne fournit pas toutes les bonnes solutions. Il ne fournit que les solutions pour lesquelles vous avez des faits directs, car le prédicat edge(X, Y) tel que défini actuellement échoue toujours avec X ou Y non lié.

| ?- edge(a, Y). 

Y = b ? ; 

Y = c ? ; 

no 

Où est la solution Y = d par exemple? edge(X, Y) ne prend que les solutions qui sont données dans vos faits edge/2, mais pas de solutions qui incluent plusieurs bords connectés.

Votre problème d'origine est dû à la récursion infinie, qui est le résultat de edge/2 appelant lui-même inutilement. Naming peut effectivement être important ici car il rend la logique plus précise et correcte. On peut dire que edge(X, Y) signifie que X et Y forment un bord (et Y sont directement connectés). Nous pouvons dire que path(X, Y) signifie qu'il y a un chemin de X à Y via un ou plusieurs bords. En d'autres termes, un chemin de x à y peut être soit un bord de x à y, ou il peut être un bord de x à z et un chemin de z à y.

path(X, Y) :- edge(X, Y). 
path(X, Y) :- edge(X, Z), path(Z, Y). 

Maintenant, nous obtenons:

| ?- path(a, X). 

X = b ? a 

X = c 

X = d 

X = e 

X = f 

X = g 

X = d 

X = e 

X = f 

X = g 

(1 ms) no 
| ?- 

Il y a des doublons car il peut y avoir plusieurs façons d'obtenir a-e par exemple. Si vous incluez un argument qui montre le chemin parcouru, cela deviendra évident.

Cette solution n'est pas la fin de l'histoire, cependant. Vos faits actuels sont tels qu'il n'y a pas de chemins "détournés" (chemins qui finissent par revenir sur le même noeud s'ils sont suivis). Pour gérer cela, vous avez besoin d'un argument de prédicat pour garder une trace des nœuds/arêtes que vous avez déjà traversés et éviter de les traverser à nouveau.