Traverse graphique non orienté dans prolog

Question

En bref: J'essaie de traverser un graphe non orienté en prologue, mais je ne sais pas comment, tout conseil serait grandement apprécié.

Contexte:

Essayer de modéliser le système ferroviaire, avec des stations comme des noeuds et leurs liens comme bords avec un poids 1.

J'ai eu aucun problème à faire d'une manière dirigée, mais ne peux pas le faire dans un graphe non orienté.

sur le net en général, je l'ai appris que le graphique est déclaré non orienté de la manière suivante:

node(1). 
node(2). 
node(3). 
node(4). 
node(5). 
node(6). 

arc(1,2):-node(1),node(2),1==2. 
arc(1,4):-node(1),node(4),1==4. 
arc(2,3):-node(2),node(3),2==3. 
arc(3,5):-node(3),node(5),3==5. 
arc(4,5):-node(4),node(5),4==5. 
arc(5,6):-node(5),node(6),5==6. 

path(X,Z,A) :- (arc(X,Y),path(Y,Z,A1),A is A1+1;arc(X,Z), A is 1). 

ainsi, le chemin de requête (1,2, X). devrait retourner 1, mais il ne le fait pas ... vraiment besoin d'aide/d'orientation .. merci!

Answer 1

Voici quelques pointeurs: Pour modéliser un graphe non orienté, vous n'avez pas besoin du fait 'node', juste le fait 'arc'. Que voulez-vous reconnaître avec le fait 'arc', bien qu'il y ait un arc entre les deux nœuds. Donc, vous auriez besoin seulement quelque chose comme

arc(1, 2). 
arc(1, 4). 
... 

Maintenant, selon votre définition de chemin, il semble que vous voulez que la requête pour réussir s'il y a un chemin de X à Y avec un poids total de A. Si vous aviez affaire avec des graphiques réalisés qui pourraient être exprimés avec un prédicat comme celui-ci:

path(X, Y, 1):- arc(X, Y). 
path(X, Y, A):- arc(X, Z), Z\=Y, 
       path(Z, Y, A1), 
       A is A1+1. 

Notez cependant que cela peut conduire à des boucles infinies si le graphe est cyclique. Pour éviter ce problème, vous pouvez suivre les nœuds visités, de sorte que vous visitez presque une fois par noeud:

path(X, Y, A):- path(X, Y, [X], A). 

path(X, Y, _, 1):- arc(X, Y). 
path(X, Y, Visited, A):- arc(X, Z), 
          not(member(Z, Visited)), 
          path(Z, Y, [Z|Visited], A1), 
          A is A1+1. 

Maintenant, cet algorithme peut être modifié trivialement pour traiter les graphes non orientés, en ajoutant juste une clause. Merci d'avoir signalé cette erreur (1 == 2) que je faisais, kaarel et merci pour la réponse gusbro

Answer 2

Gusbro, je voudrais clarifier si en effet un graphique non orienté est créé.

C'est ce que j'ai écrit pour créer un graphique non orienté.

arc (1,2).

arc (2,1).

arc (1,4).

arc (4,1).

arc (2,3).

arc (3,2).

arc (3,5).

arc (5,3).

arc (5,6).

arc (6,5).

ainsi le chemin (1,4) devrait montrer 1; 4; non. Où 1 est le chemin direct entre les nœuds 1,4 et 4 est le chemin à partir des nœuds 1-2-3-5-4.

Mais ce n'est pas le cas. A la place, j'obtiens

A = 1;

A = 3;

A = 5;

A = 7;

A = 9;

A = 11

Vous ne savez pas pourquoi?

Answer 3

Merci de m'avoir indiqué la bonne direction. J'ai modifié votre code un peu pour atteindre mon objectif de parcourir les graphes non orientés:

path(X, Y, A):- % this method allows user to input a path to be checked 
    path(X, Y, [X], A). % this is to ensure a list exists, to determine visited nodes later. 

member(X,[X|_]). % X can be head of list. 
member(X,[_|Tail]) :- 
    member(X,Tail). %X can be tail of list, regardless of what the head is. 

path(X, Y, Visited, A):- 
    ( arc(X,Y), A is 1 
    ; not(arc(X,Y)), 
     arc(X, Z), 
     not(member(Z,Visited)), 
     path(Z, Y, [Z|Visited], A1), 
     A is A1+1 
    ). 
% this method checks if a direct/indirect path exists between X,Y in undirected graph 

Je ne me sens pas encore comme j'ai une bonne connaissance encore de récursivité. Apprécierait tous les pointeurs pour mieux le comprendre, en plus de la pratique de cse :)

Merci pour l'aide!