Algorithme pour un problème d'optimisation

Version imprimable

Voir 40 message(s) de cette discussion en une page

23/10/2019, 10h14
CliffeCSTL

Hop, une nouvelle version avec la remarque de tbc92 et une version récursive du générateur pour prendre en compte autant de type de cadre que l'on veut :

https://onlinegdb.com/rJtIiF6Fr

Algorithme pour un problème d'optimisation

Variante plus rapide de l'algorithme précédent, un peu sommaire:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
NaMax := Lm DIV La; 
FOR Ia:= 1 TO NaMax DO
  BEGIN
    L1:= Lm - (Ia * La); NbMax = L1 DIV Lb; 
    IF (NbMax>0) THEN
      FOR Ib:= 1 TO NbMax DO
        BEGIN
          L2:= L1 - (Ib * Lb); NcMax := L2 DIV Lc; 
          IF (NcMax>0) THEN
            FOR Ic:= 1 TO NcMax DO
              BEGIN
                L3:= L2 - (Ic * Lc); Nd:= L3 DIV Ld;
                IF (Nd>0) THEN
                  BEGIN
                    //  Ltot:= Ia * La; Inc(Ltot, Ib * Lb); Inc(Ltot, Ic * Lc); Inc(Ltot, Id * Ld); 
                    //  IF (Ltot<=Lm) THEN condition toujours vraie donc inutile
                    <Examen des critères>
                  END
              END
        END
  END;

23/10/2019, 14h46
Fixette2000

Vous êtes trop fort les gars

J'ai pas le temps de me concentrer sur une de vos proposition qu'une autre arrive!

Je prend connaissance de tout ça
...et vous remercie pour votre aimable participation à ce problème existentiel qui me taraude depuis quelques jours, en espérant que ça serve aussi à satisfaire votre curiosité;)
23/10/2019, 14h56
tbc92

Les différentes versions sont des variantes très proches les unes des autres d'une même idée.
La variante avec la récursivité est la seule vraiment différente, elle a l'avantage de permettre de traiter autant de tailles de tableaux qu'on veut (et pas seulement 4), mais pour un débutant, le code correspondant est totalement illisible.
La dernière variante Python sans récursivité, ou la version que j'avais proposée, c'est quasiment une traduction en 2 langages différents d'une même logique... lire les 2 codes en parallèle peut aider à les décrypter.
23/10/2019, 15h59
Fixette2000

Royal.

C'est bien ce que je pensais, je vais finir comme Champollion devant la Pierre de Rosette ahaha
23/10/2019, 17h25
Fixette2000

Alors, plusieurs questions:

pour wiwaxia: quel est ce langage?
pour tbc92: le code que tu as proposé est en quel langage?
pour cliffeCSTL: dans ton code, je n'arrive pas à comprendre où est la formule qui permet d'afficher la dimension utilisée.. c'est {}\n ? Pourtant quand
J'essaye de faire apparaître la dimension finale obtenue, c'est à dire la dimension utilisée + 2*e_b je n'y arrive pas...il faut que ce soit sur la même ligne?
23/10/2019, 17h31
tbc92

Message n°19 :

Citation:

Envoyé par tbc92

Le code que j'ai posté est écrit en Windev. C'est un langage plutôt simple. Pour l'utiliser, il faut le compilateur Windev (payant), mais tu peux télécharger une version d'évaluation : ici .
Avec cette version d'évaluation, tu pourras modifier les paramètres , faire tout ce que j'ai fait ... A priori aucune restriction due au fait que c'est une version d'évaluation. Tu pourras très facilement faire un écran où tu saisis les 5 paramètres + un bouton qui lance les différents calculs. Et tu pourras aussi ajouter les contraintes (au maximum x tableau de largeur y)
23/10/2019, 17h32
Fixette2000

ah oui merci, j'avais zappé
23/10/2019, 17h50
CliffeCSTL

Code:

print(2 * e_b)

ou alors si tu veux formater avec du texte, j'utilise la méthode format :

Code:

print("2 * e_b = {}".format(2 * e_b))
23/10/2019, 18h20
Fixette2000

okay...ça me donne la somme des deux bordures.
Mais je ne pige toujours pas comment la "dimension utilisée" (somme des différents cadres utilisés) est calculée dans ton code.

Mais je me suis trompé, pour la dimension finale obtenue il faut intégrer les écarts entre les cadres aussi.

La dimension finale obtenue c'est:
dimension utilisée + ((e_c * nombre de cadres utilisés )-1) + 2* e_b

En fait je ne pige pas ou retrouver la valeur ou la formule de la longueur utilisée qui s'affiche avec la solution.
23/10/2019, 18h28
Fixette2000

ok j'ai pigé la mise en forme dans le principe

Code:

print("Dimension obtenue: 2 * e_b = {}".format(best_solution[1] + 2 * e_b))

Mais y'a t'il une formule qui calcul le nombre de cadres utilisés dans ton code? ce qui me permettrait de trouver le nombre d'écarts entre les cadres et l'inclure dans le calcul de la dimension totale?

Après je vous embête plus promis :)
23/10/2019, 18h45
Fixette2000

Je croyais que la dimension utilisée était liée à {}\n mais je viens de comprendre que \n c'est juste pour sauter une ligne...

Du coup je capte pas ou se fait le calcul longueur utilisée...ou plutôt je cherche dans quelle partie je peux intervenir pour faire calculer le nombre de cadres utilisés...Bref, je rame quoi ahahha
23/10/2019, 20h17
wiwaxia

Citation:

Envoyé par Fixette2000

Alors, plusieurs questions:
pour wiwaxia: quel est ce langage? ...

C'est du Pascal. Cela se lit comme du pseudo-code.
23/10/2019, 20h20
tbc92

Dans le code de CliffeCSTL, celui avec la récursivité, si je ne me trompe pas, c'est cette ligne qui calcule la longueur 'utile' :
return sum(s[idx] * cadre[0] for idx, cadre in enumerate(l_cadre))Il faut la remplacer par :
return sum(s[idx] * (cadre[0]+e_c) for idx, cadre in enumerate(l_cadre))
Dans le code que j'avais posté, message n°11, c'est cette ligne :
score = i1* tb_larg[1] + i2* tb_larg[2] + i3* tb_larg[3] + i4* tb_larg[4]qu'il faut remplacer par
score = i1* tb_larg[1] + i2* tb_larg[2] + i3* tb_larg[3] + i4* tb_larg[4] + (i1+i2+i3+i4)*lg_intercalaire
23/10/2019, 20h23
CliffeCSTL

Je comprends pas ce que tu cherches, les solutions de ton problème sont représentées par un vecteur de dimension le nombre de type de cadre.

Chaque composante représente le nombre de cadre pour chaque type, ex :
une solution s = [0, 1, 0, 12] signifie : 0 cadre du premier type, 1 cadre du deuxième, 0 du troisième et 12 du quatrième.

Ensuite, pour comparer des solutions entre elles afin de garder la meilleure, je calcul la longueur totale utilisée par les cadres avec la fonction eval_s.

=> \n c'est juste pour un retour ligne oui.
23/10/2019, 21h49
Fixette2000

Je cherche en fait à faire afficher la valeur totale de la solution.

si pour un mur de 500cm, j'ai une solution qui arrive à 498cm, j'aimerai le voir tout de suite poir savoir la différence à combler potentiellement.

Et ça passe par (largeur utilisée + (nombre de cadres -1) * e_c + 2* e_b)

et je crois que dans ton code à aucun endroit je ne peut récupérer le nombre de cadres utilisés (donc le nombre d'écarts entre les cadres à rajouter à l'equation)

désolé si c'est pas clair
23/10/2019, 22h29
tbc92

Dans mon code, il y avait à la fin du traitement un tableau best_je_ne_sais_plus_quoi, avec le nombre de tableaux de chaque dimension.
Pour trouver la place occupée, il suffit de faire

Code:

place occupée = best[1] * (70+8) + Best[2]*(60+8) + Best[3]*(50+8) + Best[4]*(40+8)

Dns le code de CliffeCSTL, c'est plus ou mois la même chose.

Mais je le dis et le redis : le code 'Récursif' proposé par CliffeCSTL, il est certainement très bien, mais oublie-le. Il est beaucoup trop compliqué pour un débutant, n'essaie pas de le comprendre. Essaie de comprendre la version précédente proposée par CliffeCSTL, elle est très bien, elle est compréhensible par un débutant, et elle fonctionne parfaitement. Elle a un seul inconvénient : la limitation à 4 tailles de cadres.Mais, c 'est facile d'en faire une variante avec 5 voire 6 tailles de cadres.
24/10/2019, 11h57
Fixette2000

C'est good, j'ai mes réponses.

Merci beaucoup en tout cas, j'ai appris beaucoup de choses grâce à vous, je vais classé ce post comme résolu.
Il y a encore la partie "symétrie" mais chaque chose en son temps, c'est déjà top!

Je me dois d'aider à mon tour une âme perdue dans un forum de mon domaine de compétence.

Changez-rien
25/10/2019, 08h00
CliffeCSTL

La partie avec la symétrie c'est pareil, comme déjà dit, on travaille sur la moitié du mur et on essaye pour chaque solution de rajouter une moitié de cadre :

https://onlinegdb.com/SkQGJGg5S

Une solution est représentée par le même vecteur que précédemment plus l’indice du cadre que l'on choisi pour mettre au milieu.
25/10/2019, 08h29
wiwaxia

Algorithme pour un problème d'optimisation

Il n'est peut-être pas souhaitable de faire intervenir des divisions par 2, alors que l'expression des longueurs en centimètres permet d'utiliser des variables entières, et que dénombrer des moitiés de cadre ne conduit pas à un critère simple.

tbc92 a livré dès le début le bon test (#1):

Citation:

Envoyé par tbc92

... Pour le 3ème cas (disposition symétrique), je pars de cette propriété : les tableaux pourront être disposés de faàons symétrique si on a un nombre pair pour chaque taille, ou au maximum une taille de tableau qui est en nombre impair.
Ce qui se traduit par cette instruction :

Code:

SI modulo(i1,2) +modulo(i2,2)+modulo(i3,2)+modulo(i4,2) <= 1 ALORS

Et rien n'interdit d'exprimer les longueurs en millimètres, si la précision l'exige.

Voir 40 message(s) de cette discussion en une page