Möglichst viele Flächen in eine größere einordnen
gibt es einen Algorithmus um kleinere Flächen möglichst platzsparend in eine große einzuordnen? Also z.b. Mehrere unterschiedliche Rechtecke in ein großes Rechteck..
4 Antworten
Es gibt dafür keine einfache Lösung. Die Anzahl der Kombinationen für unterschiedlich große Rechtecke ist einfach zu groß. Es gibt eine Reihe von Suchalgorithmen, mit denen solche Lösungen angenähert werden können, das ist alles andere als trivial, vor allem, wenn noch Nebenbedingungen dazu kommen. In der Industrie kommt das relativ oft vor (sog. Schneideprobleme).
es geht mir ja nicht darum eine Aufgabe zu lösen, sondern einen Algorithmus oder suchverfahren zu haben... Wie heißen den solche suchverfahren damit ich weiß nach was ich googlen muss :)
Das übrigens schon kompliziert genug für gleiche Rechtecke. Stelle Dir vor, du sollst in ein großes Rechteck möglichst viele kleine Rechtecke eines Typs hineinpacken. Eine optimale Lösung für ein konkretes Problem sieht z. B. so aus: http://lagrange.ime.usp.br/~lobato/packing/images/49_28_8_3_57.png.
Da hin zu kommen ist schon ziemlich aufwändig.
Such nach Best-Fit, First-Fit usw.
Dann habe ich noch http://de.wikipedia.org/wiki/Zuschnittsproblem gefunden. Lässt sich wohl auf mehrere Dimensionen übertragen.
die große fläche durch die fläche der kleinen rechtecke dividieren.
Ich will doch wissen WIE ich die Rechtecke ordnen muss, damit alle reinpassen.. Oder möglichst viele je nachdem..
Das mit den Rechtecken ist ja nur ein Beispiel... Es gibt ja auch kompliziertere varianten... Hast du noch nie so ein Rätsel gehabt, wo man drei- und vierecke hat und die passend zusammenlegen muss? Ich weiß schon dass man das alles durch ausprobieren hinkriegt aber die frage ist ja ob es einen Algorithmus gibt... Das Haus vom Nikolaus kriegt man ja auch durch ausprobieren hin, aber wenn es dann zu komplizierteren formen kommt, wendet man das eulerkreeisproblem an...
Es gibt ganze Forschungsgruppen, die sich damit beschäftigen und sogar eine europäische Wissenschaftlervereinigung (Esicup, http://www.euro-online.org/web/ewg/25/esicup-euro-special-interest-group-on-cutting-and-packing). Diese Art von Problemen gehören zum Bereich Operations Research, irgendwo zwischen BWL, Mathematik und Informatik. Mach dir also nix draus, wenn du nicht sofort eine einfache Lösung siehst!