Bonjour, je sèche sur un petit problème de prolog que je pratique trop peu pour le maîtriser vraiment.
Je cherche, tout est dans le titre, à lister, dans un graphe orienté, l'ensemble des chemins allant d'un point à un autre.
Exemple avec un début d'implémentation
J'ai donc pas mal d'atomes, du genre :
parcours(depart,arrivee).
parcours(depart,point1).
parcours(point1,point2).
parcours(point2,point3).
parcours(point3,point4).
parcours(point4,arrivee).
et je voudrai récupérer deux listes :
parcours(depart,arrivee).
et
parcours(depart,point1).
parcours(point1,point2).
parcours(point2,point3).
parcours(point3,point4).
parcours(point4,arrivee).
(ou sous une autre forme, ce n'est pas important)
J'ai une espèce de formalisation mathématique, que j'ai du mal à traduire en prolog :
Soit un prédicat :
Follow(P,Q) :- parcours(P,Z), parcours(Z,Q).
trouvechemin(Dep,Arriv) :- Qqsoit j appartient à [1;n-1], Follow(Pj,Pj+1), Follow(Dep,P2), Follow(Pn-1, Arriv).
En gros, je définis qu'il existe un sommet P2 (P indice 2) suivant mon sommet de départ dans mon graphe, et qu'il existe un sommet Pn-1 précédent mon sommet d'arrivée.
Entre les deux, il existe une série de sommets reliés les un aux autres.
J'ai en fait réalisé une espèce de définition par récurrence.
Question 1 : Ma formalisation vaut-elle quelques chose ?
Question 2 : Quelques pistes pour la traduire en prolog (en utilisant les listes probablement) ?
Merci
Forum Programmation.autre [Prolog]Liste des chemins allant d'un point à un autre dans un graphe
4
avr.
2008
# ebauche de solution
Posté par castorpilot . Évalué à 4.
Alors, pour repondre à 1), il me semble que la formulation est pas mal. Je dirait juste qu'elle n'est pas encore assez recursive : en gros, on devrait pouvoir laisser prolog se debrouiller tout seul.
Voila comment je listerai les chemins allant d'un point à un autre (c'est une solution, et bien sur pas LA solution).
Dans la meme veine que follow, je defini la fonction connected, qui ressemble à connected (point A, point B, chemin) :
connected(P,P,[P]).
% tout d'abord, un point est connecté à lui meme, et le chemin est le point lui meme.
% c'est ma condition d'arret de la recursivité.
connected(P,Q,[Z|Chemin]):-
parcours(P,Z), connected(Z,Q,Chemin).
% P est connecté à Q si P est Z sont dans un parcours (tel que tu l'as defini), et si Z lui
% meme est connecte à Q. C'est la transitivité de la connexion. Dans ce cas, je rajoute
% le point intermediaire Z au chemin.
Avec l'interpreteur, je peux maintenant faire :
connected(depart, arrivee, Chemin).
Et prolog va me lister tout les chemins possible via la variable Chemin, tant que j'appuie sur ";".
[^] # Re: ebauche de solution
Posté par castorpilot . Évalué à 3.
C'est connected(P,P,[]). En effet, le chemin entre P est P est nul.
[^] # Re: ebauche de solution
Posté par Ontologia (site web personnel) . Évalué à 2.
Par contre, mon volume de donnée étant un peu volumineux, je me prend des stack overflow dans tous les sens. J'ai 4Go sur la machine et il ne veut pas utiliser plus de 128 Mo :-(
« Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
[^] # Re: ebauche de solution
Posté par castorpilot . Évalué à 1.
Peut etre cela vaut-il le coup d'essayer avec un autre interpreteur (gprolog, swi-prolog, ...)
[^] # Re: ebauche de solution
Posté par Ontologia (site web personnel) . Évalué à 2.
Swi-prolog me permet une local stack de 128 Mo
gprolog me permet une stack de 4Mo...
De toutes façons, j'ai trouvé un exemple assez long ou l'interpréteur tronquait l'affichage de la liste si elle est trop longue...
M'enfin, ça m'a permis de trouver quelques résultats utiles :-)
Merci !
« Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.