Programmation.autre : [Prolog]Liste des chemins allant d'un point à un autre dans un graphe
Posté par Ontologia (page perso, ) le 04 avril 2008Bonjour, 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
> Lire le message (5 commentaires, moyenne: 2,4).
Vous avez demandé le commentaire #919921.
Run by 
Cette page a été générée par Templeet en 0.0499s (dont 0.0042 de SQL).
Cette page est peut-être conforme xhtml 1.0.
Information sur le site.
ebauche de solution
Chouette, du prolog, ça faisait longtemps :)
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
Petite correction :
C'est connected(P,P,[]). En effet, le chemin entre P est P est nul.
[^]Re: ebauche de solution
Génial, ça marche.
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 :-(
[^]Re: ebauche de solution
Avec quel interpreteur ?
Peut etre cela vaut-il le coup d'essayer avec un autre interpreteur (gprolog, swi-prolog, ...)
[^]Re: ebauche de solution
Ah oui j'ai oublié.
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 !