Discussion :

[sarmad354]

Bonjour tout le monde,

J'ai un problème que j'ai essayé d'assimiler au problème du « plus court chemin » sous contraintes :



On doit passer obligatoirement par chaque ensemble et, dans chaque ensemble, on doit passer seulement par une ellipse.

les contraintes peuvent être (à titre d'exemple) :

• passer par les ellipses rouges au maximum 2 fois ;
• passer par les ellipses vertes au maximum 3 fois ;
• passer par les ellipses bleues au maximum 2 fois ;
• passer par les ellipses jaunes au maximum 2 fois.

Ma question est de trouver l'algorithme pour déterminer le plus court chemin.
Merci d'avance.

[ToTo13]

Bonjour,

tu peux utiliser un dijkstra avec les contraintes, mais pour cela il te faut ajouter des informations lorsque tu es dans chaque noeud afin de vérifier si le chemin est valide (ne viole pas tes contraintes).

[sarmad354]

bonjour
Merci ToTo13 pour l'idée

[Trap D]

J'entends contraintes, aussitôt je dégaine Prolog et CLP(FD).

Voilà un exemple de programme :

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
:- use_module(library(clpfd)).
 
parcours :-
	Etapes= [[(rouge, 10), (vert, 15), bleu(20)],
		 [(vert,12), (rouge,12), (bleu, 15), (jaune, 17)],
		 [(vert, 12), (rouge, 14)],
		 [(bleu, 17), (jaune, 10), (vert, 8)]],
 
	length(Etapes, L),
	length(Poids, L),
	% on donne une limite aux poids    
	Poids ins 0..100,
 
	maplist(etudie, Etapes, Couleur, Poids),
	[NB, NJ, NR, NV] ins 0..4,
 
	% on totalise les couleurs
	total(Couleur, 0, 0, 0, 0, NB, NJ, NR, NV),
 
	% on calcule la longueur du parcours
	sum(Poids, #=, Len),
 
	% on veut deux bleux
	NB #= 2,
 
	% on ne veut pas de vert
	NV #= 0,
 
	% on calcule pour minimiser le parcours
	labeling([min(Len)], [NB, NJ, NR, NV]),
 
	maplist(affiche, Couleur),
	nl,
	writeln(Len).
 
 
etudie(Etape, R, N) :-
	member((C, N), Etape),
	test(C, R).
 
test(C, R) :-
	C = bleu,  R = [1,0,0,0];
	C = jaune, R = [0,1,0,0];
	C = rouge, R = [0,0,1,0];
	C = vert,  R = [0,0,0,1].
 
total([], B, J, R, V, B, J, R, V).
 
total([[NB, NJ, NR, NV]|T], B1, J1, R1, V1, B, J, R, V) :-
	B2 #= B1 + NB,
	J2 #= J1 + NJ,
	R2 #= R1 + NR,
	V2 #= V1 + NV,
	total(T, B2, J2, R2, V2, B, J, R, V).
 
 
affiche([1,0,0,0]) :-
       write('bleu ').
 
affiche([0,1,0,0]) :-
       write('jaune ').
 
affiche([0,0,1,0]) :-
       write('rouge ').
 
affiche([0,0,0,1]) :-
       write('vert ').

Sorties possibles
On demande 2 bleux

?- parcours.
rouge bleu vert bleu
54
true

On demande deux bleux et pas de vert

?- parcours.
rouge bleu rouge bleu
56

[sarmad354]

merci infiniment Trap D
je vais essayer de généraliser cet algorithme

[Trap D]

merci infiniment Trap D
je vais essayer de généraliser cet algorithme

Attention, je viens de voir qu'il est incorrect.
Je suis en train d'essayer de le corriger, mais l'idée y est !!.

[Trap D]

Bon, je crois que c'est bon.
Le programme est en SWI-Prolog.

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
91
92
93
94
95
96
97
98
:- use_module(library(clpfd)).
 
 
% Bleu -> 0
% Jaune -> 1
% Rouge -> 2
% Vert -> 4
parcours :-
	Etapes= [[(4, 15),(0, 20), (2, 10) ],
		 [(0, 15), (1, 17), (2,12), (4,12) ],
		 [(2, 14), (4, 12)],
		 [(4, 8), (0, 17), (1, 10) ]],
 
	% on poste les contraintes
	contraintes_parcours(Etapes, [NB, NJ, NR, NV], Couleurs, Longueur, Liste),
 
	% on impose les contraintes de couleurs
	% on veut deux bleux
	NB #= 2,
	% mais pas de vert
	NV #= 0,
 
	% on veut 3 rouges
	% NR #= 3,
 
	% on effectue le calcul
	labeling([min(Longueur)], Liste),
 
	format('Couleurs ~w ~n', [Couleurs]),
 
	maplist(affiche, Couleurs),
	nl,
	writeln(Longueur).
 
 
contraintes_parcours(Etapes, [NB, NJ, NR, NV], Couleurs, Longueur, Liste) :-
 
	etudie_etapes(Etapes, Couleurs, Distances, Portes),
 
	% on totalise les couleurs
	total(Couleurs, NB, NJ, NR, NV),
 
	% on calcule la longueur du parcours
	sum(Distances, #=, Longueur),
 
	% on calcule pour minimiser le parcours
	flatten(Portes, Liste).
 
 
% etude de chéque étape,
% on parcours la liste des portes
etudie_etapes([], [], [], []).
 
etudie_etapes([Etape | Etapes],
	      [Couleur | Couleurs],
	      [Distance | Distances],
	      [Porte | Portes]) :-
	etudie_etapes(Etapes, Couleurs, Distances, Portes),
	etudie(Etape, Couleur, Distance, Porte),
	% il n'y a qu'une seule porte à chaque fois
	sum(Porte, #=, 1).
 
% on calcule la couleur et le poids correspondant
etudie([], 0, 0, []).
 
etudie([(C, N) | T], TC1, TN1, [A | TE]) :-
	etudie(T, TC, TN, TE),
	% la porte est choisie ou pas
	A in 0..1,
	TC1 #= A * C + TC,
	TN1 #= A * N + TN.
 
total([], 0, 0, 0, 0).
 
total([C|T], B1, J1, R1, V1) :-
	total(T, B, J, R, V),
	% les couleurs sont présentes ou absentes
	[NB, NJ, NR, NV] ins 0..1,
	% il n'y en a qu'une
	sum([NB, NJ, NR, NV], #=, 1),
	C #= NB * 0  + NJ * 1 +  NR * 2 + NV * 4,
	B1 #= B + NB,
	J1 #= J + NJ,
	R1 #= R + NR,
	V1 #= V + NV.
 
 
affiche(0) :-
       write('bleu ').
 
affiche(1) :-
       write('jaune ').
 
affiche(2) :-
       write('rouge ').
 
affiche(4) :-
       write('vert ').

[olibara]

Dans le cas que tu presente, le graph est asser simple et tster toutes les combinaisons est tout a faisable

Par contre le traitement des contraintes telles que tu les donnes me semble tout a fait impraticable avec du dijkstra dans un contexte généralisé

Car il est possible a tout moment que tu n'ai pas d'autre solution que d'enfreindre une contrainte
Dans ce cas tu est obligé de revenir en arriérre et tu risque de tomber dans une complexité O(n!)

passer par les ellipses rouges au maximum 2 fois ;
passer par les ellipses vertes au maximum 3 fois ;
passer par les ellipses bleues au maximum 2 fois ;
passer par les ellipses jaunes au maximum 2 fois.

[Trap D]

Dans le cas que tu presente, le graph est asser simple et tster toutes les combinaisons est tout a faisable

Par contre le traitement des contraintes telles que tu les donnes me semble tout a fait impraticable avec du dijkstra dans un contexte généralisé

Car il est possible a tout moment que tu n'ai pas d'autre solution que d'enfreindre une contrainte
Dans ce cas tu est obligé de revenir en arriérre et tu risque de tomber dans une complexité O(n!)

Je ne sais pas trop à qui tu t'adresses, mais il est évident que ma méthode ne peut être applicable pour un grand nombre d'étapes et d'ellipses différentes.