Algoritmo di imballaggio bin 3D

Sto cercando un'implementazione deterministica per qualsiasi algoritmo di imballaggio di contenitori 3D, vale a dire per imballare molti piccoli e diversi cuboidi all'interno di uno o più grandi. La soluzione potrebbe variare da quella ottimale.Algoritmo di imballaggio bin 3D

Dovrebbe essere scritto in C, C++, Java, C#, IronPython, IronRuby o qualsiasi altra lingua in cui è possibile bin.

Ho trovato questo algoritmo C http://www.diku.dk/hjemmesider/ansatte/pisinger/3dbpp.c, ma non ruota i cuboidi per trovare la soluzione migliore. Sto bene, non ruotandoli capovolti, ma la rotazione orizzontale dovrebbe essere possibile.

fonte

2009-10-13 Mouk

@Mouk: è questo compito? – Asaph

Si dichiara che si sta cercando un algoritmo, ma si elencano quindi i linguaggi di programmazione. Stai cercando un algoritmo generico o un'implementazione? –

Vuoi la soluzione ottimale, o quella che è abbastanza buona? I cuboidi sono tutti uguali? Quando dici rotazione, intendi 90 gradi o qualsiasi angolo? – Beta

Ho scritto un algoritmo approssimativo per il caso che descrivi, ad esempio, scatole rettangolari 3D, con rotazione ortogonale, in C++. È possibile trovare i risultati e l'algoritmo nel documento pubblicato: http://www.cs.ukzn.ac.za/publications/erick_dube_507-034.pdf

fonte

2010-04-19 14:55:29 user320450

L'app source o C++ è disponibile online ovunque? –

Questo è buono per una soluzione semplice ma in realtà non funziona molto bene. Per chiunque desideri una spiegazione e aiutare a scriverne uno suggerisco questo libro: Knapsack Problems, di Martello and Toth, ISBN: 0471924202 – ars265

Questo problema è NP-difficile. La tua migliore scommessa è un algoritmo di approssimazione (fino a quando un genio risolve qualsiasi problema di NP, o un compagno molto fortunato inciampa in una soluzione.) Purtroppo non conosco algoritmi di approssimazione per questo problema.

fonte

2009-10-16 22:51:16 ldog

Risolvere un problema NP-completo in tempo polinomiale non ti darà ancora una soluzione polinomiale per i problemi NP-difficili :) –

ho convertito wknechtel/3d-bin-pack codice C a JavaScript. Può essere facilmente portato a C#.

https://github.com/keremdemirer/3dbinpackingjs

È possibile eseguire calcoli di esempio da index.html di file e rivedere il rapporto generato. Il file pack1.js contiene l'app e l'algoritmo. Non sono sicuro di come funziona l'algoritmo ma i risultati sono soddisfacenti per i calcoli del packaging.

fonte

2016-02-27 23:10:46

risposta

Problemi correlati