Définir un graphe dans Prolog: edge et path, trouver s'il existe un chemin entre deux sommets

Je suis très nouveau à Prolog. J'ai défini dans graph.pl le graphique suivant:

Et voici mon Prologue code:

edge(a,e).
edge(e,d).
edge(d,c).
edge(c,b).
edge(b,a).
edge(d,a).
edge(e,c).
edge(f,b).
path(X,X).
path(X,Y):- edge(X,Z) ; path(Z,Y).

Je le comprends comme ceci: il y a un chemin entre les vertex X et vertex Y seulement si il existe une arête entre le sommet X et vertex Z ET il y a un chemin entre les vertex Z et vertex Y (une sorte de récursivité).

Est que pour la présentation graphique? Quand je demande Prologue sur le chemin entre le sommet A et vertex F il me donne true ... qui n'est même pas droit! Ce qui ne va pas dans ce code?

source d'informationauteur yak | 2014-01-16

Cycles dans le graphe. Vous avez besoin de suivre ce que les nœuds que vous visitez, et de les vérifier. Essayez ceci, à l'aide d'un helper prédicat avec un accumulateur de suivre les nœuds visités:

path(A,B) :-   % two nodes are connected, if
  walk(A,B,[]) % - if we can walk from one to the other,
  .            % first seeding the visited list with the empty list

walk(A,B,V) :-       % we can walk from A to B...
  edge(A,X) ,        % - if A is connected to X, and
  not(member(X,V)) , % - we haven't yet visited X, and
  (                  % - either
    B = X            %   - X is the desired destination
  ;                  %   OR
    walk(X,B,[A|V])  %   - we can get to it from X
  )                  %
  .                  % Easy!

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

5

Le format que vous utilisez (edge/2) faire sens pour l'apprentissage de Prolog, et vous devez suivre mbratch avis sur le tutoriel.

En fait, il y a des bonnes alternatives déjà disponibles, dans certains cas avec des prédicats prêt à aller: par exemple, dans la bibliothèque(ugraph), il est accessible/3. Maintenant, avec vos données, ce chemin/2 prédicat
```
path(X,Y) :-
    findall(A-B, edge(A,B), Es),
    vertices_edges_to_ugraph([],Es,G),
    reachable(X,G,Path),
    member(Y,Path).
```
ne
```
?- path(a,X).
X = a ;
X = b ;
X = c ;
X = d ;
X = e.
```
Voyons ce que cela signifie:
```
findall(A-B, edge(A,B), Es)
```
mettre en Es de tous les bords, avec la notation comme requis par la bibliothèque,
```
vertices_edges_to_ugraph([],Es,G)
```
construit en G le graphique correspondant
```
reachable(X,G,Path)
```
faire une liste de tous les sommets accessibles (duh) à partir de X
```
member(Y,Path)
```
voir si Y est présent dans le Chemin d'accès.

Depuis que j'ai interrogé avec Y gratuitje reçois tous les sommets accessibles à partir de X, que j'ai lié à a.
3

Si vous êtes intéressé à en savoir si un chemin existe—mais pas nécessairement dans le chemin d'accès réel(s)—calculer la fermeture transitive de la relation binaire edge/2.

Heureusement pour vous, transitif-fermeture est une commune de l'idiome dans prologue!

Pour exprimer la irreflexive fermeture transitive de edge/2utiliser les méta-prédicat fermeture/3défini dans la question précédente "Définition de la Réflexivité Fermeture Transitive":
```
?- fermeture de bord, X, Y). 
X = a, Y = e 
; X = a, Y = d 
; X = a, Y = c 
; ... 
```
Noter que closure/3 a de très bonnes résiliation propriétés.

Si toutes les clauses de edge/2 sol sont faits, closure(edge, _, _) se termine universellement! Look:
```
?- closure(edge, _, _), false.
false.
```
2

De contrôle, il est dans un cycle de!
J'ai exécuté l'exemple avec le trace. commande avant de la main, et vit, le programme revient au problème de trouver le chemin de a à f après le vélo autour de.
chemin(a,f) besoins chemin(e,f). pour être vrai, suivant en bref notation nous avons besoin pour être vrai:

(d,f), (c,f), (b,f), alors (a,f).

De résoudre la boucle vous avez besoin d'un mécanisme pour empêcher la boucle. Ma première Idée serait de garder une liste de nœud-noms et également vérifier si la liste ne comprend pas les X actuels, tout en vérifiant le chemin.

Vous devez vous connecter pour publier un commentaire.