VBA / Flächenberechnung

[JayN]

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

[Gast]

Vielleicht gibt es eine heuristische Methode.

Was genau meinst Du mit "platzsparend" platzieren?

[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.

[JayN]

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.

[JayN]

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.

[dgr243]

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

[JayN]

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

[dgr243]

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 ...

[JayN]

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

[dgr243]

Also: Keine weiteren Fragen Euer Ehren ?

[maxim_42]

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

[JayN]

Original geschrieben von maxim_42

Nicht einfach...:beagolisc

Das weiß ich...

Danke für die Ansätze...