« le plus court chemin » sous contraintes

**sarmad354** · 07/02/2010, 18h41

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** · 08/02/2010, 09h43

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** · 15/02/2010, 21h17

bonjour
Merci ToTo13 pour l'idée

**Trap D** · 16/02/2010, 18h39

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** · 16/02/2010, 22h13

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

**Trap D** · 17/02/2010, 00h16

Envoyé par sarmad354

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** · 17/02/2010, 08h52

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** · 17/02/2010, 20h32

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** · 17/02/2010, 21h50

Envoyé par 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!)

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.

**olibara** · 17/02/2010, 22h12

Salut Trap_D

Je m'adresse à l'intéressé évidement : sarmad354 , il est le seul a pouvoir evaluer le domaine de pertinence de son traitement

Je n'ai honetement pas etudié ton algorithme mais je voulais aussi faire remarquer que la resolution de ce parcours avec les contraintes énoncées s'écartait a mon avis asser fort d'un Dijkstra classique

Mais j'avoue aussi que c'était ma perception intuitive

en y reflechissant bien je n'en suis plus si sur ..

Si l'on applique diijkstra en remplacant le poids d'un noeud par le nombre de liberté par rapport au contraintes ca pourait peut etre le faire mais je n'ai pas joué a essayer

**sarmad354** · 20/02/2010, 00h30

merci Trap_D , olibara et ToTo13
à titre d'information
le nombre des ellipses peut dépasser 100 types (couleur)
le nombres des ensemble peut aussi dépasser 10

Envoyé par olibara

Salut Trap_D
Si l'on applique diijkstra en remplaçant le poids d'un nœud par le nombre de liberté par rapport au contraintes ca pourrait peut être le faire mais je n'ai pas joué a essayer

plus d'explication SVP

et merci pour tous le monde

**olibara** · 20/02/2010, 09h15

Salut

Le principe de Dijkstra en gros c'est que sur chaque noeud tu inspecte le poids du parcours pour atteindre les noeud adjacent

Le poids du noeud adjacent sera le poids cumulé du noeud courrant plus le poids pour l'atteindre

Ces poids sont stockés dans une file d'attente et a chaque itération on prends dans la file le noeud du poids le plus faible (dont on a conservé le parent) qui disparait de la liste et que l'on ne va plus retraverser

Quand on arrive a destination on refait le parcours a l'envers et l'on obtient le meilleur parcours selon la contrainte d'evaluation de poids

Dans ton cas j'entrevois d'evaluer le poids selon le nombre de contraintes "consommées" pour chaque type de noeud
Si une limite est dépassée le poids devient infini

**Trap D** · 20/02/2010, 13h21

Envoyé par sarmad354

à titre d'information
le nombre des ellipses peut dépasser 100 types (couleur)
le nombres des ensemble peut aussi dépasser 10

Alors tu oublies ma méthode hélas

**sarmad354** · 20/02/2010, 13h55

Envoyé par olibara

Dans ton cas j'entrevois d'evaluer le poids selon le nombre de contraintes "consommées" pour chaque type de noeud
Si une limite est dépassée le poids devient infini

"Si une limite est dépassée le poids devient infini"
est ce que vous parlez du poids du nœud visité

**olibara** · 20/02/2010, 14h31

Je ne me suis pas amusé a faire l'exercice
Mais je dirais que si l'on inspecte un noeud qui va enfreindre une contrainte on ne le met pas dans la file d'attente et son poids devient infini via le parent actuel

Pour le reste c'est un exercice Dijkstra a mettre en musique, a toi d'essayer

**sarmad354** · 22/02/2010, 23h19

Envoyé par olibara

Je ne me suis pas amusé a faire l'exercice
Mais je dirais que si l'on inspecte un noeud qui va enfreindre une contrainte on ne le met pas dans la file d'attente et son poids devient infini via le parent actuel

Pour le reste c'est un exercice Dijkstra a mettre en musique, a toi d'essayer

je pense que ce truc est valable si la contrainte est de passer par la même couleur une seule fois
mais pour plus???????

**olibara** · 23/02/2010, 08h05

Envoyé par sarmad354

je pense que ce truc est valable si la contrainte est de passer par la même couleur une seule fois
mais pour plus???????

Ben non pourquoi ?
Si tu a un compteur de poids par couleur et par noeud et une methode d'aggregation qui evalue l'indice de liberté, je ne vois pas encore ce qui peut bloquer ?
Mais c'est vrai que cent compteurs par noeud ca peut faire un peu lourd
C'est en plus toi qui proposait Dijkstra ... Tu a déja fait des parcours de graph avec Dijkstra ?

Mais j'espere avoir bien compris qu'on ne peut passer qu'une seule fois par le meme noeud !!

« le plus court chemin » sous contraintes

Algorithmes et structures de données

Discussions similaires

Partager

Partager