Discussion :

[raphael.portillo]

Bonjour,

Je voudrais bien savoir si quelqu’un parmi vous peut m’aider. Je dois écrire un programme qui calcule les chemins possibles d’un réseau du métro (grâce à une base de faits), calcule le chemin le plus court et après génère tous les chemins par ordre de croissance. Pour la première partie, c’est ok. Voici le code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
connexion(lumiere,eau).
connexion(eau,pierre).
connexion(pierre,gaz).
connexion(mix,pierre).
connexion(pierre,pas).
connexion(pas,coup).
connexion(coup,gaz).
connexion(gaz,can).
connexion(can,mix).
 
reseau(X,X,_, [X]). 					/*reseau(station_de_depart,station_de_arrivee,station_interdite,chemin)*/
reseau(X,Y,Station_int, [X|Chemin_a_faire]) :-
	connexion(X,Z),					/*La station interdite represente une station par laquelle notre trajet ne peut pas passer.*/
	not(dans(Z, Station_int)),
	reseau(Z,Y,[Z|Station_int], Chemin_a_faire).
reseau(X,Y,Station_int, [X|Chemin_a_faire]) :-
	connexion(Z,X),
	not(dans(Z, Station_int)),
	reseau(Z,Y,[Z|Station_int], Chemin_a_faire).

Par contre, pour trouver le chemin le plus court et pour les organiser, je n’arrive pas à concevoir leurs codes. J’ai déjà cherché à propos de l’algorithme de Dijkstra, mais cet algorithme est trop compliqué par rapport à mes besoins (mes distances entre deux stations n’ont pas de poids) et, en plus, je suis débutant en Prolog, ce qui malheureusement m’empêche de le comprendre.
Vous avez des idées pour m’aider ?

Merci beaucoup,
Raphael

[Trap D]

pour trouver le plus court chemin, tu peux faire une exploration en largeur du graphe, je te renvoie à cet article

[raphael.portillo]

Bonjour,

Merci d’avoir répondu Trap. Par contre, j’ai encore le même problème qu’avant. Vu que je suis débutant en Prolog, je n’arrive pas à comprendre comment ce code peut m’aider (je pense que, peut-être, je ne maîtrise pas assez le langage pour pouvoir faire les adaptations nécessaires).
J’ai déjà créé une fonction qui calcule la longueur d’une liste et une fonction que calcule le minimum. Mon idée serait de créer une fonction qui, tout de suite, garde le premier chemin donné par ma fonction « reseau » (voir mon premier post) et calcule sa respective longueur L1. Après, elle calcule la longueur L2 du chemin suivant et, si L2<L1, elle jette le premier chemin et garde le deuxième.
Je pense que le Logique du problème est déjà dans ma tête, mais le problème reste concevoir le langage. Quelqu’un aurait une idée ?

[Trap D]

Ton programme (que j'ai un peu modifié pour qu'il fonctionne en SWI-Prolog) est correct et te donne les chemins.
Pourquoi ne classes-tu pas ces chemins par ordre de longueur ?
Existe-t-il dans ton Prolog l'équivalent de bagof ?
Ce prédicat te permet d'obtenir toutes les solutions d'un but.