Discussion :

[JeanRaviol]

Salut,

Je recherche un algo proche de celui du problème du sac à dos.
Avec plusieurs objets de tailles différentes (rectangulaires pour simplifier), je dois en faire des colis.
Je ne trouve rien de bien concluant.

Merci de votre aide ;-)

A+, Jean

[JHelp]

Peux-tu décrire un peux mieux le pb, stp
JHelp

[senke]

je ne sais pas si c'est ce que tu recherches mais renseignes toi sur la construction de carrés magiques "approximatifs".

[mio]

Si je comprends ton probleme est celui qui consiste a optimiser le remplissage d'un sac a dos avec des objets caracterises par un volume d'encombrement. C'est un probleme complexe si je me rappelle bien.

Voici quelques liens qui devraient t'aider.
http://eleves.ensmp.fr/P00/00rouaul/...cados_swp.html
http://www.enseignement.polytechniqu...in8/node8.html

[JeanRaviol]

Merci de vos réponse.

Oui, c'est bien un algorithme de colisage. Je dois remplir des colis avec des pièces rectangulaires de différentes tailles.

Je regarde vos liens.

Merci et A+,

Jean

[JeanRaviol]

Salut,

En plus de ces algo, je dois y rajouter un soupçcon de 3D pour tenir compte du volume :-((((

Cela va être dur. Si vous avez d'autres idées, je suis preneur ;-)

A+ et merci
Jean

[JHelp]

Je vais peut etre te paraitre idiot, mias ton probleme est-ce :
Soit un batiment ayant un longuer,hauteur,profondeur,
Soit des boites, ayant égalament 3D,
Combien de boites peut on metre ?
ou
Comment s'aranger pour mettre le plus de boites possible ?
ou
...?

Sans les donées d'un pb, on à du mal à le résoudre.
JHelp

[JeanRaviol]

Salut JHelp,

Excuse-moi de ne pas avoir été plus clair.
Tu as vu juste, je cherche à remplir une grosse boîte avec le plus possible de petites boîtes.
Je me base sur des objets 3D rectangulaires pour simplifier (!).

Si tu as des conseils, je suis preneur ;-)

A+ et merci
Jean

[JHelp]

Je vois, malheureusement, je n'ai pad le temps de réfléchir plus en avant.
Une piste : construit un arbre de décision. Je supose que tes boites ont des tailles diferérentes. Un arbre de décision, c'est la construction d'un arbre et d'une fonction d'évalutaion. La fonction d'évaluation te donne à chaque branche une estimation plus grande du nombre de boites que tu peu mettre, et tu développes d'abord celle qui donne la meilleur évaluation. Une fois que tu arrives à une feuille, tu as une valeure du nombre de boites réelles si tu met les boites en suivant l'arbre, tu "ébranches", c'est à dire, que tu supprimes de l'arbre toutes les branches commencées qui ont une estimation inférieure à la valeure trouvée, ainsi, tu n'a qu'a développer les branches qui restes (s'il en reste). L'"ébranchage" se justifie, si ta fonction d'évaluation, donnee bien un nombre supérieur aux nombres de boites possibles. Forcement, puisque ce nombre est supérieur, toutes les feuilles, de cette branche, auront une valeur plus petite, donc si cette évaluation est trop petite, inutile de la développer.
Pour la fonction d'évalutaion je te sugéres (il y a surement mieux), soit v le voulme de la plus petite boite parmis celles non mises, soit V le volume restant, évalution = V/v.
J'espère avoir été clair, et que ça peut t'aider.
JHelp

[Pazz]

Oui l'arbre est la bonne solution, et avec de bonnes heuristiques il ne sera pas trop gros.

[SQLpro]

La méthode à utiliser est la technique du backtraking que l'on trouve en recherche oprationelle.

Cherche knapsack dans un moteur US

Voici une implémentation :
http://www.nist.gov/dads/HTML/knapsackProblem.html
http://www.cs.sunysb.edu/~algorith/files/knapsack.shtml

A +

Frédéric BROUARD, expert SQL / bases de données
Livre 'SQL' la référence - Campus Press éditeur
* http://sqlpro.developpez.com/bookSQL.html *
site web 'SQLpro' http://sqlpro.developpez.com/