Je cherche une implémentation déterministe pour tout algorithme d'emballage de bac 3D, c'est-à-dire pour emballer de nombreux petits et différents cuboïdes à l'intérieur d'une ou de nombreuses plus grandes. La solution pourrait varier de l'optimal.
Il devrait être écrit en C, C ++, Java, C #, IronPython, ironRuby ou toute autre langue d'une poubelle Can à partir du code .NET.
J'ai trouvé cet algorithme C http://www.diku.dk/hjemmesider /ansatte/pisant/3dbpp.c , mais cela ne fait pas pivoter les cuboïdes pour trouver le meilleur ajustement. Je suis correct avec ne les faire pivoter pas à l'envers, mais la rotation horizontale doit être possible.
3 Réponses :
Ce problème est np-dur. Votre meilleur pari est un algorithme d'approximation (jusqu'à ce qu'une personne géniale résout un problème de NP, ou un homme très chanceux trébuche sur une solution.) Je ne connais malheureusement aucun algorithme d'approximation de ce problème.
La résolution d'un problème de NP-complet en temps polynomial ne vous donnera toujours pas une solution polynomiale aux problèmes durs NP :)
Eh bien pour les petits paquets, le temps nécessaire n'est pas si élevé. La force si brute est une alternative juste pour quelques livraisons de magasinage en ligne.
@THOMASRS Si vous êtes prêt à faire une force brute, vous obtiendrez probablement le meilleur coup pour votre argent en utilisant un ILP correspondant pour représenter le problème et l'alimentant à quelque chose comme Gurobi.
Merci à @Idog, cependant j'ai déjà écrit une implémentation personnalisée qui fait quelques optimisations spécifiques à une application, telles que la comptabilisation de plusieurs cases de la même taille et de telles.
J'ai écrit un algorithme approximatif pour le cas que vous décrivez I.e. Boîtes rectangulaires 3D, avec rotation orthogonale, en C ++. Vous pouvez trouver les résultats et l'algorithme du papier publié: http://www.cs.ukzn.ac.za/publications/erick_dube_507 -034.pdf
L'application Source ou C ++ est-elle disponible en ligne?
C'est bon pour une solution simple mais ne fonctionne vraiment pas tout ça. Pour quiconque voulant une explication et aide à écrire une explication, je suggère ce livre: Problèmes de Knapsack, de Martello et de Toth, ISBN: 0471924202
Je ne trouve pas de résultats dans la page liée? Est-ce toujours la bonne URL?
@Amrelgarhy à partir du nom de l'URL d'origine, je suppose
J'ai converti wknechtel / 3d-bin-pack < / A> Code C à JavaScript. Peut être facilement port à c #.
https://github.com/keremdemirer/3dbinpackingjs
Vous pouvez exécuter des exemples de calculs à partir de index.html et examinez le rapport généré. pack1.js contient l'application et l'algorithme. Je ne sais pas comment fonctionne l'algorithme, mais les résultats sont satisfaisants pour les calculs d'emballage.
Vous prétendez que vous recherchez un algorithme, mais vous lisez ensuite les langages de programmation. Vous recherchez un algorithme générique ou une implémentation?
Voulez-vous la solution optimale ou une bonne qualité? Les cuboïdes sont-ils tous les mêmes? Lorsque vous dites une rotation, voulez-vous dire 90 degrés, ou n'importe quel angle?
@Beta: S'il emballe des cuboïdes dans un cuboïde, tout à fait autre chose que des multiples entiers de 90 degrés entraînera une solution sous-optimale.
@Asaph: de couse, pas! Ce n'est pas parce que j'ai mentionné "l'algorithme" ne signifie pas que c'est un devoir.
@Beta, eh bien il devrait être déterministe et une bonne solution est suffisante (car j'ai lu des solutions optimales sont très difficiles à trouver) Les cuboïdes ne sont pas tous identiques et je suppose que Kinopiko dit, toute rotation autre que de 90 degrés ne pas être utile.
@ Mads-Elvheim: Désolé pour l'ambiguïté. J'ai besoin d'une mise en œuvre concrète que je peux appeler directement. J'ai trouvé beaucoup de papiers résolvant ce problème à l'aide d'une programmation linéaire entier ou d'algorithmes génétiques. Mais je pensais que, pour un problème aussi commun, il doit y avoir une implémentation existente.
@Kinopiko et Mouk, essayez de mettre 5 carrés d'unité dans un carré de largeur 2.708, puis racontez-moi à nouveau sur des angles non-90 degrés.
@Beta convaincu. Avoir un tel algorithme? 90 degrés Les rotations sont juste assez pour moi.