Cut Algorithmus Optimierung

Mir und einigen meiner Freunde am college zugewiesen wurden, eine praktische Aufgabe, die Entwicklung eines net-Anwendung für die Optimierung von schneiden von rechteckigen teilen aus einer Art von material. So etwas wie apps in diese Liste, aber mehr simpel. Im Grunde bin ich daran interessiert, wenn es irgendeinen Quellcode für diese Art von Optimierungs-algorithmen, die über das internet verfügbar. Ich Plane, mir die app zu entwickeln mit Adobe Flex-framework. Die Programmierung erfolgt in Actionscript 3, ofc. Ich bezweifle jedoch, dass es irgendwelche Optimierungs-Proben für diese Sprache. Es kann einige für Java, C++, C#, Ruby oder Python und anderen populären Sprachen, obwohl(dann würde ich nur noch schreiben in WIE). Also, wenn jemand weiß, jede freie libs oder Algorithmus-code-Beispiele, die zu mir passen würde, würde ich gerne Ihre Vorschläge hören. 🙂

InformationsquelleAutor Varnius | 2010-12-05

  1. 3

    Dies möglicherweise overkill für das, was Sie brauchen, aber der folgende link beschreibt einen Ansatz, der liefert sehr gute Ergebnisse für diese Art von problem:

    http://www.intechopen.com/articles/show/title/a_greedy_algorithm_with_forward-looking_strategy

    Es wird kein code zur Verfügung, aber der Algorithmus ist beschrieben in genug detail, dass es nicht zu schwierig zu implementieren. Ich habe umgesetzt wird dieses mit C# (sorry, kann nicht teilen, dass der "code") und war sehr zufrieden mit dem Ergebnis.

    Danke, scheint wie eine gute Lösung, werde ich hineinschauen. 🙂

    InformationsquelleAutor cbranch

  2. 1

    Dieser klingt genau wie die stock Schneid-problem die extermely schwierig! Die besten Lösungen nutzen lineare Programmierung (in der Regel basierend auf dem simplex-Methode) mit column generation (die, die auch noch nach Jahren auf eine Einschränkung der Lösung des Forschungsvorhabens ich fühle mich nicht bestückt zu geben, eine halbwegs anständige Erklärung). Kurz gesagt, Sie werden nicht wollen, um zu versuchen, diesen Ansatz in Actionscript; folglich, mit dem, was Sie tun, zu implementieren, Sie sollten nicht erwarten, dass große Ergebnisse, die auf alles andere als kleine Probleme.

    Ist der beste Rat, den ich anbieten kann, ist dann zu sehen, wenn Sie können schneiden Sie die Quell-Rechteck in Streifen schneiden (jeweils von der Breite des größten Rechtecke, die Sie brauchen), dann weiter zu unterteilen, der Rest von jedem Streifen nach der "Kopf" Rechteck entfernt wurde.

    Ich würde empfehlen die Verwendung von branch-and-bound als Ihre Optimierung Strategie. BnB arbeitet, indem Sie eine erschöpfende Baum Suche, die Spur hält, die beste Lösung bisher gesehen. Wenn Sie eine Lösung finden, aktualisieren Sie die gebunden, und wieder ansetzen der Suche nach der nächsten Lösung. Wenn Sie wissen, dass Ihre Suche führt Sie an einen ast, dass Sie wissen, kann nicht dazu führen, eine bessere Lösung als die beste, die Sie gefunden haben, können Sie backtrack früh am Punkt.

    Da diese Suche Bäume werden sehr groß ist, werden Sie wahrscheinlich wollen, eine Frist auf die Suche und gerade wieder Ihre besten Anstrengungen.

    Hoffe, das hilft.

    InformationsquelleAutor Rafe

  3. 0

    Hatte ich Probleme bei der Suche Beispiele, wenn ich wollte, das gleiche zu tun für die woodwoorking Firma für die ich arbeite. Das problem ist NP-schwer, so dass Sie verwenden müssen, um eine Annäherung Algorithmus wie ein first-fit oder best-fit-Algorithmus.
    Führen Sie eine Suche für 2d-bin-packing-algorithmen. Die, die ich gefunden, Sie Sortieren die Paneele größten bis zur kleinsten, dann fügen Sie die Blätter um, indem in der ersten bin, wird es passen. Sorry habe nicht den code mit, der mit mir und seiner in vb.net sowieso.

    InformationsquelleAutor Kratz

Schreibe einen Kommentar