Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algorithme pour un problème d'optimisation


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    decorateur
    Inscrit en
    octobre 2019
    Messages
    42
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : decorateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : octobre 2019
    Messages : 42
    Points : 1
    Points
    1
    Par défaut Algorithme pour un problème d'optimisation
    Bonjour,

    je suis tout à fais nul en math, et encore plus en algorithme, mais j'ai un gros besoin.
    Je pense que c'est un algorithme d'optimisation avec contraintes qu'il me faut.
    Etant ignare de ce langage, je cherche un coup de pouce pour me dire comment je dois procéder, dans quel ordre je dois faire les choses, ou au mieux, s'il existe un algorithme tout fait.

    Je vous explique mon problème:

    Je cherche une formule me permettant d'afficher plusieurs solutions selon plusieurs critères en fonction d'une variable principale (largeur de mur) et des variables implicites (nombre de cadres).

    On me donne un mur d'une certaine largeur; je dois y installer une série de cadres photos en utilisant un stock de 4 modèles de cadres différents (Par exemple cadre A 30cm de large, cadre B 40cm de large, cadre C 50cm de large, cadre D 70cm de large).
    Je dois respecter un écart de 8cm entre chaque cadre et au minimum 6cm d'espace entre les 2 cadres d'extrémité et le bord du mur, je peux utiliser plusieurs fois le même modèle de cadre.

    1-je voudrais calculer automatiquement la meilleur combinaison pour remplir au maximum la largeur du mur selon les critères cités au dessus.

    2-je voudrais également trouver la meilleur combinaison pour remplir au maximum le mur, mais en utilisant le minimum de cadres, donc en priorisant les plus grands cadres, tout en recouvrant au maximum le mur, selon les critères cités au dessus. (exemple cadre D

    3-je voudrais aussi calculer la meilleure combinaison qui remplisse au maximum le mur, toujours selon les critères cités au dessus, mais cette fois en ayant une symétrie parfaite dans le calepinage (exemple cadre A, cadre B, cadre C, cadre B, cadre A).

    En fait, j'aimerais pouvoir calculer automatiquement ces 3 solutions, et voir aussi toutes les autres solutions, classées de la plus approchante à la moins approchante de la perfection.

    Les variables sont donc la dimension du mur et le nombre de cadres utilisés (donc nombre d'écarts de 8cm)

    Comment pensez-vous que je doive faire?

    Chaque tentative d'ajouter un cadre dans la combinaison implique un nombre d'écarts de 8cm différents, l'algorithme doit donc calculer automatiquement la somme totale des cadres et écarts au fur et à mesure.

    ça ne me semble pas impossible mais je devine qu'il y a un problème de recalcule constant.
    Pensez-vous qu'il faille avant tout faire un tableau de données avec toutes les solutions possibles (fastidieux) pour que l'algorithme puise dans ces données pour faire le calcul?

    Je vous remercie d'avance pour tout conseil, suggestion qui pourrait me faire avancer.

  2. #2
    Membre actif
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2012
    Messages
    518
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2012
    Messages : 518
    Points : 248
    Points
    248
    Par défaut
    Je te propose de résoudre avec la programmation linéaire :

    1 :

    Données :
    Nom : CodeCogsEqn(6).png
Affichages : 153
Taille : 4,4 Ko


    Variable de décisions :

    Nom : CodeCogsEqn(8).png
Affichages : 137
Taille : 2,6 Ko




    Programme linéaire :
    Nom : CodeCogsEqn(13).png
Affichages : 138
Taille : 873 octets

    Contraintes :
    Nom : CodeCogsEqn(14).png
Affichages : 140
Taille : 1,2 Ko



    2. Tu dois pondérer les deux critères d'optimisations.
    3. Il suffit de résoudre le pb en remplissant la moitié du mur, avec la possibilité de mettre au maximum une fois la moitié d'un cadre.

  3. #3
    Nouveau Candidat au Club
    Homme Profil pro
    decorateur
    Inscrit en
    octobre 2019
    Messages
    42
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : decorateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : octobre 2019
    Messages : 42
    Points : 1
    Points
    1
    Par défaut intéressant
    Bonjour,

    merci pour cette réponse.

    Hier sur un autre forum, 2 contributeurs m'ont plutôt guidés vers du code type VBA;
    Ici vous me proposez une mise équation que j'ai beaucoup plus de mal à interpréter mais qui me semble plus didactique.

    Je ne saurais pour l'instant mettre en parallèle les 2 langages mais je vais me faire mettre dans la peau de Champollion face à la pièce de rosette

    En étudiant les problèmes de sac à dos, j'ai l'impression qu'il faut utiliser 3 méthodes différentes pour mes 3 objectifs:

    -remplir le mur au maximum (sac à dos multi-objectif?/Procédure de séparation et d'évaluation?)

    -utiliser le minimum d'éléments pour remplir au maximum le mur (Algorithme glouton? procédé d'exploration systématique?)

    -obtenir une symétrie parfaite qui rempli au maximum le mur (comme vous dites, travailler sur la moitié de la dimension totale voulue))


    Bon je mélange un peu tout, mais je sens que le choix de la méthode selon les objectifs est crucial pour ne passer à cotés de solutions plus efficaces que je pourrais trouver de façon empirique…

    Je vis étudier tout ça au rythme de ma compréhension, vous avez peut-être exprimé tout cela mais je suis comme un aveugle à qui on essaye d'expliquer une couleur pas facile

    Merci en tout cas

  4. #4
    Membre actif
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2012
    Messages
    518
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2012
    Messages : 518
    Points : 248
    Points
    248
    Par défaut
    La méthode pour résoudre ton problème va dépendre de :
    1. la taille de celui-ci
    2. le temps maximal autorisé pour avoir un résultat

    Ma méthode ne te donnera que la solution exacte et est intéressante pour des instances de taille moyenne.



    Une autre solution consiste à tester toutes les combinaisons possibles, à afficher celles qui sont réalisables, et à retourner la meilleure trouvée.
    Avec un algo de principe ça donne ça :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    Pour toutes les combinaisons possibles parmi l'ensemble des cadres 
        Si la combinaison courante est réalisable alors
            Afficher la solution
            Si la combinaison courante est une meilleure solution  alors
                mémoriser la combinaison comme meilleure solution
    Cette manière de faire est simple et rapide à coder, mais pas du tout adapter sur des grosses instances (Largeur très grande avec des milliers ou millions de cadres)



    Après, pour les grosses instances, tu as aussi des méthodes exactes ou approchées mais plus compliquées à mettre en œuvre, à voir tes besoins...

  5. #5
    Nouveau Candidat au Club
    Homme Profil pro
    decorateur
    Inscrit en
    octobre 2019
    Messages
    42
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : decorateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : octobre 2019
    Messages : 42
    Points : 1
    Points
    1
    Par défaut
    Ok, merci Cliffe CSTL, c'est très clair.

    ...Effectivement il est possible que j'ai des murs très grands, donc beaucoup plus de possibilités à tester.

    Je me dis maintenant qu'il me faudrait peut-être 2 algorithme à utiliser selon la taille du mur.

    J'y vois plus clair maintenant...au travers la brume, mais je devine mon objectif

    Merci encore

  6. #6
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 653
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 653
    Points : 5 800
    Points
    5 800
    Par défaut
    La question des performances et des temps de calcul : Ce n'est pas un problème.

    Dans ton exemple, tu parles de 4 ou 5 cadres sur un mur. Dans la vraie vie, tu auras 10, 20, éventuellement 50 cadres au grand maximum ! Ca reste des petits nombres. Comme disait CliffeCTL, tu vas avoir des problèmes de performance si tu dois placer quelques milliers ou quelques millions de cadre sur un seul et même mur ... configuration purement théorique donc.
    Et si par hasard, le calcul que tu dois lancer doit prendre 3 minutes pour trouver la meilleure réponse à chacune des questions, je pense que ça ne te dérange pas vraiment.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  7. #7
    Nouveau Candidat au Club
    Homme Profil pro
    decorateur
    Inscrit en
    octobre 2019
    Messages
    42
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : decorateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : octobre 2019
    Messages : 42
    Points : 1
    Points
    1
    Par défaut
    ok, et bien tant mieux.
    J'avais une crainte la-dessus. Effectivement je n'aurais pas de murs de plus de 35m à priori

    merci

  8. #8
    Membre habitué
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    210
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 210
    Points : 158
    Points
    158
    Par défaut
    Tant que tu n'aura pas défini(s) ton (ou tes) cahier(s) des charges et qu'ils seront fixés et définitifs tu ne pourra rien faire. Pour qu'il y ait une solution il faut qu'il y ait un problème.
    Savoir pour comprendre et vice versa.

  9. #9
    Nouveau Candidat au Club
    Homme Profil pro
    decorateur
    Inscrit en
    octobre 2019
    Messages
    42
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : decorateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : octobre 2019
    Messages : 42
    Points : 1
    Points
    1
    Par défaut
    Merci Valentin.

    Veux-tu dire ceci?: Tant que je n'ai pas défini mon cahier des charges (suite d'opération recherchées?), que je ne l'ai pas fixé définitivement (en rentrant des valeurs, une équation?), je ne pourrais rien faire.
    Connaissant la valeurs et le nombre de cadres disponibles, connaissant la valeur du mur, puis-je programmer à partir de cela?

    D'après mes recherches, je suis dans un problème d'optimisation combinatoire (du type SAC A DOS en variables entières /c.a.d. avec possiblité de répétition) que je dois résoudre par programmation dynamique, notamment avec une procédure par séparation et évaluation (PSE).
    (Ou bien problème de type RENDU DE MONNAIES avec une monnaie non canonique?)

    Mon besoin (objectif) c'est de savoir combien de chaque cadre je dois utiliser pour remplir au maximum le mur en respectant les contraintes d'écart entre cadres, et au mieux les écarts entre cadre et fin de mur.

    A priori un algorithme de type glouton ne me donnera pas forcément la solution otpimale.


    Je découvre algorithmes et programmation depuis 1 semaine...pas facile de s'y retrouver.

  10. #10
    Nouveau Candidat au Club
    Homme Profil pro
    decorateur
    Inscrit en
    octobre 2019
    Messages
    42
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : decorateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : octobre 2019
    Messages : 42
    Points : 1
    Points
    1
    Par défaut
    CliffeCSTL :

    je retourne la question depuis ce temps, et je recentre.

    que penses-tu de cet algorithme?



    Nom : ALGORITHME PLNE sac a dos correcte.jpg
Affichages : 92
Taille : 89,3 Ko

  11. #11
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 653
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 653
    Points : 5 800
    Points
    5 800
    Par défaut
    Voici un programme qui fait le job. J'ai testé un peu, ça me semble correct.
    - Je considère qu'il y a 4 tailles de tableaux au maximum, On peut adapter facilement pour 5 , voire 6 tailles de tableaux. Si on voulait plus de souplesse sur ce critère, il faudrait organiser le programmme très différemment.
    - Je ne traite pas le 1er cas que tu proposes. Ce 1er cas fait complètement doublon avec le 2ème cas.
    - 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 : Sélectionner tout - Visualiser dans une fenêtre à part
    SI modulo(i1,2) +modulo(i2,2)+modulo(i3,2)+modulo(i4,2) <= 1 ALORS
    Le code complet :
    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
     
    tb_larg est un tableau de 4 entiers
    lgtot est un entier
    lg_intercalaire est un entier = 8
    tab_Nbtableaux est un tableau de 4 entiers
    tab_Best_scenario est un tableau de 4 entiers 
    nScore_best_scenario est un entier 
    ntableaux_best_scenario est un entier 
     
     
    tab_Best_scenario_sym est un tableau de 4 entiers 
    nScore_best_scenario_sym  est un entier 
    score est un entier 
     
     
    tab_Nmax est un tableau de 4 entiers
     
    i1,i2,i3,i4 est un entier 
     
    lgtot = 1100    // 11 mètres =1100 cm.
    tb_larg = [90, 75, 60, 50 ]    // Je mets les largeurs des tableaux en ordre décroissant, pour que le programme soit plus rapide.
     
    tab_Nmax[1] = (lgtot - lg_intercalaire) / (tb_larg[1] + lg_intercalaire)  // Si je mets uniquement des tableaux de type 1, je peux en mettre au max combien ?
    POUR i1 = 0 _A_ tab_Nmax[1]
    	// je fais une hypothèse ; je mets i1 tableau de type 1.
    	tab_Nmax[2] = (lgtot - lg_intercalaire - i1 * (tb_larg[1] + lg_intercalaire) ) / (tb_larg[2] + lg_intercalaire)
    	// Du coup, avec i1 tableaux de type 1, je peux mettre au max  tab_Nmax[2]  de type 2
    	POUR i2 = 0 _A_ tab_Nmax[2]
    		// je fais une hypothèse ; je mets i1 tableau de type 1 et i2 tableaux de type 2.
    		tab_Nmax[3] = (lgtot - lg_intercalaire - i1 * (tb_larg[1] + lg_intercalaire) - i2 * (tb_larg[2] + lg_intercalaire)  ) / (tb_larg[3] + lg_intercalaire)
    		// Du coup, avec i1 tableaux de type 1,et i2 tableaux de type 2,  je peux mettre au max  tab_Nmax[3]  de type 3
    		POUR i3 = 0 _A_ tab_Nmax[3]
    			tab_Nmax[4] = (lgtot - lg_intercalaire - i1 * (tb_larg[1] + lg_intercalaire) - i2 * (tb_larg[2] + lg_intercalaire) - i3 * (tb_larg[3] + lg_intercalaire)  ) / (tb_larg[4] + lg_intercalaire)
    			POUR i4 = 	tab_Nmax[4]-1 A tab_Nmax[4]
    				// La configuration i1, i2, i3, i4 convient , je peux placer  (i1, i2, i3, i4 ) tableaux sur mon mur.		
    				// Cette configuration est-elle mieux que la meilleure configuration déjà rencontrée.
    				score = i1* tb_larg[1] + i2* tb_larg[2] + i3* tb_larg[3] + i4* tb_larg[4] 					
    				SI score > nScore_best_scenario _OU_ ( score = nScore_best_scenario _ET_ i1+i2+i3+i4 < ntableaux_best_scenario ) ALORS 
    					nScore_best_scenario = score 
                                            ntableaux_best_scenario = i1+i2+i3+i4
    					tab_Best_scenario[1] = i1
    					tab_Best_scenario[2] = i2
    					tab_Best_scenario[3] = i3
    					tab_Best_scenario[4] = i4							
    				FIN
    				// Recherche du meilleur résultat, avec une répartition symétrique 
    				SI modulo(i1,2) +modulo(i2,2)+modulo(i3,2)+modulo(i4,2) <= 1 ALORS
    					score = i1* tb_larg[1] + i2* tb_larg[2] + i3* tb_larg[3] + i4* tb_larg[4] 					
    					SI score > nScore_best_scenario_sym ALORS 
    						nScore_best_scenario_sym = score 
    						tab_Best_scenario_sym[1] = i1
    						tab_Best_scenario_sym[2] = i2
    						tab_Best_scenario_sym[3] = i3
    						tab_Best_scenario_sym[4] = i4							
    					FIN
    				FIN
    			FIN
    		FIN
    	FIN
    FIN
     
    Info ( " Meilleur scénario remplissage ",tab_Best_scenario[1]  , tab_Best_scenario[2] , tab_Best_scenario[3] , tab_Best_scenario[4]  )
    Info ( " Meilleur scénario remplissage + symétrie ",tab_Best_scenario_sym[1]  , tab_Best_scenario_sym [2] , tab_Best_scenario_sym[3] , tab_Best_scenario_sym[4]  )
    Une fois qu'on connait le nombre de tableaux pour chaque dimension, la disposition elle-même peut être quelconque.

    Le programme affiche les 2 réponses en quelques centièmes de seconde.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  12. #12
    Membre habitué
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    210
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 210
    Points : 158
    Points
    158
    Par défaut
    Citation Envoyé par Fixette2000 Voir le message
    Merci Valentin.

    Veux-tu dire ceci?: Tant que je n'ai pas défini mon cahier des charges (suite d'opération recherchées?), que je ne l'ai pas fixé définitivement (en rentrant des valeurs, une équation?), je ne pourrais rien faire.
    Connaissant la valeurs et le nombre de cadres disponibles, connaissant la valeur du mur, puis-je programmer à partir de cela?

    D'après mes recherches, je suis dans un problème d'optimisation combinatoire (du type SAC A DOS en variables entières /c.a.d. avec possiblité de répétition) que je dois résoudre par programmation dynamique, notamment avec une procédure par séparation et évaluation (PSE).
    (Ou bien problème de type RENDU DE MONNAIES avec une monnaie non canonique?)

    Mon besoin (objectif) c'est de savoir combien de chaque cadre je dois utiliser pour remplir au maximum le mur en respectant les contraintes d'écart entre cadres, et au mieux les écarts entre cadre et fin de mur.

    A priori un algorithme de type glouton ne me donnera pas forcément la solution otpimale.


    Je découvre algorithmes et programmation depuis 1 semaine...pas facile de s'y retrouver.
    Dans ton message initial tu veux trois options, or, une option => un algo; je doute qu'avec un seul algo tu ai les trois options, traite donc les problèmes en options distinctes, tu verra après si tu peux les regrouper.
    Savoir pour comprendre et vice versa.

  13. #13
    Nouveau Candidat au Club
    Homme Profil pro
    decorateur
    Inscrit en
    octobre 2019
    Messages
    42
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : decorateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : octobre 2019
    Messages : 42
    Points : 1
    Points
    1
    Par défaut
    Merci pour ta participation tbc92

    [QUOTE=tbc92;11187706]
    - Je ne traite pas le 1er cas que tu proposes. Ce 1er cas fait complètement doublon avec le 2ème cas. QUOTE]

    Alors justement, il semble que non.
    Par exemple il est possible que 10 cadres de petites tailles remplissent mieux l'espace que 5 cadres de grande tailles.
    C'est l'inconvénient de l'algorithme de type glouton, qui ne donne pas obligatoirement la solution optimale.
    Dans le système de rendu de monnaie par exemple, on peut partir de la plus grande pièce, pas dans mon cas.

    Pour le reste, je vais me pencher dessus et traduire comme je peux
    Merci

  14. #14
    Nouveau Candidat au Club
    Homme Profil pro
    decorateur
    Inscrit en
    octobre 2019
    Messages
    42
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : decorateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : octobre 2019
    Messages : 42
    Points : 1
    Points
    1
    Par défaut
    Citation Envoyé par valentin03 Voir le message
    Dans ton message initial tu veux trois options, or, une option => un algo; je doute qu'avec un seul algo tu ai les trois options, traite donc les problèmes en options distinctes, tu verra après si tu peux les regrouper.
    Effectivement. Il faudrait une combinaison d'algorithmes.

    J'ai revu mon énoncé dans ce sens:


    J'ai un stock de cadres photos de 4 largeurs différentes*:
    Cadre A de largeur 30cm (vA) au nombre illimité ou limité (nA)
    Cadre B de largeur 40cm (vB) au nombre illimité ou limité (nB)
    Cadre C de largeur 50cm (vC) au nombre illimité ou limité (nC)
    Cadre D de largeur 70cm (vD) au nombre illimité ou limité (nD)
    J'ai un mur (m) de largeur connue (vm)

    Je cherche à obtenir la meilleure combinaison (et donc la quantité de chaque type de cadres nécessaire) pour remplir au maximum le mur
    sachant que*:
    -on peut choisir plusieurs fois ou aucune fois chaque cadre.
    -vm est supérieur ou égale à 1 vA
    -vA, vB, vC, vD sont tous supérieur à 0

    selon plusieurs cas*:

    Cas 1*: J'ai un stock illimité de cadres
    Cas 2*: j'ai un stock limité de chaque type de cadres (nA=12 nB=12 nC=12 nD=12)
    Cas3*: je veux utiliser un maximum des grands cadres dans la combinaison (utiliser en priorité D puis C puis B puis A / par exemple D+D+C +B+A)
    Cas 4*: je veux avoir un calepinage de composition parfaitement symétrique (par exemple A + B + C + B +A)

    Question programmation, je souhaiterais bien sur trouver la bonne formulation pour combiner tout ça (en langage C si possible) pour voir s'afficher les 4 solutions de la plus approchante à la moins approchante de la dimension idéale (vm)
    ...mais déjà résoudre chaque cas serait un exploit pour moi.

  15. #15
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 653
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 653
    Points : 5 800
    Points
    5 800
    Par défaut
    J'avais interprété le premier message de la façon suivante :
    - Cas n°1 : la somme des largeurs des tableaux doit être la plus grande possible.
    - Cas n°2 : la somme des largeurs des tableaux doit être la plus grande possible, et si plusieurs solutions sont ex-aequo, on les départage en prenant celle qui a le moins de tableaux.

    C'est pour ça que je disais que les 2 cas étaient similaires. Le départage par le nombre de tableaux ne se fait qu'en cas d'ex-aequo.

    Dans ta nouvelle formulation, il y a des ambiguités. Tu mets sur un même plan 2 notions qui sont très différentes :
    Cas 1*: J'ai un stock illimité de cadres
    Cas 2*: j'ai un stock limité de chaque type de cadres (nA=12 nB=12 nC=12 nD=12)
    Cas3*: je veux utiliser un maximum des grands cadres dans la combinaison (utiliser en priorité D puis C puis B puis A / par exemple D+D+C +B+A)
    Cas 4*: je veux avoir un calepinage de composition parfaitement symétrique (par exemple A + B + C + B +A)
    Les 2 lignes Cas 1 et Cas 2 décrivent les contraintes.
    Alors que les lignes Cas 3 et Cas 4 définissent l'objectif.

    Et encore, spécialement dans le cas 3, l'objectif est mal défini (il était mieux défini dans le premier message). Par exemple (faisons l'impasse sur les 8cm de part et d'autre de chaque tableau), avec des tableaux de 70, 50, 40, 30cm, sur un mur de 300cm, dans le cas 3, c'est quoi la solution idéale ?
    Mettre 4 tableaux de 70cm, ou mettre 3 tableaux de 70cm, un de 50 et un de 40 ?
    Dans la 1ère proposition, on a mis 4 tableaux de 70cm, contre seulement 3 dans la 2ème proposition, donc ça correspond mieux à ce que tu as écrit. Et pourtant, je suis à peu près sûr que tu préfères la proposition n°2.

    Idem, toujours dans le cas 3, avec nos tableaux de 70 50 40 et 30cm, et un mur d'1,50mètre, tu préfères 70+50+30, ou 50+50+50 ?

    Dans le code que j'ai proposé, tu auras 50+50+50 et non 7050+30. Pour inverser, il faut remplacer les symboles > par >=
    Et c'est comme ça, parce que les longueurs sont en ordre décroissant dans le tableau tb_larg.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  16. #16
    Nouveau Candidat au Club
    Homme Profil pro
    decorateur
    Inscrit en
    octobre 2019
    Messages
    42
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : decorateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : octobre 2019
    Messages : 42
    Points : 1
    Points
    1
    Par défaut
    tbc92

    Tes questions sont pertinentes.
    Dns un idéal parfait, supprimant les notions de bordures de 8cm etc., pour un mur de 210cm la solution est 70+70+70 et est proposée dans les 3 algorithmes

    "Par exemple (faisons l'impasse sur les 8cm de part et d'autre de chaque tableau), avec des tableaux de 70, 50, 40, 30cm, sur un mur de 300cm, dans le cas 3, c'est quoi la solution idéale ?
    Mettre 4 tableaux de 70cm, ou mettre 3 tableaux de 70cm, un de 50 et un de 40 ?
    Dans la 1ère proposition, on a mis 4 tableaux de 70cm, contre seulement 3 dans la 2ème proposition, donc ça correspond mieux à ce que tu as écrit. Et pourtant, je suis à peu près sûr que tu préfères la proposition n°2.

    Idem, toujours dans le cas 3, avec nos tableaux de 70 50 40 et 30cm, et un mur d'1,50mètre, tu préfères 70+50+30, ou 50+50+50 ?"


    Effectivement c'est subtile...
    Pour un mur de 300cm, l'algorithme du Cas 1 et Cas 2 devrait normalement trouver 3 tableaux de 70cm + 1 tableau de 50cm + 1 tableau de 40cm, mais c'est aussi la réponse que j'attend en Cas 3 si c'est la solution la plus approchante. Mais entre 2 solutions de même résultat, elle devra choisir celle qui comporte le plus de grands cadres (pour un même résultat, je préfère qu'il n'y ai qu'un cadre de 70cm que pas du tout de cadre de 70cm).

    dans le cas 3, avec nos tableaux de 70 50 40 et 30cm, et un mur d'1,50mètre, tu préfères 70+50+30, ou 50+50+50 ?

    J'attend du logarithme du Cas 3 qu'il me donne 70+50+30.
    Considérant que le logarithme du Cas4 est là pour me donner 50+50+50.

    Et pour répondre au mieux, je dirais que:
    Dans le Cas 1 et 2 j'espère y trouver la solution la plus proche de la valeur du mur.
    Dans le cas 3, j'espère y trouver la solution moins otpimale que Cas 1 et 2 mais qui utilise le maximum de grands cadres
    Dans le cas 4 j'espère trouver la solution moins otpimale que les 2 premières mais proposant une symétrie pour compenser le manque de remplissage

    C'est dans ces choix que je ne peux pas me faire remplacer par une machine.

  17. #17
    Nouveau Candidat au Club
    Homme Profil pro
    decorateur
    Inscrit en
    octobre 2019
    Messages
    42
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : decorateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : octobre 2019
    Messages : 42
    Points : 1
    Points
    1
    Par défaut
    tbc92

    par ailleurs, je n'arrive pas a tester ton code dans les quelques logiciels que j'ai (LARP, algobox, Dev-C+), mais ça c'est lié à mon ignorance dans le domaine...

  18. #18
    Nouveau Candidat au Club
    Homme Profil pro
    decorateur
    Inscrit en
    octobre 2019
    Messages
    42
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : decorateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : octobre 2019
    Messages : 42
    Points : 1
    Points
    1
    Par défaut
    Suite à cette discussion, je reformule plus précisément mon problème, en vu de le programmer ou le faire programmer.

    Toute bonne âme pour le vérifier, corriger, ou y répondre est la bienvenue.



    Ennoncé du problème:


    J'ai un stock de cadres photos de 4 largeurs différentes et je peux en racheter si besoin;
    (ICI considérant que j'ai un stock illimité de cadres)

    Cadre A de largeur 30cm (vA) au nombre illimité (n 8) ou limité (nA)*
    Cadre B de largeur 40cm (vB) au nombre illimité (n 8) ou limité (nB)*
    Cadre C de largeur 50cm (vC) au nombre illimité (n 8) ou limité (nC)*
    Cadre D de largeur 70cm (vD) au nombre illimité (n 8) ou limité (nD)*
    J'ai un mur (m) de largeur connue (vm)

    Je cherche à obtenir la meilleure combinaison (et donc la quantité de chaque type de cadres nécessaire) pour remplir au maximum le mur
    sachant que:
    -on peut choisir plusieurs fois ou aucune fois chaque cadre.
    -vm est supérieur ou égale à 1 vA
    -vA, vB, vC, vD sont tous supérieur à 0

    selon plusieurs cas:

    Cas 1: J'ai un stock illimité de cadres et je cherche (dans l'ordre des opérations) la solution qui remplisse le plus le mur, puis qui utilise le moins de cadres.

    (*Cas 2: j'ai un stock limité de chaque type de cadres (par exemple nA=12 nB=12 nC=12 nD=12) et je cherche (dans l'ordre des opérations) la solution qui remplisse le plus le mur, puis qui utilise le moins de cadres. )

    Cas3: je veux utiliser en priorité les plus grands cadres (en dernier lieu les plus petits cadres, par exemple A+A+A+A+C+C+C+BB+A) quitte à accepter une solution de 10% moins optimale que la solution du cas 1 (ou*cas2)
    =(algorithme glouton/division euclydienne)

    Cas 4: je veux un calepinage de composition parfaitement symétrique (par exemple A + B + C + B +A
    ou encore A+B+C+D+D+C+B+A)


    Question programmation, je souhaiterais combiner ces 3 ou 4 algorithmes pour voir s'afficher dans l'ordre:

    -La combinaison la plus optimale, c'est à dire la plus approchante de la valeur (vm) du mur
    -La combinaison la plus optimale, à condition qu'elle utilise le maximum de grands cadres
    -La combinaison la plus optimale, à condition qu'elle permette une symétrie dans son agencement, en utilisant si possible les plus grands cadres en priorité

  19. #19
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 653
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 653
    Points : 5 800
    Points
    5 800
    Par défaut
    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)

    Eventuellement, je peux essayer de le traduire en Python, mais je ne connais que les bases, je ne suis même pas sûr de savoir le faire.

    Et je me répète : tes cas 1 et 2 sont similaires :
    -La combinaison la plus optimale, c'est à dire la plus approchante de la valeur (vm) du mur
    -La combinaison la plus optimale, à condition qu'elle utilise le maximum de grands cadres
    Dans les 2 cas, la somme des largeurs des tableaux doit être la plus grande possible.
    Dans le 1er cas, en cas d'ex-aequo, on choisit une solution comment ? au hasard ? tu nous laisses libre de choisir. Tu ne donnes de règle pour départager les ex-aequo que dans le cas 2.
    Et comme je n'aime pas choisir au hasard (c'est compliqué à programmer), dans le 1er cas, en cas d'ex-aequo, je choisis en appliquant un certain critère, celui que tu donnes pour le cas n°2.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  20. #20
    Nouveau Candidat au Club
    Homme Profil pro
    decorateur
    Inscrit en
    octobre 2019
    Messages
    42
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : decorateur
    Secteur : Arts - Culture

    Informations forums :
    Inscription : octobre 2019
    Messages : 42
    Points : 1
    Points
    1
    Par défaut
    Merci l'ami mais ne t'embêtes pas, je préfère déjà avoir le raisonnement, ce qui en découlera me dira comment faire la chose

    Je me corrige plusieurs fois sur ce pot: Oui je comprend ton raisonnement, et je précise le mien:
    (j'ai changé l'énoncé mais restons sur 3 cas différents, une solution optimale, une solution optimale priorité aux grands cadres, une solution optimale donnant une symétrie)

    Comme il est possible par principe qu'une seule solution optimale existe (celle qui m'intéresse en priorité), et qu'elle n'utilise pas de grands cadres, le cas1 et cas2 sont bien indépendants, même si le cas2 peut venir suplanter le cas1.
    Il est possible pour différentes raison que je préfère choisir une solution au plus proche complètement anarchique, j'aimerais donc voir cette solution proposée si elle diffère de la solution au Cas2

    l'ordre des opérations devrait être ainsi:

    Je rajoute une inconnue=LE RESULTAT=Solution choisie pour son rapprochement de la valeur du mur, puis pour son utilisation maximale de grands cadres, puis pour la symétrie potentielle qu'elle permet, tout ça par comparaison des solutions Cas1, Cas2 et Cas 3:

    Cas 1:Chercher la combinaison la plus proche de la valeur du mur en piochant au hasard dans les cadres=comparer toutes les solutions et sélectionner la plus proche de vm + afficher le détail de la combinaison
    Cas 2:Chercher la combinaison la plus proche de la valeur du mur en piochant en priorité dans les grands cadres=comparer toutes les solutions et sélectionner la plus proche de vm + afficher le détail de la combinaison (algorithme glouton)
    Cas 3: Chercher la combinaison la plus proche de la valeur du mur qui permet une symétrie=comparer toutes les solutions et sélectionner la plus proche de vm + afficher le détail de la combinaison
    ENSUITE
    Comparer les 3 solutions + afficher la Solution choisie=
    Si Cas2<Cas1, afficher Cas1 comme Solution choisie
    Si cas 2=Cas1, afficher en priorité Cas2 comme Solution choisie
    Si cas 3=Cas1, afficher en priorité Cas3 comme Solution choisie
    Si cas 3 utilise autant de grands cadres que Cas2, afficher Cas3 en priorité comme Solution à Cas2

    Je le concède, ça fait des boucles dans tous les sens si on veut un truc parfait, donc on oublie ça...

    Mais voilà, à moins que je bug (c'est fort possible) la notion de "priorité aux grands cadres" engendre un phénomène d'algorithme "glouton" car le choix d'au moins 1 grand cadre exclu comme solution toutes les solutions qui n'utilisent pas de grand cadre. D'où le fait que la sélection entre ces 3 solutions indépendante doit se faire par un choix humain suivant un mix de justesse (valeur au plus proche du mur), de simplicité (moins de cadres à accrocher= plus simple) et esthétique (acceptation de non remplissage pour avoir une installation plus homogène)

    en tout cas merci pour ta contribution ça m'aide à décortiquer le problème

+ Répondre à la discussion
Cette discussion est résolue.
Page 1 sur 4 1234 DernièreDernière

Discussions similaires

  1. Trouver un algorithme pour mon problème
    Par identifiant_bidon dans le forum Langage
    Réponses: 4
    Dernier message: 28/05/2011, 01h53
  2. Algorithme le plus efficace pour ce problème
    Par george369 dans le forum C++
    Réponses: 2
    Dernier message: 08/11/2009, 16h47
  3. définition algorithme récursif et problème d'optimisation
    Par logo98 dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 10/06/2009, 17h07
  4. problème d'algorithme pour trouver les circuit d'un graphe
    Par marc_dd dans le forum Algorithmes et structures de données
    Réponses: 11
    Dernier message: 21/08/2006, 17h36
  5. Recherche de pistes pour un problème d'optimisation
    Par TiKeuj dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 15/08/2005, 16h50

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo