Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 13 sur 13
  1. #1
    Invité de passage
    Inscrit en
    octobre 2008
    Messages
    11
    Détails du profil
    Informations forums :
    Inscription : octobre 2008
    Messages : 11
    Points : 3
    Points
    3

    Par défaut Algo de tri: Bin Packing 1D (Sac à dos)

    Bonjour,
    étant débutant en programmation, je fais actuellement un programme pour le problème du sac à dos 1D, également connu sous le nom de Bin Packing 1D, avec lequel j'ai un problème ...

    Ce programme consiste a trier des valeurs (de n'importe quel type) de façon à avoir un gain de place ou de matière sur le principe du Bin Packing 1D.

    Exemple:
    Je dispose de données informatiques de différentes tailles que je veux mettre sur CD, j'essai donc d'optimiser la place afin d'utiliser le moins de CD possible:

    Données de 500mo, 400mo , 300mo et 100mo.
    Place sur CD 700mo.

    Il est donc logique de placer 400 et 300 ensemble pour remplir un CD et 500 et 100 ensemble pour le second.
    Dans ce cas j'utilise 2 cd, pour les autres solutions au moins 3.


    Voir également http://fr.wikipedia.org/wiki/Probl%C...de_bin_packing
    et http://fr.wikipedia.org/wiki/Probl%C...sac_%C3%A0_dos*.

    Dans mon cas, je créé ce programme pour optimiser la découpe de barre (comme en menuiserie).

    J'ai des barres standard de 2500mm et j'aimerai les découper en barres de différentes longueurs (exemple 1000, 1345, 537 ,886... dans des quantités plus importantes (>1000)) en utilisant le moins de barres standard possible.

    J'utilise donc la méthode Deacrising First Fit (qui consiste a trier les longueurs dans l'ordre décroissant puis de les ranger au fur a mesure dans la 1ere barre ou il y a de la place).

    En reprenant l'exemple du CD.

    Dans l'ordre décroissant j'ai 500,400,300,100

    CD1 je place 500.
    400 ne rentre plus de CD1 (400+500>700), je créé donc un CD2 pour le placer dedans.
    300 ne rentre pas dans CD1, 300 rentre dans CD2. On rajoute 300 au CD2.
    100 rentre dans CD1, on le rajoute au CD1.

    J'utilise également la méthode du Deacrising Best Fit qui est plus précise, mais je n'ai pas de réèl intérêt à prendre ce dernier car mon programme est utilisé pour des grandes séries de barres (plus de 1000 fois la même valeur).
    Je trouve donc le même résultat qu'en Next Fit mais en un temps beaucoup plus important.

    Mon problème
    Mon problème est que je ne trouve pas , dans de rare cas, une solution suffisament proche de l'optimale.

    Exemple: j'ai des barres standard de 2500, j'aimerai 10 barres de 1000 et 20 de 700.

    L'optimale est d'avoir 10 barres standard de 2500 qu'on découpe en 1000+700+700 = 2400.

    Mais en Decreasing First Fit ou Next Fit je me retrouve avec 5 barres standard découpé en 1000+1000=2000 et 6 barres standard en 700+700+700 = 2100 et 1 barre standard en 700+700=1400.

    Soit un surplus de 20% (12 barres standard au lieu de 10).

    Je sais que ma méthode est heuristique (permet de trouver rapidement un résultat approché de l'optimal), mais je sais également qu'il est possible d'avoir un tri plus approché dans le cas ci dessus, seulement je ne sais pas comment faire.

    Je cherche donc a améliorer ma méthode de tri, mais je ne sais pas comment m'y prendre.
    Pouvez vous m'aider?

    Merci

  2. #2
    Membre du Club
    Profil pro
    Inscrit en
    juillet 2005
    Messages
    55
    Détails du profil
    Informations personnelles :
    Âge : 30
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations forums :
    Inscription : juillet 2005
    Messages : 55
    Points : 61
    Points
    61

    Par défaut

    Bonjour,

    tout d'abord je tiens a preciser que le probleme de bin packing 1D n'est pas le meme probleme que celui du sac a dos 1D (meme s'il existe un lien forte entre ces deux problemes)!!!
    En effet, dans ton exemple, le bin packing 1D consiste a determiner le nombre minimum de CD qui puisse contenir tous tes fichiers alors que le sac a dos 1D consiste a determiner le "maximum" qui puisse rentrer dans UN CD, maximum pouvant etre le nombre de fichier ou bien la quantite occupe sur le CD ou tout autre critere d'optimisation...
    C'est pas du tout le meme probleme !!!!
    Si je suis ton exemple de CD, le probleme qui t'interesse c'est le bin packing 1D et non le probleme du sac a dos (tu cherches le nombre minimum de CD pouvant contenir tes fichiers et pas combien tu peux en rentrer sur un CD).

    De plus, il faut noter que resoudre le probleme bin packing 1D ne revient pas a resoudre le probleme sac a dos sur chaque CD. Admettons que tu applique un sac a dos sur le 1er CD (donc tu remplit optimalement ton premier CD), jusque la pas de probleme. Ensuite, si tu applique un sac a dos sur le 2eme CD et 3eme CD, tu n'es pas certain que la repartition sur ces 3CD est optimale (en d'autres mots, il se peut qu'il y ait une solution en 2CD) alors que tu as resolu optimalement chaque CD.

    Ensuite en ce qui concerne les heuristiques que tu as essaye, il est clair qu'elles ont l'avantage de trouver une solution rapidement mais suivant les tailles des fichiers, elle peuvent etre tres loin de l'optimal. Ces heuristiques datent des annees 70 si je ne me trompe pas et il y a eu entre temps des heuristiques de bien meilleur qualité. Tu peux lire les travaux de Martello, Vigo et Pisinger sur des calculs de bornes inferieures au probleme de bin packing 3D (mais elle s'adaptent egalement pour le cas 1D). Ce sont des papiers de 2000 et 1998 (il y a "Three-Dimensional Bin Packing Problem" ou "Exact Solution of the two-dimensional finite bin packing problem"). C'est assez technique mais ces bornes vont en fait t'assurer que tu ne peux trouver de solution optimale avec moins de X CD. Et ils se servent de ces bornes pour trouver le nombre de CD necessaires.

    Bon courage pour la suite.

  3. #3
    Inactif
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    octobre 2004
    Messages
    3 894
    Détails du profil
    Informations personnelles :
    Âge : 39
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : octobre 2004
    Messages : 3 894
    Points : 4 684
    Points
    4 684

    Par défaut

    Déjà, ce n'est pas un tri, mais un problème d'optimisation...


    Pour résoudre ce genre de problèmes, tu as deux solutions qui doivent être choisies en fonction de tes besoins :
    - Méthodes heuristiques,
    - Méthodes exactes.


    Une méthode heuristique est souvent proche de l'optimal, sans toutefois jamais garantir qu'il est atteint (sauf coup de bol, bien sûr).
    Une méthode exacte te garantit qu'il n'existe aucune meilleure solution que celle trouvée, qui est donc optimale.


    Avec tes algos, tu ne peux pas trouver l'optimal "tel quel", car ils sont heuristiques. On tente UN SEUL rangement, suivant une méthode donnée (pas trop débile de préférence), et on considère - à raison - que l'on approche de l'optimal : c'est résumé brutalement, mais c'est pourtant bien ça.

    Comme ce genre d'algo est souvent très rapide, tu peux tenter de le dérouler suivant plusieurs fits, et prendre le meilleur possible, tout comme tu peux tenter de piocher tes valeurs de façon alternée (un coup la plus grande, un coup la plus petite). Une fois combiné, tu devrais avoir 6 à 10 méthodes heuristiques déroulées, dans laquelle une a produit un meilleur résultat que les autres.

    Déjà, tu devrais certainement observer un gain par rapport à une méthode heuristique unique "figée dans le marbre", et pour un temps de calcul plutôt ridicule car le tri initial des données n'est fait qu'une seule fois. Il te faut bien sûr optimiser aussi cette partie (tri QuickSort au minimum) afin de ne pas exploser ton temps de calcul à cause de ça...

    Si cela te convient, tu peux arrêter à ce stade et fournir le résultat. Tout dépend du pourcentage de pertes toléré...


    En méthode exacte, on passe dans un tout autre domaine, à savoir la RO (Recherche Opérationnelle) dans toute sa splendeur. Tes données étant, finalement, relativement petites pour un PC moderne, je te conseille d'aller voir du côté de la Programmation Dynamique, sachant qu'il devrait être possible de partir de la solution heuristique (optimisée ou non) comme base de départ.

    Histoire de mieux voir par où démarrer :
    http://www.labri.fr/perso/robson/cours/AlgAv_TD5.html
    http://www.labri.fr/perso/robson/cou...D5corrige.html

    Attention toutefois : là, le temps de calcul est rarement négligeable, mais c'est le prix à payer pour trouver LA solution... Sinon, il faudra se contenter d'une solution approchée, avec un pourcentage de pertes donné.


    Tu peux aussi tenter une méthode hybride : à partir de l'optimal absolu (somme des longueurs demandée, habituellement impossible à atteindre donc), tu peux raffiner le processus au fur et à mesure jusqu'à tomber sur perte réelle (pourcentage de différence entre la longueur des barres requises et la somme mathématique des longueurs utiles) qui sera tolérable, par exemple 15% de perte réelle.

    Si ton heuristique trouve une solution convenable, tu t'arrêtes. Sinon, tu tentes une heuristique optimisée, et si ça foire, tu tentes une recherche exacte.

    Là, on arrive aussi dans une approche pragmatique : de combien de temps disposes-tu pour donner la solution, après réception d'une commande, avant que le client ne décide d'aller voir le concurrent ?

    Si ton patron veut la réponse en 30 secondes maximum, à toi de lancer un max de calculs en même temps (vive les multi-cœurs...) afin de chercher une solution, et au bout du temps fatidique, tu donnes la meilleure solution trouvée, qu'elle soit optimale ou non.
    Si ton patron est radin et veut absolument la solution optimale, alors pas le choix : laisse tomber les heuristiques (sauf pour servir de "point de départ"), et passe directement en méthode exacte. Préviens-le avant que ça peut prendre plusieurs heures pour avoir la réponse... Ce qui pourrait très bien n'avoir aucune importance s'il a un PC dédié à ça qui bosse la nuit pour les commandes du lendemain !!

  4. #4
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 962
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 962
    Points : 16 880
    Points
    16 880

    Par défaut

    Citation Envoyé par fredschmidt Voir le message
    Mon problème
    Mon problème est que je ne trouve pas , dans de rare cas, une solution suffisament proche de l'optimale.

    Exemple: j'ai des barres standard de 2500, j'aimerai 10 barres de 1000 et 20 de 700.

    L'optimale est d'avoir 10 barres standard de 2500 qu'on découpe en 1000+700+700 = 2400.

    Mais en Decreasing First Fit ou Next Fit je me retrouve avec 5 barres standard découpé en 1000+1000=2000 et 6 barres standard en 700+700+700 = 2100 et 1 barre standard en 700+700=1400.
    Dans ce cas particulier, tu peux énumérer les différentes configurations de découpage possibles pour une barre:

    config #1 : 2500 = 2*1000 + 0*700 + 500
    config #2 : 2500 = 1*1000 + 2*700 + 100
    config #3 : 2500 = 0*1000 + 3*700 + 400

    Et ensuite faire une exploration de l'arbre des solutions possibles pour chaque objectif/contrainte (branch & bound), en utilisant le score (nb de barres utilisées) pour elaguer l'arbre.

    10 barres de 1000 =>

    5 * config #1 => manque 20 barres de 700
    4 * config #1 + 2 * config #2 => manque 16 barres de 700
    3 * config #1 + 4 * config #2 => manque 12 barres de 700
    2 * config #1 + 6 * config #2 => manque 8 barres de 700
    1 * config #1 + 8 * config #2 => manque 4 barres de 700
    0 * config #1 + 10 * config #2 => manque 0 barres de 700

    etc.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Invité de passage
    Inscrit en
    octobre 2008
    Messages
    11
    Détails du profil
    Informations forums :
    Inscription : octobre 2008
    Messages : 11
    Points : 3
    Points
    3

    Par défaut

    Bonjour,
    merci pour vos réponses.

    J'ai choisis la méthode de pseudocode, cette dernière est la plus facile à coder et la plus rapide.

    Je ne cherche pas la solution optimale, mon unique problème reste le souci du genre 1000+700+700, qui est trop éloigné de ce que je cherche.

    Pour la réponse de cedriku, comme il l'a mentionné, c'est technique, et surtout un peu trop pour moi, j'ai déjà fait du Bin packing 2D en utilisant simplement les méthode Decreasing First et Next Fit en Height et Widht, mais la c'est vraiment trop technique (je manque de pratique en algo, je suis débutant et je ne fais pas d'informatique dans ma formation).
    L'anglais ne me rebute pas, c'est plutôt les formules mathématiques (je ne vois pas le rapport avec l'algo).
    Merci également de m'avoir corrigé (pour moi sac a dos et Bin packing étaient pareil).

    Pour répondre à Mac LAK, la méthode de tester plusieurs algo me semble être une fausse bonne idée, j'y ai déjà pensé avant.
    J'ai tester les first, next, best et worst fit en normal et en decreasing, et d'un algo à l'autre les résultats sont meilleur ou pire, mais aucun de ces algo me permet de résoudre l'histoire des 1000+700+700.
    Pour la programmation dynamique, je laisse tomber, c'est trop compliqué pour moi, d'autant plus que les PC utilisés ne sont pas tout neuf et que le temps n'est pas à négliger.

    Etant donné que j'ai toujours une quantité importante de barres de mêmes longueurs (après découpe), j'ai pensé que la meilleur solution est de vérifier toutes les solutions possibles en additionnant les longueurs de barres souhaités après découpe entre elles (en restant < 2500), puis de prendre la 1ere solution la plus proche de 2500, jusqu'à épuisement d'une des longueurs, puis de choisir la solution suivante la plus proche de 2500, et ainsi de suite, jusqu'à avoir tout découpé.

    Exemple:

    j'ai 5 barres de 1200, 10 de 1000 et 14 de 700.

    Les solutions possible sont:
    1)1200 + 1200 = 2400
    2)1200+1000=2200
    3)1200+700=1900
    4)1000+1000=2000
    5)1000+700+700=2400
    6)700+700+700=2100

    Dans un 1er temps, j'utilise la solution1) (1er solution la plus proche de 2500 en 1ere position), je découpe dans une barre standard 1200+1200, je fais ça 2 fois de façon à ne plus avoir assez de barre pour la solution 1.
    Il me reste 1x1200

    Puis je passe a la solution 5) (1ere solution la plus proche de 2500, 2eme position), je découpe 7 barres de 1000+700+700, jusqu'à épuisement des barres de 700.
    Il me reste 3 barres de 1000.

    Je passe à la solution 2) (2eme solution la plus proche de 2500, 1ere position).
    Je découpe 1x 1200+1000.
    Il me reste 2 x 1000.

    Et pour finir, je passe à la solution 4) (4eme solution la plus proche, 1ere position), et je finis avec 1000+1000.


    Mon problème est que je n'arrive pas a faire l'algo qui va me donner toutes les positions possibles.

    Comme valeur de départ, j'ai les longueurs souhaitées, et les quantités de chaque longueurs.

    Pouvez-vous m'aider?

    Merci

  6. #6
    Inactif
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    octobre 2004
    Messages
    3 894
    Détails du profil
    Informations personnelles :
    Âge : 39
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : octobre 2004
    Messages : 3 894
    Points : 4 684
    Points
    4 684

    Par défaut

    Citation Envoyé par fredschmidt Voir le message
    J'ai tester les first, next, best et worst fit en normal et en decreasing, et d'un algo à l'autre les résultats sont meilleur ou pire, mais aucun de ces algo me permet de résoudre l'histoire des 1000+700+700.
    Tu as essayé en prenant alternativement la plus grande et la plus petite ? Ou la valeur "médiane" (= en milieu de tableau) ?

    Dans ton cas de figure, cela se résume (une fois trié) à prendre une barre de 1000, puis une barre de 700, puis une barre de 1000, puis une de 700, etc. jusqu'à épuisement des barres de 1000 où piocher alternativement ne se "verra" plus... En fonction du "fit" utilisé, tu devrais normalement plus ou moins tomber sur l'optimal, avec plusieurs essais de différentes méthodes.

    Et au moins, ça reste "générique", et sur un truc qui est déjà fait ou presque.

  7. #7
    Invité de passage
    Inscrit en
    octobre 2008
    Messages
    11
    Détails du profil
    Informations forums :
    Inscription : octobre 2008
    Messages : 11
    Points : 3
    Points
    3

    Par défaut

    Je ne suis pas sur de bien te suivre, j'ai l'impression que tu crois que je n'ai que 2 longueurs de barres différentes à placer, mais je peux en avoir plus que 2.

    En fait , je ne vois pas ce que tu veux dire par valeur médiane.

    Si je comprends bien, au lieu de d'abord trier les valeurs par ordre décroissant, je les tris par ordre décroissant par couche ( au lieu d'avoir 1200 1200 1200 1200... 1000 1000 1000 1000... 950 950 950... 750 750 750... j'ai 1200 1000 950 750 1200 1000 950 750...)? c'est ça?

    Merci

  8. #8
    Inactif
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    octobre 2004
    Messages
    3 894
    Détails du profil
    Informations personnelles :
    Âge : 39
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : octobre 2004
    Messages : 3 894
    Points : 4 684
    Points
    4 684

    Par défaut

    Non, du tout. Prenons un jeu de longueurs comme exemple :
    100 150 300 400 900 1200 1200 1800 1900 2000 2200 2200

    En prenant alternativement, tu vas avoir les valeurs suivantes, en prenant une fois en début de tableau, une fois en fin de tableau, en début, etc.

    => 100 2200 150 2200 300 2000 400 1900 900 1800 1200 1200

    En valeur médiane, tu prends la valeur en milieu de tableau :

    => 1200 900 1200 400 1800 300 1900 150 2000 100 2200 2200

    C'est plus clair ? Bien sûr, tu laisses ton tableau trié "tel quel", c'est juste ta boucle de parcours qui devient différente, pas le tri.

  9. #9
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 962
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 962
    Points : 16 880
    Points
    16 880

    Par défaut

    Citation Envoyé par fredschmidt Voir le message
    J'ai choisis la méthode de pseudocode, cette dernière est la plus facile à coder et la plus rapide.

    Je ne cherche pas la solution optimale, mon unique problème reste le souci du genre 1000+700+700, qui est trop éloigné de ce que je cherche.

    (...)

    J'ai tester les first, next, best et worst fit en normal et en decreasing, et d'un algo à l'autre les résultats sont meilleur ou pire, mais aucun de ces algo me permet de résoudre l'histoire des 1000+700+700.
    ?

    Bah, mon algo fait une exploration totale donc il trouve forcément l'optimal.


    j'ai 5 barres de 1200, 10 de 1000 et 14 de 700.

    Les solutions possible sont:
    1)1200 + 1200 = 2400
    2)1200+1000=2200
    3)1200+700=1900
    4)1000+1000=2000
    5)1000+700+700=2400
    6)700+700+700=2100
    Exact. Il faut alors alors explorer les solutions qui permettent d'avoir 5 barres de 1200, et d'y ajouter celles qui permettent d'avoir 10 barres de 1000, ...

    Ca donne assez vite le résultat sur mon PC : il faut 11 barres.
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    config #0 : 0*1200 0*1000 3*700 
    config #1 : 0*1200 1*1000 2*700 
    config #2 : 0*1200 2*1000 0*700 
    config #3 : 1*1200 0*1000 1*700 
    config #4 : 1*1200 1*1000 0*700 
    config #5 : 2*1200 0*1000 0*700 
    Target : [5, 10, 14]
    Solution : 7*(#1) 3*(#4) 1*(#5)  = [5, 10, 14]
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  10. #10
    Membre du Club
    Profil pro
    Inscrit en
    juillet 2005
    Messages
    55
    Détails du profil
    Informations personnelles :
    Âge : 30
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations forums :
    Inscription : juillet 2005
    Messages : 55
    Points : 61
    Points
    61

    Par défaut

    Dans le cas du probleme de fredschmidt, on est d'accord que l'algo Pseudocode est plutot bien adapté et simple.

    Mais je pense qu'il faut tout de meme preciser, que lister les configurations possibles revient a trouver toutes les solutions maximales d'un probleme de sac a dos 1D ce qui est deja NP-Dur.
    Dans le cas du probleme de fredschmidt, il est clair que le nombre de configurations est limité pour deux raisons :

    1) le nombre de taille differentes est faible (700, 1000, 1200)
    2) Les tailles sont tres grandes compare a la taille maximale 2500.

    Je dis ca juste pour que fredschmidt se rende compte de la complexité et que si ca marche bien dans ce cas la, ca ne sera pas forcement le cas s'il a des tailles petites par rapport a 2500 et beaucoup de tailles differentes.

    Mais sinon +1 pour la solution de pseudocode lol

  11. #11
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 962
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 962
    Points : 16 880
    Points
    16 880

    Par défaut

    Citation Envoyé par cedriku Voir le message
    Mais je pense qu'il faut tout de meme preciser, que lister les configurations possibles revient a trouver toutes les solutions maximales d'un probleme de sac a dos 1D ce qui est deja NP-Dur.
    C'est clair que ca ne fait pas de miracle. Je n'ai pas encore réussit a transformer NP en P.

    Cela dit, travailler sur les "configurations" plutot que sur les éléments découpés permet de réduire la taille des solutions a explorer. D'autant plus si on peut réduire la cible en la factorisant : Solution([500, 1000, 1400]) = 100 * Solution([5, 10, 14]) = 100*11 = 1100 barres
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  12. #12
    Membre du Club
    Profil pro
    Inscrit en
    juillet 2005
    Messages
    55
    Détails du profil
    Informations personnelles :
    Âge : 30
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations forums :
    Inscription : juillet 2005
    Messages : 55
    Points : 61
    Points
    61

    Par défaut

    Citation Envoyé par pseudocode Voir le message
    C'est clair que ca ne fait pas de miracle. Je n'ai pas encore réussit a transformer NP en P.
    Ah bon ? lol. Je trouve qu'un million de dollars c'est pas assez payé pour celui qui demontrerait NP egal ou different de P !!

    Citation Envoyé par pseudocode Voir le message
    Cela dit, travailler sur les "configurations" plutot que sur les éléments découpés permet de réduire la taille des solutions a explorer.
    Tout a fait, il faut juste faire attention au cout de la recherche de ces configurations et au nombre de configurations !

    Citation Envoyé par pseudocode Voir le message
    D'autant plus si on peut réduire la cible en la factorisant : Solution([500, 1000, 1400]) = 100 * Solution([5, 10, 14]) = 100*11 = 1100 barres
    Ben la factorisation permet de "diminuer" la complexite, grosse modo au lieu d'etre exponentiel en le nombre de barre, tu deviens exponentiel en le nombre de types de barres... mais comme dans le pire des cas il y a autant de types de barres que de barres... mais sur le fond je suis entierement d'accord avec toi.

    Et une telle factorisation est deja beaucoup plus difficile a mettre en oeuvre a partir de 2 dimensions ! Bon ok la c'est hors sujet.

  13. #13
    Invité de passage
    Inscrit en
    octobre 2008
    Messages
    11
    Détails du profil
    Informations forums :
    Inscription : octobre 2008
    Messages : 11
    Points : 3
    Points
    3

    Par défaut


    Merci pour votre aide, j'ai gardé la solution à pseudocode, et ça marche nickel en un temps relativement faible (< 1sec).

    Merci

+ Répondre à la discussion
Cette discussion est résolue.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •