3d bin Packalgorithmus

Ich bin auf der Suche nach einer deterministischen Implementierung für jeden 3d bin Packalgorithmus, d. H. Für die Verpackung vieler kleiner und unterschiedlicher Quader innerhalb eines oder mehrerer großer. Die Lösung könnte von der optimalen abweichen.3d bin Packalgorithmus

Es sollte in C geschrieben werden, C++, Java, C#, IronPython, IronRuby oder jede andere Sprache, die ich von .Net-Code bin.

Ich fand diesen C-Algorithmus http://www.diku.dk/hjemmesider/ansatte/pisinger/3dbpp.c, aber es dreht nicht die Quader, um die beste Anpassung zu finden. Es ist in Ordnung, sie nicht auf den Kopf zu drehen, aber eine horizontale Rotation sollte möglich sein.

Quelle

2009-10-13 Mouk

@Mouk: Ist das Hausaufgaben? – Asaph

Sie behaupten, Sie suchen nach einem Algorithmus, aber Sie listen dann Programmiersprachen auf. Suchen Sie nach einem generischen Algorithmus oder einer Implementierung? –

Wollen Sie die optimale oder eine sehr gute Lösung? Sind die Quader gleich? Wenn Sie Rotation sagen, meinen Sie 90 Grad oder irgendeinen Winkel? – Beta

Ich habe einen ungefähren Algorithmus für den Fall geschrieben, den Sie beschreiben, d. H. 3D-Rechteckkästen mit orthogonaler Rotation in C++. Sie können die Ergebnisse und Algorithmus in dem veröffentlichten Papier finden: http://www.cs.ukzn.ac.za/publications/erick_dube_507-034.pdf

Quelle

2010-04-19 14:55:29 user320450

Ist die Quell- oder C++ - App überall online verfügbar? –

Das ist gut für eine einfache Lösung, aber funktioniert wirklich nicht so gut. Für alle, die eine Erklärung und Hilfe beim Schreiben wünschen, empfehle ich dieses Buch: Knapsack Problems, von Martello und Toth, ISBN: 0471924202 – ars265

Dieses Problem ist NP-schwer. Ihre beste Wette ist ein Approximationsalgorithmus (bis eine geniale Person irgendein NP-Problem löst, oder ein sehr glücklicher Mensch stolpert über eine Lösung.) Ich kenne leider keine gut bekannten Approximationsalgorithmen für dieses Problem.

Quelle

2009-10-16 22:51:16 ldog

Das Lösen eines NP-vollständigen Problems in Polynomialzeit gibt Ihnen immer noch keine Polynomlösung für NP-harte Probleme :) –

I umgewandelt wknechtel/3d-bin-pack C-Code Javascript. Kann leicht zu C# portiert werden.

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

Sie können beispielsweise Berechnungen von index.html-Datei ausführen und den erstellten Bericht überprüfen. pack1.js Datei enthält die App und den Algorithmus. Ich bin mir nicht sicher, wie der Algorithmus funktioniert, aber die Ergebnisse sind zufriedenstellend für Verpackungsberechnungen.

Quelle

2016-02-27 23:10:46

Antwort

Verwandte Themen