Discussion :

[denolfj]

Bonjour,

J'aimerais trouver le meilleur chemin entre n points. Chaque point est défini par un prédicat type :
arc(X,Y) -> renvoie vrai si les points X et Y sont liés...

J'ai déjà l'algorithme pour trouver le meilleur chemin entre 2 points, mais je voudrais l'étendre sur une liste de points...


Merci

[pcaboche]

Vu comme le problème est posé, on admet que les arcs du graphe ont tous le même poids (autrement dit, la 'distance' est la même pour tous les arcs). N'est-ce pas?

Pour le meilleur chemin entre 2 points, il s'agit en fait d'implémenter l'algorithme de Dijkstra en Prolog. Pour cela, tu auras besoin:
- de la liste des noeuds déjà visités
- de la liste des chemins en cours d'évaluation
et de procéder à un parcours en largeur.

Maintenant, ce que je ne comprends pas, c'est quand tu dis que tu veux "étendre ce problème à une liste de n points". Qu'est-ce que tu cherches exactement? L'arbre de recouvrement minimum? (dans ce cas, tu as les algo de Prim et Kruskal à ta disposition)

Donne-nous des précisions quant à la nature exacte de ton problème (avec si possible des exemples).

[denolfj]

En fait j'ai deja implementer les algorithmes pour 2 points, mais je voudrais pouvoir passer une liste de points et obtenir le chemin le + court pour relier tous ces points entre eux...

Je vais regarder les algo de Prim et Kruskal

Merci

[pcaboche]

Dit autrement, c'est comme si tu avais des villes et que tu devais relier TOUTES les villes au moyen de conduites de gaz en utilisant le moins de conduites possibles pour minimiser les coûts. C'est ça? Dans ce cas là, c'est bien Prim ou Kruskal qu'il te faut.

Maintenant, si tu veux approvisionner seulement certaines villes en gaz et pas toutes, il faudra adapter l'algo (en utilsant plusieurs fois Dijkstra).

[denolfj]

Tu as tout compris !!!!

Je veux passer dans une liste mes villes à relier (et que celles là) et avoir la liste des conduites...

Je vais essayer de me debrouiller avec les algo dont tu me parles, par contre si tu as une adresse sur le web ou les trouver, je suis preneur...

Merci

[pcaboche]

Bon alors c'est nickel, je vais pouvoir t'aider.

Au départ, on a une liste de villes à relier entre elles. On prendra comme exemple [a,b,c,d].

On écrit un prédicat qui va nous renvoyer tous les couples possibles entre ces villes, sous forme de tuples: [(a,b), (a,c), (a,d), (b,c), (b,d), (c,d)]. C'est très facile à faire.

De là, on a le prédicat: dijkstra(+P1, +P2, -Chemin, -Distance) qui, à partir des points P1, P2, nous renvoie le chemin le plus court entre P1 et P2 ainsi que la longueur total de ce chemin.

On fait donc la liste de tous les chemins les plus courts entre toutes les villes considérées, avec leur poids respectifs. Cela nous donne donc un nouveau graphe pour lequel on va chercher l'arbre de recouvrement minimum grâce à l'algorithme de Kruskal:
- tu tries tous ces chemins par longueur croissante
- tu parcours la liste des chemins triés en ne gardant à chaque fois que les chemins pour lesquels l'une des extrèmités (au plus) a déjà été visitée mais pas l'autre

Voilà, tu as résolu ton problème!

[denolfj]

Tout d'abord, merci pour ta réactivité !!

En fait je pense m'être mal exprimé...

Mon but est de realiser un requeteur SQL automatique:
Je passe une liste de table à joindre et il me retourne la liste de toutes les tables à utiliser.

Ex : je veux relier les Tables a,b,c et d entre elles. mais pour relier a à b je dois passer par une table e ou une table f et une table g, idem eventuellement pour les autres tables.

J'ai deja ecrit ma fonction lien(A,B,Liste) ou Liste contiendra la + courte liste des tables me permettant de relier A à B
Dans l'exemple : Liste : [A,E,B].

Là ou cela se complique c'est pour n tables, pour l'instant je fais les choses suivantes :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
lien3Tables(A,B,C,Liste):-
     lien(A,B,Liste),
     member(C,Liste).
 
lien3Tables(A,B,C,Liste):-
     lien(A,C,Liste),
     member(B,Liste).
 
lien3Tables(A,B,C,Liste):-
     lien(C,B,Liste),
     member(A,Liste).

Mais bon , ce n'est pas top et je dois ensuite recuperer la + petite de ces listes...

Si je pouvais le généraliser à N tables, j'aurais atteind mon but !!!

J'espere avoir été + clair sur mon besoin.

Merci

[pcaboche]

Il y a quelque chose qui me choque dans ton "requeteur SQL automatique": avoir une jointure entre des tables n'est pas suffisant pour dire qu'il existe un "chemin" entre toutes ces tables: il faut également prendre en compte la signification de la jointure par rapport à ces tables.

Ainsi, entre 2 tables, tu peux avoir plusieurs jointures ayant une sémantique complètement différente. De même, tu peux avoir des jointures réflexives (relations "père-fils") pour traduire une hiérarchie. Par conséquent, ce n'est pas parce qu'il existe un "chemin" entre 2 tables que ce chemin aura forcément un sens au niveau applicatif.

Par ailleurs, toutes les jointures ne sont pas de type "INNER JOIN". Il existe d'autres types de jointures, en particulier les "LEFT OUTER JOIN", les produits cartésiens, parfois combinées entre elles (prod. cartésien + LEFT JOIN) avec des conditions de restriction particulières (ex: "WHERE champ IS NULL"). On a aussi d'autres opérateurs ensemblistes tels que l'UNION (UNION DISTINCT et UNION ALL).

Bref, il est pour ainsi dire impossible de généraliser un tel problème. La seule manière de s'en sortir, c'est de créer des "vues", c'est à dire une sorte de table qui aura le même comportement qu'une requête SQL donnée, avec les jointures qui conviennent (et qui ont un sens au niveau applicatif). Ainsi, il est possible d'intéroger directement cette vue et de faire des jointures à partir de cette vue. Autrement, ce n'est pas possible.

[denolfj]

Je suis d'accord avec toi, mais les cas que tu exposes ne sont que 10 à 20 % des requetes. DOnc je règle en automatique 80% des cas et pour le reste, comme c'est du spécifique, le développeur pourra les écrire et les optimiser...

Concernant les left outer join , ce n'est pour moi qu'un inner join particulier( modification de la requete par un autre processus ).

En fait, une fois que j'ai le chemin, que je connais les clés primaires, il ne me reste plus qu'à les relier...

Donc pour revenir sur mon requeteur, j'utilise une modelisation UML.
La base de données est modélisée en diagramme de classe ou les tables sont des classes reliées par des associations et contenant des attributs (colonnes de la table).

Mon developpeur indique les tables qu'il veut relier et je lui sors la requete où il n'a plus qu'à rajouter ses restrictions...

[pcaboche]

En fait, ce qu'il te faut, c'est le plus court chemin qui passe par tous les points de la liste, c'est ça?

(désolé de ne pas avoir été aussi réactif qu'avant, mais j'ai eu des choses à faire après 18h...).

[pcaboche]

Je repense à ton problème et voilà comment on peut procéder:

Au départ, on a un graphe vide, la liste des tables à relier entre elles et une troisième liste, dont on verra l'utilisté après:
([], [a,b,c,d], [])

On recherche le chemin le plus court 2 tables de notre liste, on trouve par exemple le chemin [a,e,c], on ajoute ce chemin à notre graphe et on enlève les point a et c de notre liste. On obtient alors:

([a,c,e], [b,d], [[a,e,c]])

On cherche ensuite le chemin le plus court qui relie l'un des points du graphe obtenu à l'un des points b et d. On trouve [e,h,d]:

([a,c,d,e,h], [b], [[a,e,c],[e,h,d]]).

On continue ainsi jusqu'à ce qu'on ait relié toutes les tables.

***
La troisième liste permet de savoir en fin d'algorithme comment effectuer les jointures
***

Maintenant, il faut que tu prennes en compte un nouveau facteur pour ton problème: le poids des arcs. Au début on a supposé que les arcs étaient tous de même poids. Ce n'est pas vrai: le poids de tes arcs varie en fonction de la volumétrie de tes tables (volumétrie estimée lors de l'analyse).

Si on a par exemple l'arc : arc(a,b) entre a et b, le poids de cet arc sera donné par la formule:
poids( arc(a,b) ) = volume(a)*volume(b)

En effet, il vaut mieux faire une liaison entre 3 tables de 10 enregistrements (10*10*10=1000), qu'entre 2 tables de 100 enr. (100*100=10000).

***
Voilà, j'espère t'avoir aidé pour ton problème (si c'est le cas, je te demanderai peut-être une lettre de recommendation).

[denolfj]

Bien vu, c'est pas mal du tout l'idée de la 3eme liste...

Je vais l'utilisé avec un autre algo qui test avec le + court mais qui ramene egalement les autres chemin. En effet le + court ne sera pas forcement le mieux au final...

Pour le problème de poids des arcs, tu as tout a fait raison sur le fond, mais je ne veux pas surcharger la modelisation, et donc les requete seront retouchées à la fin manuellement (toujours la règle des 80%).

Encore merci pour ta réactivité !!!! Et pas de problème pour la lettre de recommendation :-))

[pcaboche]

Encore merci pour ta réactivité !!!!

De rien !

Et pas de problème pour la lettre de recommendation :-))

On verra ça par mp.


Si tu as un problème quelconque, n'hésite pas à le soumettre sur ce forum. On a relativement peu de questions à propos de Prolog.

[denolfj]

!!!! Challenge !!!!

Bon passons aux choses sérieuses...

Voici mes règles (Pour info , c'est en SWI-Prolog) :

ou isLien(A,B) renvoie vrai si A et B sont directement liés...
Ensuite les commentaires parlent d'eux meme...

Pour l'instant les règles isLien3 et isLien4 me renvoient la liste de tous les chemins possibles...

Question : saurais-tu les rendre générique avec ton idée de double liste ou autre ??

Ma solution pour le moment consiste à prendre la sous-liste de + petite taille, pas top...

PS : Je suis également grand fan de futurama !!! Cher Bender ;-)

----------------------------------------
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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
% **** tous chemins entre 2 tables non directement liées... ****
isLien2Table(X,X,_,[X]).
 
isLien2Table(X,Y,P,[X|C]) :-
	isLien(X, Z),
	\+ member(Z,P),
	isLien2Table(Z,Y,[X|P],C).
 
% **** chemin le + court entre 2 tables non directement liées... ****
isLienCourt([ouvert(Destination,C)|_], Destination, _, C).
 
isLienCourt([ouvert(A,B)|T], Destination, K, C) :-
        findall(ouvert(N,[N|B]), (isLien(A,N),\+ member(N,K)), S),
        append(T,S,L),
        isLienCourt(L, Destination, [A|K], C).
 
isLien2TableCourt(Origine, Destination, C) :- isLienCourt([ouvert(Origine, [Origine])], Destination, [], C).
 
 
% **** Lien entre 2 tables ****
isLien2(A, B, Liste) :- isLien2TableCourt(A,B,Liste).	
isLien2(A, B, Liste) :- isLien2Table(A,B,[],Liste).
 
% **** Lien entre 3 tables ****
isLien3(A,B,C,Liste) :-
	isLien2(A, B, Liste),
	member(C,Liste).
 
isLien3(A,B,C,Liste) :-
	isLien2(A, C, Liste),
	member(B,Liste).
 
isLien3(A,B,C,Liste) :-
	isLien2(B, C, Liste),
	member(A,Liste).
 
% **** Lien entre 4 tables ****
isLien4(A,B,C,D,Liste) :-
	isLien3(A, B,C, Liste),
	member(D,Liste).
 
isLien4(A,B,C,D,Liste) :-
	isLien3(A, C, D, Liste),
	member(B,Liste).
 
isLien4(A,B,C,D,Liste) :-
	isLien3(A, D, B, Liste),
	member(C,Liste).
 
isLien4(A,B,C,D,Liste) :-
	isLien3(D, B,C, Liste),
	member(A,Liste).

[pcaboche]

PS : Je suis également grand fan de futurama !!! Cher Bender

Eat my shiny metal ass, meatbag !

Sinon, comment peux-tu affirmer qu'il s'agit de Bender? Ca pourrait tès bien être Flexo, le double de Bender (Episode "The lesser of two evils"). Oui, j'adore cette série!

J'ai pensé me pencher sur ton problème... mais il se trouve que je suis déjà en pyjama (dixit le professeur Farnsworth: "although I'm already in my pajamas" )

***
Plus sérieusement, j'ai regardé ce que tu as fait, mais ça n'est pas efficace du tout. En fait, tu cherches à générer les chemins de longueurs 1, 2, 3... n en vue de rechercher le plus court. Heureusement que tu n'as pas énormément de points parce que c'est exponentiel comme problème !

Comme je t'ai expliqué, on a l'algorithme de Dijkstra à notre disposition pour la recherche du plus court chemin. C'est d'ailleurs celui-là que j'ai implémenté. J'ai mis des commentaires de manière à être plus clair.

Pour être le plus générique possible, j'ai également attribué un poids aux arcs (au cas où quelqu'un chercherait une implémentation de Dijkstra en Prolog...).

Dans ton cas, c'est un peu particulier: les poids ne dépendent pas des arcs mais des sommets du graphe. En plus il ne faut pas les additionner mais les multiplier. Il faudra adapter l'ago en conséquence (si jamais tu décides de prendre en compte la volumétrie dans ton modèle).


Pour ce qui est des points visités, on dispose des infos suivantes:
- la longueur totale du chemin
- le chemin complet, mais en ordre inverse
sous la forme: Longueur-[Pn, P3, P2, P1], ceci afin d'avoir recours au prédicat keysort/2 pour trier les chemins selon la longueur.


Voilà pour les explication, voyons maintenant ce que ça nous donne:

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
arc(a,b,5).
arc(a,c,5).
arc(b,c,5).
arc(c,d,5).
 
 
%
% Dijkstra
%   + Start        : Point de départ
%   + Finish       : Point de d'arrivée
%   - ShortestPath : Chemin le plus court
%   - Len          : Longueur de ce chemin
%
 
 
dijkstra(Start, Finish, ShortestPath, Len) :-
  dijk( [0-[Start]], Finish, RShort, Len),
  reverse(RShort, ShortestPath).
 
 
 
% Le dernier point visité est le point d'arrivé => on s'arrête
%
 
dijk( [ Len-[Fin|RPath] |_], Fin, [Fin|RPath], Len) :- !.
 
 
dijk( Visited, Fin, RShortestPath, Len) :- 
 
  % Recherche du meilleur candidat (prochain point à ajouter au graphe)
  %
 
  candidates(Visited, Visited, Cands),
  minimum(Cands, BestCandidate),
 
  dijk( [BestCandidate|Visited], Fin, RShortestPath, Len).
 
 
 
%
% Recherche toutes les arêtes pour lesquelles on a: 
%  - un point dans le graphe (visité)
%  - un point hors du graphe (candidat)
%
% Retourne les points en question (+ Chemin et Longueur_Chemin)
%
 
candidates([],_,[]) :- !.
 
candidates([Len-[P1|Path] | Other], Visited, Cand) :-
 
  % Recherche des points susceptibles d'être ajoutés au graphe
  %
 
  findall(NP,
   ( arc(P1,P2,Dist), \+isVisited(Visited, P2), NLen is Len+Dist, NP=NLen-[P2,P1|Path] ),
   L1),
 
  % On continue la recherche sur les autres points du graphe (visités)
  %
 
  candidates(Other, Visited, L2),
  append(L1, L2, Cand).
 
 
 
%
% Test si un point P a déjà été visité
%
 
isVisited([(_-[P|_])|_], P) :- !.
isVisited([_|Q], P) :- isVisited(Q, P).
 
 
 
%
% Sort le meilleur candidat parmi une liste de candidats
% (= celui de chemin le moins long)
%
% TODO: possibilité d'optimisation: 
%   remplacer keysort/2 par une recherche de minimum
%
 
minimum(Candidates, BestCandidate) :-
  keysort(Candidates, [BestCandidate|_]).
 
 
test :-
  dijkstra(a, d, Short, Len),
  write(Short), write(' '), write(Len), nl.

J'ai pas tout testé à fond mais ça à l'air correct (j'ai fait varier les poids des arcs)

***
Maintenant, si on s'en réfère à mon 3ème post de ce fil de discussion, on a bien le prédicat dijkstra avec les bons paramètres. Ce prédicat nous permettra d'obtenir un "sur-graphe" (graphe définit au-dessus du précédent) sur lequel on va appliquer l'algo de Kruskal.

***
Tout ceci me donne plein d'idées d'articles:
- les listes en Prolog + fonctions prêtes à l'emploi (keysort, append, reverse...)
- utilisation de findall/3, bagof/3, setof/3 et parcours en largeur
- algorithme sur les graphes en Prolog (Dijkstra, Kruskal, Prim, Bellmann-Ford...)

Sans compter celui que je suis en train de rédiger et ceux que j'ai en tête... ça en fait du boulot !

***
Voilà, j'espère t'avoir aidé au mieux. J'avais envie de boucler ça pour que tu puisses le lire traquillement le matin en arrivant au boulot... maintenant je vais me pieuter. Bonne nuit !

[denolfj]

Impressionnant !!!

Je test ça cet aprem et je te tiens au courant , mais ça m'a l'air vraiment pas mal !!!

Encore Merci pour ta réactivité !!!!

[denolfj]

Bon en y regardant de + près , ça ne resoud pas mon problème de relier tous les points d'une liste, là je relie 2 points entre eux par le + court chemin...

Je me trompe ??

[pcaboche]

Non, tu ne te trompes pas.


Relis mon 3ème message:

Bon alors c'est nickel, je vais pouvoir t'aider.

Au départ, on a une liste de villes à relier entre elles. On prendra comme exemple [a,b,c,d].

On écrit un prédicat qui va nous renvoyer tous les couples possibles entre ces villes, sous forme de tuples: [(a,b), (a,c), (a,d), (b,c), (b,d), (c,d)]. C'est très facile à faire.

De là, on a le prédicat: dijkstra(+P1, +P2, -Chemin, -Distance) qui, à partir des points P1, P2, nous renvoie le chemin le plus court entre P1 et P2 ainsi que la longueur total de ce chemin.

On fait donc la liste de tous les chemins les plus courts entre toutes les villes considérées, avec leur poids respectifs. Cela nous donne donc un nouveau graphe pour lequel on va chercher l'arbre de recouvrement minimum grâce à l'algorithme de Kruskal:
- tu tries tous ces chemins par longueur croissante
- tu parcours la liste des chemins triés en ne gardant à chaque fois que les chemins pour lesquels l'une des extrèmités (au plus) a déjà été visitée mais pas l'autre

Voilà, tu as résolu ton problème!

Le code que je t'ai donné correspond à la partie en gras. Reste à coder le reste...

Sinon, est-ce que ça marche? Ca donne bien une approximation du plus court chemin entre 2 points?

[denolfj]

Et bien j'ai le regret de t'apprendre que ton algo fonctionne mais ne ramène pas le chemin le + court...

Je ne cherche pas à améliorer cet algo, je veux juste l'étendre et au lieu de passer 2 paramètres, passer une liste.

[pcaboche]

Et bien j'ai le regret de t'apprendre que ton algo fonctionne mais ne ramène pas le chemin le + court...

L'algo de Dijkstra renvoie une approximation du chemin le plus court (maximum 60% plus long que le chemin le plus court, je crois), mais sans tester toutes les combinaisons possibles (problème NP-complet, je crois).

Et puis j'ai aussi pu faire une erreur. Ca arrive.

***
Sinon, si tu veux une liste exhaustive des chemins sans cycle du graphe pour ensuite ne garder que le plus court, c'est possible (mais les calculs risquent d'être longs). Si il faut, on peut toujours rechercher un éventuel bug dans mon implémentation de l'algo de Dijkstra.

***

Je ne cherche pas à améliorer cet algo, je veux juste l'étendre et au lieu de passer 2 paramètres, passer une liste.

Et la méthode que je t'ai proposé ne te convient pas? (faire la liste de tous les "plus courts chemins" entre les points considérés, les trier, etc. (bref tout ce qui est décrit à la suite du paragraphe en gras)