Comment vérifier si deux sommets sont connectés ou non dans un prologue ?

Question

Mon problème est que je veux vérifier si deux nœuds sont connectés ou non.

Ma base de connaissances est la suivante

edge(a,b):-!.
edge(b,a):-!.
edge(a,e):-!.
edge(e,a):-!.
edge(b,c):-!.
edge(c,b):-!.
edge(b,d):-!.
edge(d,b):-!.
edge(c,e):-!.
edge(e,c):-!.
edge(d,e):-!.
edge(e,d):-!.
edge(a,f):-!.
edge(f,a):-!.

isConnected(X,X):-!.
isConnected(X,Y):-edge(X,Y),!.
isConnected(X,Z):-not(edge(X,Y)),edge(X,Y),isConnected(Y,Z),!.
isConnected(X,Z):not(edge(X,Y)),edge(X,Z),not(isConnected(Y,Z)),isConnected(Z,Y),!.

Answer 1

Whoa là. Cela fait beaucoup de coupes. Les coupes sont parfois utiles en Prolog pour élaguer les réponses inutiles, mais lorsque vous avez un fait comme celui-ci :

edge(a, b).

Il n'y a absolument rien à gagner à l'écrire comme :

edge(a, b) :- !.

Après tout, il n'y a pas de point de choix ici, parce qu'il n'y a pas de variables et pas de solutions alternatives. Commençons donc par corriger les faits en supprimant toutes ces coupes.

Voyons maintenant ce que dit isConnected. Lisons-le à haute voix en anglais et voyons s'il a un sens.

1. X est connecté à X.
2. X est connecté à Y s'il existe une arête reliant X à Y.
3. X est connecté à Z s'il n'y a pas d'arête de X à Y, mais il y a une arête de X à Y et Y est connecté à Z. ( ???)
4. X est connecté à Z s'il n'y a pas d'arête de X à Y, mais qu'il y a une arête de X à Z, et Y n'est pas connecté à Z mais Z est connecté à Y. ( ???)

Les deux premières semblent tout à fait raisonnables. La troisième semble se contredire d'emblée. Comment la not(edge(X, Y)) être vrai en même temps que edge(X, Y) ? Gardez à l'esprit que la virgule en Prolog signifie et et non seulement puis . Le reste de la clause n'a pas de sens car ces deux conditions ne peuvent jamais être toutes les deux vraies. Ce que vous vouliez probablement dire, c'est quelque chose comme ceci : X est connecté à Z s'il y a une arête de X à Y et Y est connecté à Z. Cela ressemblerait à ceci en Prolog :

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

Logiquement, c'est certainement vrai, mais pour n'importe quel type de graphe complexe, cela va être monstrueusement coûteux à calculer, parce que vérifier si X est connecté à Z peut impliquer de vérifier si Y est connecté à Z pour tous les mêmes nœuds.

Votre quatrième clause comporte une faute de frappe dans la mesure où le : devrait être un :- . Plus important encore, il semble que vous essayez de compenser la directionnalité de vos bords. Il aurait été préférable de le faire autour de l'étape 2, dans les deux cas :

isConnected(X, Y) :- edge(X, Y) ; edge(Y, X).

Je ne suis pas sûr, sur la base de votre base de données de faits, que vous le pensiez vraiment ; vous avez dupliqué tous vos faits pour tenir compte des deux directions. Si la base de données des faits représente un graphe orienté, c'est probablement nécessaire et les règles ne devraient pas essayer d'inverser les nœuds. Si elle représente plutôt un graphe non orienté, votre prédicat devrait en tenir compte avec une règle comme celle-ci qui vérifie les deux côtés, et vous ne devriez lister chaque arête qu'une seule fois. Dans les deux cas, vous demandez à Prolog de faire un tas de travail inutile, puisqu'il vérifie d'abord edge(a, b) , puis la règle l'inverse en edge(b, a) puis passe au fait suivant edge(b, a) puis la règle l'inverse en edge(a, b) et de vérifier en fait tout ce qui se passe

T