JayN Geschrieben 2. März 2004 Geschrieben 2. März 2004 Hallo, ich versuche gerade für einen Freund eine Access-Anwendung zu erstellen, die folgendes machen soll: Es ist gegeben eine bestimmte Fläche. Weiterhin gibt es x Teilflächen, die auf dieser Fläche plaziert werden sollen. Von jeder Teilfläche können mehrere Exemplare existieren. Ziel ist es die Teilflächen so platzsparend wie möglich zu platzieren. Es müssen nicht alle Teile draufpassen. Die restlichen Teile werden dann in einer neuen Berechnung platziert. Nochmal zur Verdeutlichung als Beispiel: FLÄCHE A -> 200 cm x 600 cm TEILFLÄCHE A -> 20 cm x 20 cm, 50 Stück TEILFLÄCHE B -> 14 cm x 32 cm, 20 Stück TEILFLÄCHE C -> 15 cm x 18 cm, 17 Stück ... TEILFLÄCHE X -> 40 cm x 10 cm, 34 Stück Nun brüte ich über einem Algorhythmus und komme nicht wriklich voran. Mein Problem ist es, dass ich nicht von vornerein weiß, wieviele Teilflächen es gibt, die in die Berechnung miteinbezogen werden (d.h. es können mal A - G sein, mal aber auch A - Z oder mehr) und auch nicht eine maximale Anzahl eingrenzen kann. D.h. ich müsste die Berechnung irgendwie dynamisch ausrichten. Wahrscheinlich heißt das, dass irgendwie Code zur Laufzeit erstellt werden muss. Ich bin mir aber fast sicher, dass VBA das nicht kann. Aber vielleicht habe ich auch nur ein Brett vorm Kopf und es gibt eine einfache Lösung. Kann mir jemand einen Denkanstoss geben? Mit Dank im Voraus JayN Zitieren
Gast Geschrieben 3. März 2004 Geschrieben 3. März 2004 Vielleicht gibt es eine heuristische Methode. Was genau meinst Du mit "platzsparend" platzieren? Zitieren
dgr243 Geschrieben 4. März 2004 Geschrieben 4. März 2004 Ist noch was früh um da jetzt wirklich was zu produzieren, aber als Ansatz mal ein Versuch: 2 Variablen Eine kennzeichnet dir die Anzahl der versch. Teilflächen (A bis Z meinetwegen) und steuert eine for schleife, die von 1 bis maxAnzahl Teilflächen zählt. Innerhalb dieser Schleife liesst du die Anzahl der Teilflächen vom gerade behandelten Typ in die zweite Variable ein. Dann startest du eine do while Schleife innerhalb der schon for Schleife. In der do while Schleife packst du so lange Teilflächen auf deine vorhande Grundfläche, wie diese noch draupassen (mehrfache if .. else if) oder halt bis MaxAnzahlTeilflächeX erreicht ist. Abbruchbedingung für do...while ist dann ne Triggervariable. Ist die innere Schleife beendet gehts mit der nächsten Teilfläche (B ...) weiter. Zitieren
JayN Geschrieben 4. März 2004 Autor Geschrieben 4. März 2004 Original geschrieben von LoneGunman Was genau meinst Du mit "platzsparend" platzieren? Mit "platzsparend" platzieren meine Ãch, dass am Ende möglichst wenig freie Fläche übrig bleiben soll. Das Ziel der Anwendung ist es, die zur Verfügung gestellte Fläche optimal auszunutzen. Zitieren
JayN Geschrieben 4. März 2004 Autor Geschrieben 4. März 2004 Original geschrieben von dgr243 Ist noch was früh um da jetzt wirklich was zu produzieren, aber als Ansatz mal ein Versuch: 2 Variablen Eine kennzeichnet dir die Anzahl der versch. Teilflächen (A bis Z meinetwegen) und steuert eine for schleife, die von 1 bis maxAnzahl Teilflächen zählt. Innerhalb dieser Schleife liesst du die Anzahl der Teilflächen vom gerade behandelten Typ in die zweite Variable ein. Dann startest du eine do while Schleife innerhalb der schon for Schleife. In der do while Schleife packst du so lange Teilflächen auf deine vorhande Grundfläche, wie diese noch draupassen (mehrfache if .. else if) oder halt bis MaxAnzahlTeilflächeX erreicht ist. Abbruchbedingung für do...while ist dann ne Triggervariable. Ist die innere Schleife beendet gehts mit der nächsten Teilfläche (B ...) weiter. Diesen Ansatz habe ich auch schon in Betracht gezogen. Nur mit dieser Methode kann ich nicht rausfinden, wann die optimale Flächenausnutzung erreicht ist. Beispiel: Vielleicht passen bei 40 A-Teilen, noch 2 B-Teile dazu und dann ist Sense. Würde man aber ein A-Teil wegnehmen, so würde zu den 2 B-Teilen noch 1 C-Teil und 1 D-Teil passen und die größere Fläche ausfüllen. Gruß JayN P.S. Aber trotzdem schon mal danke für die Bemühungen. Zitieren
dgr243 Geschrieben 4. März 2004 Geschrieben 4. März 2004 Dann musst du halt in der von mir angesprochenenen do..while Schleife zusätzlich prüfen, ob eins der anderen Teile Flächenmässig passt. Dann muss die äussere for Schleife von der Gesamtzahl der Teilfläche abhängig gemacht werden. Hierzu liesst du dann halt vor der for Schleife ein wie viele Teilflächentypen es gibt (innere Schlefiensteuerung) und zusätzlich die Anzahl pro Teilflächentyp. Die for schleife läuft dann von 1 bis "summe alelr teilflächenanzahlen" In welcher Sprache du das hinterher codierst ist allerdings egal. Handelt sich ja um ein reines Algorhytmusproblem Zitieren
JayN Geschrieben 4. März 2004 Autor Geschrieben 4. März 2004 Ja, ja, dass es ein Algorythmus-Problem ist, ist mir klar. Habe ich ja auch in meinem Eingangsposting erwähnt. Ich habe es in dieses Forum gepostet, weil es halt mit VBA realisiert wird und weil ich dachte, dann schon auch sprachbezogene Tips zu erhalten. Ich werde, Deinen Lösungsansatz durchdenken. Danke für Deine Bemühungen. Gruß JayN Zitieren
dgr243 Geschrieben 4. März 2004 Geschrieben 4. März 2004 Zu der Prüfung ob ein Teil noch passt: Wenn die Teile rechteckig sind ist das ganze recht leicht if freiefläche < gebrauchteFläche pack das teil da rein else nächste teilegrösse testen sinnvollerweise sollte man die teile der grösse nach sortieren, dann spart man sich unter anderem ein paar fallunterscheidungen (wenn das kleinste teil nicht passt, passen alle anderen natürlich auch nicht ) Sind die Teile nicht rechteckig wird das ganze sehr schnell sehr kompliziert. Da ist dann halt die Frage ob Teil B in den nicht genutzten Flächeninhalt von Teil A passt und so weiter. Lässt sich natürlich auch realisieren wird bloss extrem komplex dann ... Zitieren
JayN Geschrieben 4. März 2004 Autor Geschrieben 4. März 2004 Nee, nee, die Teile sind schon rechteckig. Und mit den Berechnungsalgorhythmen habe ich auch nicht so die Probleme. Das Problem war die Berechnung auf eine unbestimmte Anzahl von Teilfläche zu übertragen. Wie ich dann die Flächen berechne und so weiter ist mir klar. Gruß JayN Zitieren
dgr243 Geschrieben 4. März 2004 Geschrieben 4. März 2004 Also: Keine weiteren Fragen Euer Ehren ? Zitieren
maxim_42 Geschrieben 8. März 2004 Geschrieben 8. März 2004 Zum Algorythmus: BruteForce scheidet aus, da mit angenommen 100 Teilen zu viele Möglichkeiten bestehen. Ich bin sicher es gibt "ausgefeilte" Suchstrategien. Eine Internetrecherche könnte lohnen. Ich bezweifele etwas, dass es eine Strategie abseits von BruteForce gibt, die mathematisch beweisbar, die platzsparenste Lösung garantiert. Hier muss man wahrscheinlich Kompromisse machen. Willst du die Lösung selbst erarbeiten, würde ich einen rekursiven Ansatz in Erwägung ziehen. Ein Rekursionsschritt versucht dabei, möglichst viele der grössten verfügbaren und passenden Teilstücke in ein gegebenes Rechteck zu plazieren. Die leer verbleibenden Rechtecke deiner Grundfläche behandelst du in darauffolgenden Rekursionsschritten. Nicht einfach...:beagolisc Zitieren
JayN Geschrieben 8. März 2004 Autor Geschrieben 8. März 2004 Original geschrieben von maxim_42 Nicht einfach...:beagolisc Das weiß ich... Danke für die Ansätze... Zitieren
Empfohlene Beiträge
Dein Kommentar
Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.