Wenn man zum Beispiel aus einer Blechtafel verschieden große Flächen herausschneiden muß, hat man ja das Problem, die Formen so anzuordnen, daß so wenig Verschnitt wie möglich entsteht. Frage: Gibt es für so Etwas ein Programm, welches die Anordnung der Flächen optimal errechnen kann? MfG Paul
Paul Baumann schrieb: > Frage: Gibt es für so Etwas ein Programm, welches die Anordnung der > Flächen optimal errechnen kann? Berechnen kann man das schon, die Frage ist wie lange willst du warten? Hier eine kleine Einführung: http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Lehre/WS1011/Proseminar_Algorithmen/OptimiertePlatzierung_Folien.pdf Paul Baumann schrieb: > Gibt es für so Etwas ein Programm http://www.eding.de/projekte/projektuebersicht/rov/rechteck-optimal-verteilung-programmbeschreibung.html
Läubi .. schrieb: > Berechnen kann man das schon Da ist der Begriff berechnen wohl etwas fehl am Platz - das ist eher ein systematisches Probieren. Aber deswegen gehört das Problem auch in die Klasse NP-vollständig.
Uhu Uhuhu schrieb: > Da ist der Begriff berechnen wohl etwas fehl am Platz ... der Bergiff NP-vollständig aber auch :) Es handelt sich hier um ein Optimierungs- nicht um ein Entscheidungsproblem.
@Läubi Danke für die Hinweise und den "Lesestoff". Ich dachte eben daran, daß etliche Leute dieses Problem haben. (Stanzerei, Kleidungszuschnitt, Zeitungsartikel anordnen etc.) Ich will mal versuchen, ob ich in der Openoffice Tabellenkalkulation etwas Anständiges zusammenbringe. Den Begriff "NP-vollständig" hatte ich noch nicht gehört. Das ist komplizierter, als ich dachte... MfG Paul
Yalu X. schrieb: > ... der Bergiff NP-vollständig aber auch :) > > Es handelt sich hier um ein Optimierungs- nicht um ein > Entscheidungsproblem. Wenn du das globale Optimum suchst, dann bist du bei NP-vollständig. Wenn du vorher abbrichst, bist du ein fauler Hund ;-) Paul Baumann schrieb: > Den Begriff "NP-vollständig" hatte ich noch nicht gehört. Das ist die härteste Problemklasse überhaupt. Wenn du dafür eine effiziente Lösung findest, brachst du dir keine Sorgen mehr zu machen...
Yalu X. schrieb: > ... der Bergiff NP-vollständig aber auch :) > > Es handelt sich hier um ein Optimierungs- nicht um ein > Entscheidungsproblem. Wo liegt da der Unterschied ? Bei einer Optimierung setze ich mindestens zwei Elemente voraus bei denen ich mich für eines von beiden entscheiden muß -> ergo Optimierung sind Entscheidungsprobleme in meinen Verständnis. Gruß Hagen PS: ich muß dazu sagen das es ja um eine Optimierung ala Suche handelt.
Uhu schrob:
>Das ist die härteste Problemklasse überhaupt.
Den leisen Verdacht bekam ich beim Lesen des Artikels in Wikipedia
auch...
Na, mal sehen, ob ich da was hinkriege. Ich denke, ich müßte mit dem
größten Teil an der linken, oberen Ecke beginnen. Damit bekomme ich die
Entfernung zur rechten oberen Ecke. Dann kann ich testen lassen, welche
der anderen Werkstücke noch dahin passen würde. Alle, die noch breiter
sind, scheiden aus und müssen in der nächsten "Zeile" Platz finden.
u.s.w
MfG Paul
Hagen Re schrieb: > Optimierung sind Entscheidungsprobleme in meinen Verständnis. Entscheidungsprobleme beschäftigen sich meist mit dem Umstand ob es überhaupt eine Lösung gibt. Das heißt aber nicht notwendigerweise, dass du durch das Wissen, dass es eine Lösung gibt auch ein "Ergebnis" im Sinne von: So und so mußt du es machen, damit die Lösung minimal/Maximal ist, hier steht es eigentlich ganz übersichtlich erklärt: http://de.wikipedia.org/wiki/Optimierungsproblem Hagen Re schrieb: > PS: ich muß dazu sagen das es ja um eine Optimierung ala Suche handelt. Dann ist es ein Suchproblem ;) Paul Baumann schrieb: > Den leisen Verdacht bekam ich beim Lesen des Artikels in > Wikipedia auch... > Na, mal sehen, ob ich da was hinkriege. Nicht entmutigen lassen. "Schwer" heißt hier nur, dass es aufwändig zu berechnen ist, nicht das es schwer ist einen Algorithmus zu schreiben... er wird nur für Große n sehr lange laufen... was aber möglichwerweise für deinen Anwendungsfall egal ist.
Ja gut, das was du anspricht ist in meinen Augen der Unterschied zwischen lokalen und globalen Maximas = Optimas. Das kleinste lokale und/oder globale Optima kann durchaus auch 0 sein. Ändert aber nichts an der Sache das auch solche Problem NP-vollständig sein können. Eher im Gegenteil, die angewendeten Optimierungsverfahren (oft eigentlich Suchverfahren), die auch für das Packungsproblem hergenommen werden, gehen fast immer von NP-vollständig aus. Zb. genetische Algorithmen die man auf solche Suchprobleme (Packungsbrobleme, Problem des Handlungsreisenden usw.) anwendet. Denoch Danke, da ich feststellen musste das es nur eine Definitionsfrage ist und ich mal wieder was anders unter dem Wort ansich verstanden habe. Gruß Hagen
Ein Suchproblem ist ebenso ein Optimierungsproblem, man möchte ja die Suchgeschwindigkeit möglichst optimieren.
Hagen Re schrieb: > man möchte ja die > Suchgeschwindigkeit möglichst optimieren Ich zitiere mal: >> Als Suchproblem bezeichnet man in der >> Theoretischen Informatik ein Problem ... http://de.wikipedia.org/wiki/Suchproblem Klar versucht der "Praktische Informatiker" die Suchgeschwindigkeit zu optimieren (welche ja u.A. von Proz geschw und Speicher abhängen kann), für den "Theoretische Informatiker" ist das aber irrelevant da nur die "schwere" des Problems zählt für genügend große n (unter der Annahme einer deterministischen Turingmaschine mit unendlich langem Band), das die bloße Aussage, es gäbe eine Lösung in der Praxis zudem meist uninteressant ist interessiert ihn auch nicht so sehr ;)
Angehängte Dateien:
-
Spiegelbilder.jpg
130 KB
Wie kam ich drauf? Ich habe hier eine ganze Menge "Spiegelbilder". Nun fragte ich mich, wie ich noch mehr davon an die Wand bringen könnte. MfG Paul
Ein Schreiner, ein Physiker und ein Mathematiker sollen gegeneinander im
Rechnen antreten.
Jeder erhält einen verschlossenen Briefumschlag mit der Aufgabe und wird
damit in ein eigenes Zimmer geschickt. Die Aufgabe lautet
6 * 8 = ?
Kaum sind die Türen zu, geht die vom Schreinerzimmer wieder auf und er
sagt: "48".
Eine halbe Minute später kommt auch der Physiker mit dem Rechenschieber
in der Hand und sagt: "6 mal 8 ist ungefähr 47,5".
Nach einer halben Sunde kommt auch der Mathematiker heraus und
verkündet:
"Es existiert eine Lösung"
Paul, bist Du Alkoholiker? Alle Spiegelbilder sind Werbung fuer irgendeinen Fusel. Ich sehe weniger ein Such- als ein Suchtproblem. :p
Uhu Uhuhu schrieb: > Paul Baumann schrieb: >> Den Begriff "NP-vollständig" hatte ich noch nicht gehört. > > Das ist die härteste Problemklasse überhaupt. Auch das nicht. Es ist nur die härteste Problemklasse innerhalb von NP. Die NP-vollständigen Probleme sind also sozusagen die schwersten Proble- me unter den potentiell leichten. Aber zurück zum eigentlichen Thema: @Paul: Ungeachtet aller Begrifflichkeiten aus der theoretischen Informatik ist dein Problem wahrscheinlich tatsächlich so sauschwer, dass man mit dem PC nicht die optimale Lösung findet, selbst wenn man ihn ein ganzes Wo- chenende rechnen lässt, es sei denn, deine Spiegelbildersammlung ist sehr übersichtlich, was ich aber nicht so sehr glaube ;-) Trotzdem, um einen Eindruck vom Umfang des Problems zu bekommen: - Wieviele dieser Spiegelbilder hast du denn überhaupt? - Wie groß sind diese (kleinstes und größtes Bild)? - Wie groß ist die Wand? Aber nicht, dass du jetzt anfängst, alles auszumessen. Grobe Schätzungen genügen völlig :) Es gibt natürlich heuristische Algorithmen, die in relativ kurzer Zeit eine gute, aber eben nicht die beste Lösung finden. Eine gute Lösung findest du aber wahrscheinlich auch selbst, wenn du dir verkleinerte Modelle der Spiegelbilder aus Pappe anfertigst, und einen Abend damit verbringst, diese auf einem Blatt Papier hin und herzuschieben :)
> > @Paul: > > Ungeachtet aller Begrifflichkeiten aus der theoretischen Informatik ist > dein Problem wahrscheinlich tatsächlich so sauschwer, dass man mit dem > PC nicht die optimale Lösung findet, selbst wenn man ihn ein ganzes Wo- > chenende rechnen lässt, es sei denn, deine Spiegelbildersammlung ist > sehr übersichtlich, was ich aber nicht so sehr glaube ;-) > > Trotzdem, um einen Eindruck vom Umfang des Problems zu bekommen: > > - Wieviele dieser Spiegelbilder hast du denn überhaupt? > > - Wie groß sind diese (kleinstes und größtes Bild)? > > - Wie groß ist die Wand? > > Aber nicht, dass du jetzt anfängst, alles auszumessen. Grobe Schätzungen > genügen völlig :) > > Es gibt natürlich heuristische Algorithmen, die in relativ kurzer Zeit > eine gute, aber eben nicht die beste Lösung finden. Eine gute Lösung > findest du aber wahrscheinlich auch selbst, wenn du dir verkleinerte > Modelle der Spiegelbilder aus Pappe anfertigst, und einen Abend damit > verbringst, diese auf einem Blatt Papier hin und herzuschieben :) Durchaus eine venünftige Lösung. Bei komplexen Blechzuschnitten und sauteurem Material ( zB. 4 mm Kupfer oder Titan- beschichtetem Edelstahl ) ist die Modellmethode ( Papier 1:10 ) sehr hilfreich. Die Laserschneider haben natürlich solche Verschnittoptimierungs- programme. Aber immer hilft das auch nicht. Interessant wird es, wenn Schliffrichtungen des Ausgangsmaterials auch noch beachtet werden müssen.
Haribohunter schrob:
>Paul, bist Du Alkoholiker?
Nein, dafür habe ich keinen Facharbeiterbrief.
;-)
Mir haben sie einfach nur gefallen und so begann ich damit, sie auf
Flohmärkten zu kaufen und zu sammeln.
@Yalu
Also:
Ich habe insgesamt 34 solcher Bilder. 3 davon sind 42*30cm groß, die
Anderen habe alle ungefähr A4-Format. Die Wand ist 2,60m*1,80m, wobei
die Bilder in einer Höhe von ca. 1,30 Metern beginnen.
Sicher könnte ich das mit Papiermodellen von Hand optimieren, aber mir
kam der Gedanke, daß ich ja eben nicht der Einzige bin, der so Etwas
tun will, -offenbar kennt Bernd dieses Problem in seiner Werkstatt
auch.
MfG Paul
Es müsste doch da irgendein frei verfügbares Programm dafür geben. Dafür gibt es auch Anwendungsmöglichkeiten in Hülle und Fülle. Wobei ich nie an Spiegelbilder an einer Wand gedacht hätte.
Formulier dein Problem als ILP und stecke es in einen der zahlreich online verfügbaren ILP-Solver
@Grotesque Das ist ein grotesker Ratschlag. ;-) Ehe ich diese Sprache erlernt habe, um ein Problem so zu formulieren, daß es ein sog. ILP-Solver versteht, habe ich es wahrscheinlich 100x zu Fuß gelöst. (Ich mußte erst einmal suchen, was das überhaupt bedeutet) MfG Paul
Alexander Schmidt schrieb: > Es müsste doch da irgendein frei verfügbares Programm dafür geben. Dafür > gibt es auch Anwendungsmöglichkeiten in Hülle und Fülle. Eigentlich nicht. Dazu ist das Problem zu speziell und zu eingeschränkt. Interessant wird es wenn beliebige Drehungen und das Einlegen von Objekten in andere Objekte erlaubt sind. Dann wird es richtig schwer. Paul: Mein erster Ansatz wäre eine Backtracking Lösung zu versuchen. Die Bilder werden in kleinere gleich große Zellen zerlegt, genausowie auch die zur Verfügung stehende Wandfläche. Und dann geht das Programm einfach (ha, ha) mit einem Backtracking an die Sache ran: das erste Bild wird positioniert und dann reihum alle Bilder der Reihe nach angelegt. Wenns nicht klappt, wird die letzte Wahl rückgängig gemacht und dafür eine andere Position/Bild gewählt. Aber mach dich darauf gefasst, dass dein PC unter Umständen einige Nachtschichten einlegen wird. Eventuell könnte man mit Heuristiken weiterkommen, wie zb versuche zuerst die großen Bilder unterzubringen in der Hoffnung, dass die kleinen dann schon in die Lücken reinrutschen. Mit Heuristiken kann man aus Backtracking schon noch einiges an Laufzeit rausholen. Gib dich zunächst mit überhaupt einer Lösung zufrieden. Die optimale Lösung zu finden ist nämlich dann eine reine Laufzeitfrage (die dann durchaus auch schon mal das Alter des Universums erreichen kann) Als Einstimmung in Backtracking lohnt es sich das sog. 8-Damen Problem zu studieren.
@Karl-Heinz schrob: >Dazu ist das Problem zu speziell und zu eingeschränkt. Das glaube ich eben nicht. Ich habe einen Kompagnon, der in einer Stanzerei arbeitet. Bei denen ist es noch schlimmer: Sie haben nicht nur rechteckige bzw. quadratische Teile sondern auch welche mit völlig abwegigen Formen auszustanzen. Für den wäre so Etwas ein Segen. >....wie zb versuche zuerst die großen Bilder unterzubringen in >der Hoffnung, dass die kleinen dann schon in die Lücken reinrutschen. Ich bin dabei, meine Idee von 13:06 Uhr in die Tat umzusetzen. Leider habe ich mich dabei verhaspelt und einen Schwung Zirkelbezüge eingebaut. Das gibt riesige Formeln mit mit einem Haufen "Wenn"-Bedingungen... Damit kann ich erst nächste Woche weitermachen, weil es noch Anderes zu tun gibt. MfG Paul
Paul Baumann schrieb: > @Karl-Heinz schrob: >>Dazu ist das Problem zu speziell und zu eingeschränkt. > Das glaube ich eben nicht. Ich habe einen Kompagnon, der in einer > Stanzerei arbeitet. Bei denen ist es noch schlimmer: Sie haben nicht > nur rechteckige bzw. quadratische Teile sondern auch welche mit > völlig abwegigen Formen auszustanzen. Für den wäre so Etwas ein Segen. Du widersprichst dir hier selber. Auf der einen Seite soll das eingeschränkte Problem * nur Rechtecke * die können auch nicht verdreht sein nicht schon zu speziell eingeschränkt sein, auf der anderen Seite bringt das Beispiel wo du eine gleichwertige Problemstellung siehst, sofort den neuen Passus * beliebige Formen ins Spiel Jede Änderung der beiden Ausgangsparameter (rechtecke, achsparallel) bzw. jeder zusätzlich zu berücksichtigende Paramater verkompliziert das Problem enorm! Dein Problem ist schon schwer. Mit jeder Aufweichung der bei dir vorliegenden Einschränkungen wird es noch schwerer. (schwerer im Sinne der NP Vollständigkeit. Im Prinzip ist es leicht zu lösen, nur die Rechenzeit wächst einem über den Kopf. Im Prinzip ist auch ein Travelling Salesman mit 50000 Städten nicht schwer: berechne alle möglichen Routen und suche die kürzeste raus. Im Prinzip kein Problem, alleine hat man eher selten die Jahrtausende Jahre Zeit, die heutige Rechner im allgemeinen Fall für diese Lösung benötigen)
@Karl-Heinz >Als Einstimmung in Backtracking lohnt es sich das sog. 8-Damen Problem >zu studieren. Da habe ich eben diese Seite gefunden und auch noch andere, die das Problem und den Algorithmus erläutern. http://www.hbmeyer.de/backtrack/achtdamen/autoacht.htm Oh, oh! Mein Rechner ist nicht der Langsamste, (Athlon64x2 mit 2,4GHz und anständig RAM (2GByte) Trotzdem brachte der Kollege erst nach 9 Minuten ein Resultat. Dabei sind es dort nur 8 Damen, die sich "beharken". Obwohl: Manch Einer hat schon mit einer Dame im Hause seine liebe Not. ;-) MfG Paul
@Karl_Heinz >Du widersprichst dir hier selber. >Auf der einen Seite soll das eingeschränkte Problem >* nur Rechtecke >* die können auch nicht verdreht sein.... Ich habe mich da falsch ausgedrückt: Für MICH sind nur Rechtecke bzw. Quadrate wichtig. Ich werde auch in meine Überlegungen keine anderen Formen einbeziehen. Der Faden ist nur so weitergedacht worden, daß es bei anderen Formen noch "schlimmer" aussieht. MfG Paul
Alexander Schmidt schrieb: > Es müsste doch da irgendein frei verfügbares Programm dafür geben. Im Prinzip schon: http://www.csc.liv.ac.uk/~epa/surveyhtml.html (Sourcecode auf Anfrage) http://www.cs.arizona.edu/icon/oddsends/bpack/bpack.htm (Ein 'icn' Programm... noch nie was von gehört.. ;) http://users.cs.cf.ac.uk/C.L.Mumford/Research%20Topics/layout/Outline.html (Mit Beispielapplets einfach mal nach applet auf der Seite suchen) Wenn man nach "Strip packing" sucht findet man auch die ein oder andere Info.
@Paul: Meinst du wirklihc, dass eine autmatische Lösung das ist, was du suchst? Da das ganze Deko ist, soll es doch wahrscheinlich auch ästhetischen Ansprüchen genügen. eventuell ein wenig Symmetrie oder bestimmte elemente in der Mitte Eine optimale Lösung ist wahrscheinlich ziemlich hässlich
@Vlad Ja, das ist bestimmt nicht die ästhetische Art und Weise. Es hat mich eben nur auf solche dummen Gedanken gebracht... MfG Paul
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.