Algorithme trop complexe pour moi ?

Version imprimable

15/11/2012, 10h35
siro1

Algorithme trop complexe pour moi ?

Bonjour à tous,

je me suis penché sur un aglo qui me fait me tirer les cheveux ! Bon c'est vrai je ne suis pas expert en algo et j'aurais donc besoin de vos lumières ...

voici le contexte :

Le but est d'automatiser par calcul la composition de réflecteurs dans des rampe d'une certaine longueur.

il existe plusieurs type de réflecteurs les T5 (4) et les T8(5) qui sont de longueur différentes:

Réflecteurs « T8 » :
15w : lg 471mm
18w : lg 640mm
30w : lg 940mm
36w : lg 1240mm
58w : lg 1540mm

Réflecteur « T5 » :
24w : lg 585mm
39w : lg 885mm
54w : lg 1185mm
80w : lg 1485mm

Dans une rampe, nous appelons “ombre” la partie non équipé de réflecteurs (ex : un rampe de 800mm avec un réflecteur de 640mm aura une ombre de 160mm). Il y a donc l’ombre total et l’ombre repartie (c’est à dire l’ombre total / [le nombre de réflecteur +1]).

Les rampes peuvent être en 1 ou plusieurs éléments:

En 1 élément :
- lorsque il y a plusieurs réflecteurs, ils ne doivent pas se chevaucher.
- L’ombre mini doit être de 30mm (pour l’arrivée elec)
- L’ombre repartie maximum devrait être de 100mm (ce n’est pas toujours possible, le but étant de ne pas trop dépassé)
- On ne mélange pas les T8 et les T5.
- Le but est de mettre le moins possible de réflecteurs (et le plus possible identique).

En plusieurs éléments :
- lorsque il y a plusieurs réflecteurs, ils ne doivent pas se chevaucher.
- L’ombre mini doit être de 140 mm par éléments (pièce de raccordement + arrivée elec)
- L’ombre repartie maximum devrait être de 100mm (ce n’est pas toujours possible, le but étant de ne pas trop dépassé)
- On ne mélange pas les T8 et les T5.
- Le but est de mettre le moins possible de réflecteurs (et le plus possible identique).

au final je veux avoir la composition des rampes pour une longueur et catégorie données.

Voici un fichier excel qui illustre le résultat voulu.

Tableau

Un algo est-il possible pour obtenir un tel résultat ?:calim2:

Merci a tous !

Bonjour,

Dans ton cas, il faut "saussionner" ton pb en sous cas plus simples et prendre le temps de traiter les cas de figures possibles.

tu pourrais commencer ainsi :

Code:

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
 
 
Variables :
   Entier :Long_Ramp, nb_reflecteur_24W, nb_reflecteur_39W, nb_reflecteur_54W, nb_reflecteur_80W, ........... ;
   Reel : ombre_tot, ombre_rep;
   Chaine :Type_Ramp;
 
Début
   Afficher "Saisir longueur de la rampe :"; Lire Long_Ramp;
   Afficher "Type de rampe T5 ou T8:"; Lire Type_Ramp;
   // On commence la découpe ...
   SI (Type_Ramp = "T5") ALORS
       // On commence par chercher une solution en 1 partie
        nb_reflecteur_24W = Entier(Long_Ramp/585);
        nb_reflecteur_39W = Entier(Long_Ramp/885);
        nb_reflecteur_54W = Entier(Long_Ramp/1185);
        nb_reflecteur_80W = Entier(Long_Ramp/1485);
 
        ombre_24W = Long_Ramp-nb_reflecteur_24W * 585;
        ombre_39W = Long_Ramp-nb_reflecteur_39W * 885;
        ombre_54W = Long_Ramp-nb_reflecteur_54W * 1185;
        ombre_80W = Long_Ramp-nb_reflecteur_80W * 1485;
        les_ombres = [ombre_24W ,ombre_39W , ombre_54W , ombre_80W ];
        ombre_tot = Min(les_ombres );
        Index_ombre = Index(ombre_tot, les_ombres);
        SELON Index_ombre 
             CAS 0 : Afficher("Il faut ")+nb_reflecteur_24W+Afficher(" reflecteur_24W.");
             CAS 1 : Afficher("Il faut ")+nb_reflecteur_39W+Afficher(" reflecteur_39W.");
             CAS 2 : Afficher("Il faut ")+nb_reflecteur_54W+Afficher(" reflecteur_54W.");
             CAS 3 : Afficher("Il faut ")+nb_reflecteur_80W+Afficher(" reflecteur_80W.");
        FINSELON
 
       // On cherche une solution en 2 parties
        ...........
 
   SINON SI (Type_Ramp = "T8") ALORS
       // Ici tu traites dans le même esprit les rampes T8
   SINON
      Afficher "Type de rampe invalide"
   FINSI
Fin

Il s'agit d'un début d'algo auquel je pense et toutes les règles de gestion ne sont pas implémentées....

Par ailleurs même si l'algo est censé être indépendant du langage, on ne raisonnera pas pareil si derrière tu dois coder avec un langage purement procédural, ou si tu peux faire de l'objet, ou si tu as aussi une Bdd à dispo et auquel cas tu as juste besoin de stocker les solutions puisqu'il y en a que quelques centaine (et que tu les as) et alors tu règles le pb avec une simple petite requête SQL, ou encore si tu utilises un langage logique type prolog.

Donc comme tu le vois plein de solutions sont possibles.

Bon courage

15/11/2012, 12h06
siro1

Merci pour cette réponse rapide, ton algo est bon mais pour une composition mono type, dans mon cas il sera possible d’associer des w39 et w54 par exemple, et même des triplets w39 / w54 / w80 et c'est bien la que ca se complique dans ce cas ton algorithme n'est pas bon.

Est il possible de considérer les différents type comme un tableau

Citation:

Tab(1..4)

pour la catégorie "T5"

Citation:

Tab(1..5)

pour la catégorie "T8"
et de boucler sur toute les combinaison possible tant que les conditions ne sont pas bonne : c'est à dire,
ombre repartie <= 100
ombre totale >= 30

dans ce cas, comment avoir avec un algo toutes les combinaison possible ?

Pour info:
je programme en L4G
pas de bdd à disponible
la longueur de rampe est une donnée
le nombre de partie est une donnée

Bonjour,

Comme je te l'ai dit c'est juste un début d'algo et pour le cas de la décomposition multiple, ce n'est pas que l'algo echoue, c'est seulement que ce n'est pas implémenté...pour que tu cherches un peu ...
Mais bon, c'est trop facile de dire "Il n'y a quà le faire, c'est facile ..."

Donc voici la piste que j'exploiterais si je devais le faire : La division euclidienne avec reste, et surtout pas une recherche de tous les cas.
Code:

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 /* function Decomposition_multi_T5(int:Long_Ramp) :Array reçoit un entier et ressort un tableau de cinq éléments. formaté comme suit : [nb_80W, nb_54W, nb_39W, nb_24W, ombre_residuelle] */ function Decomposition_multi_T5(int:Long_Ramp) :Array { resultat = [0,0,0,0,0]; // un tableau de cinq zéros nb_80W = Entier(int:Long_Ramp/1485); resultat[0] = nb_80W; reste = Long_Ramp-nb_80W*1485; SELON reste // qui est forcément <1485 par la division précédente cas reste > 1185 : // il ne peu y avoir qu'un objet de cette taille puisque reste < 1485 et que 2*1185> 1485 nb_54W = 1; resultat[1] = nb_54W; reste2 = reste - 1185; SELON reste2 cas reste2>885 : //même raisonnement nb_39W = 1; resultat[2] = nb_39W; reste3 = reste2-885; // etc .... FINSELON cas 885 <reste < 1185 : // tu travailles ... cas 585 <reste < 585 : // tu travailles ... FINSELON }
Attention là encore il s'agit du début de l'algo de la fonction de décomposition multi reflecteurs... et c'est une piste possible... mais cela tournera bcp plus vite qu'une recherche systématique de toutes les solution possibles.

Ci dessous voici un exemple que cela donnerait pour Long_Ramp = 5500

resultat = [0,0,0,0,0];
5500/1485 = 3,7 donc on enregistre resultat = [3,0,0,0,0];
reste = 5500-3*1485 = 1045;
885 < reste < 1185 donc
reste = 1045-885 = 160 et on enregistre resultat = [3,0,1,0,0];
reste<585 //c'est l'ombre restante
on enregistre resultat = [3,0,1,0,160]

Conclusion : l'imbrication des divisions euclidiennes avec restes nous donne :
3 réflecteurs de 80W
1 réflecteurs de 39W
ombre = 160.

Conc de la Conc : Je n'ai pas pris en compte les contraintes d'ombre mini, il faut implémenter ces règles dans les SELON ...

Bon courage

15/11/2012, 15h32
siro1

La division euclidienne n'est pas adapté à mon problème, si on reprend ton exemple pour une longueur de 5500 :
le traitement se fera en deux partie et pour:
3 réflecteurs de 80W
1 réflecteurs de 39W
ombre = 160.

on aura donc inévitablement :

2 réflecteurs 80w = 2970mm
et 80w+39w = 2000 (env)

il y a trop de différences et se sera systématiquement comme ça avec la division euclidienne. Le but n'est pas de "remplir" les rampes sur la distance voulu mais d'adapter les longueurs des éléments selon les condition de minimum et maximum.

Je pense que le parcours des combinaisons répondrait bien à mon besoin (si on met de coté l'aspect perf:zoubi:).

Le problème c'est de trouver cette algo ...

Merci Sologne pour tes multiples proposition ! :ccool:

Bonsoir,

je n'accroche pas trop aux solutions itératives car elles sont inélégantes, très gourmandes en nombres de calculs et en mémoire ... mais bon parfois on a pas le choix ... alors tentons de le faire le plus proprement possible.

Du coup cette fois j'intègre ta contrainte d'ombre mini ce paramètre semble important. Et là on commence par un peu de math :

Ton Pb est un Pb d'optimisation sous contrainte qui se traite mathématiquement avec la théorie du multiplicateur de Lagrange.Mais ne sachant pas si tu connais cette théorie, je vais faire sans.(Jette un œil dessus)

Ton Pb peu se modéliser comme suit :

a,b,c,d,L des entiers représentant :

a le nb de 80W de 1485 mm
b le nb de 54W de 1185 mm
c le nb de 39W de 885 mm
d le nb de 24W de 585 mm
L la longueur à couvrir
F(a,b,c,d,L) = L-1485*a-1185*b-885*c-585*d-(a+b+c+d+1)*140

avec comme objectif de minimiser F.

L'idée est la suivante faire tourner 4 boucles POUR ... FINPOUR afin de tester les cas possibles, puis choisir le meilleur (le plus petit).
Attention on va se retrouver avec un algo d'ordre N^4, ce qui est à déconseiller. Donc pour limiter la casse on va déterminer une borne sup la plus faible possible pour la première Boucle.
Code:

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 function F(a,b,c,d,L){ // on implémente la fonction return L-1485*a-1185*b-885*c-585*d-(a+b+c+d+1)*140; } DEBUT // je te laisse les déclarations de variables, la saisie de L, etc (les trucs basiques) ... ombre_residuelle <-- L; SELON L : cas L > 1485 : N_max = Entier(L/1485); POUR a de 0 à N_max par pas de 1 Faire POUR b de 0 à (N_max-1) par pas de 1 Faire POUR c de 0 à (N_max-1) par pas de 1 Faire POUR d de 0 à (N_max-1) par pas de 1 Faire ombre_calculee= F(a,b,c,d,L); SI (ombre_calculee >= 0) ALORS SI (ombre_calculee < ombre_residuelle) ALORS nb_80W <-- a; nb_54W <-- b; nb_39W <-- c; nb_24W <-- d; ombre_residuelle <-- ombre_calculee; FINSI FINSI FINPOUR FINPOUR FINPOUR FINPOUR break; cas 1185< L < 1485 : N_max = Entier(L/1185); // même type de raisonnement avec 3 boucles => tu complètes break; cas 885< L < 1185 : N_max = Entier(L/885); // même type de raisonnement avec 2 boucles => tu complètes break; cas 585< L < 885 : N_max = Entier(L/585); // même type de raisonnement avec 1 boucles => tu complètes break; cas L < 585 : Afficher(L,"est trop petit"); FINSELON Afficher("nb_80W : ",nb_80W)+NouvelleLigne; Afficher("nb_54W : ",nb_54W)+NouvelleLigne; Afficher("nb_39W : ",nb_39W)+NouvelleLigne; Afficher("nb_24W : ",nb_24W)+NouvelleLigne; Afficher("ombre_residuelle : ",ombre_residuelle); FIN
Bon courage pour la suite.

19/11/2012, 11h13
siro1

qu'appelles-tu l'ombre calculée ? l'ombre résiduelle ? pourquoi NBmax-1 dans les boucles suivantes ?
19/11/2012, 13h40
sologne

Bonjour,

ombre_calculée est l'ombre qui est déterminée par la fonction F, qui modélise le problème.

ombre_résiduelle est une variable temporaire qui permet récupérer en fin de traitement la plus petit ombre, tout en respectant les conditions aux limites (implémentées dans la fonction F). On détermine le min au fur et à mesure plutôt que de tout stocker et de le chercher à la fin. C'est plus rapide et moins gourmand en mémoire.

Pour le N_max-1 : le plus simple est de faire tourner l'algo. Si tu vois que cela est trop restrictif, met N_max à la place.

Ou en es-tu de ton côté ? As-tu implémenté un peu de code afin d'avancer ?

Bon courage :-)
19/11/2012, 14h12
siro1

Non pour l'instant j'ai pas de code.

J'essaye de comprendre l'algorithme, comme je te l'ai dis je suis pas un expert en la matière.:aie:

sinon , ombre_calculee= F(a,b,c,d,L);
cette fonction, je ne comprend pas trop ce qu'elle fait ...

:roll: