Berechnung von optimierter Matrix

[yamukud]

Schönen Guten Mittag die Herren und Damen,

Aufgabenstellung:

Gegeben: Fenstergröße, Anzahl der Elemente

Gesucht: Größe eines Elements

Praktisches Beispiel: Auf eine Form sollen Buttons vorgegebener Größe platziert werden. Ist der Platz der Form erschöpft soll die Größe der Buttons so angepasst werden, dass möglichst viele Buttons auf diese Form passen.

Jemand so etwas schonmal gemacht? Ist sicher mit Iteration machbar, aber die Hitze lässt mich nicht richtig denken.

Vielen Dank schon einmal,

Lars

[flashpixx]

Ist sicher mit Iteration machbar, aber die Hitze lässt mich nicht richtig denken.

Das sieht nach Hausaufgaben aus, deshalb der Hinweis: Hausaufgaben sind für Dich und ohne, dass Du eine Lösungsidee hier postest, wirst Du wohl auch keine Hilfe bekommen. Ein Forum ist nicht dafür gedacht, dass wir Deine Aufgaben machen und die Ausrede "es ist die Hitze" zählt nicht, stell Dir nen Ventilator daneben und lass Dir ne Idee einfallen, die mehr als nur "Iteration" beinhaltet....

[yamukud]

Ich betrachte diesen Kommentar als persönlichen Affront.

Aus der Zeit der Hausaufgaben bin ich ein wenig heraus.

Bevor ich aber etliche Zeit mit einem fakultativen Feature verbringe, das alles andere als nötig ist und zu einem komplexen Programm gehört, bei dem andere Dinge wichtiger sind höre ich mich gerne einmal um, ob es da bereits einen klugen Algorithmus gibt. Es gibt Menschen, sag ich dir, die kommen nicht so eben zB auf den Reed-Solomon-Code, aber das sind dann wohl auch nur Hausaufgaben.

Meine Frage war freundlich und offen gestellt, ein solcher "geh weg hier"-Kommentar ist weder angebracht noch nötig.

Lars

Nachtrag: Die typische Hausaufgabenstellung habe ich, da es passend und knapp erschien, hier adaptiert. Diese habe ich aber aus meinem Problem erstellt.

Nachtrag2: Im Übrigen bin ich der Meinung, dass du die Schwierigkeit der Fragestellung noch nicht erfasst hast. Da alles variabel außer die Anzahl und die Größe ist, gibt es für mich erstmal nur das Prinzip der Näherung (Iteration).

Bearbeitet 13. Juli 2010 von yamukud

[Klotzkopp]

Praktisches Beispiel: Auf eine Form sollen Buttons vorgegebener Größe platziert werden.

Sind die Buttons gleich groß? Dürfen sie gedreht werden?

Ist der Platz der Form erschöpft soll die Größe der Buttons so angepasst werden, dass möglichst viele Buttons auf diese Form passen.

Beliebig angepasst? Oder gibt's da irgendwelche Beschränkungen, wie minimale Größe oder Beibehalten des Seitenverhältnisses?

[flashpixx]

Nachtrag2: Im Übrigen bin ich der Meinung, dass du die Schwierigkeit der Fragestellung noch nicht erfasst hast. Da alles variabel außer die Anzahl und die Größe ist, gibt es für mich erstmal nur das Prinzip der Näherung (Iteration).

Da sich um ein binäres LP handelt, würde ich Dir zu einem Simplex-Algorithmus raten, Nach dem Dualitätsprinzip kannst Du es entsprechend als Maximierungsproblem auffassen, das Du als Minimierungsproblem formulierst. Nach Deiner Aussage "variable außer Anzahl & Größe" kann die Lösung schon keine Näherung sein, denn dann müsstest Du auch "halbe" Buttons zulassen.

Bearbeitet 13. Juli 2010 von flashpixx

[yamukud]

Vielen Dank für eure Antworten.

Die Buttons sollen alle gleich groß sein, der Text soll aber lesbar bleiben (> untere Schranke), außerdem gibt soll es einen proportionalen Abstand zwischen den Buttons geben

Unter dieser Voraussetzung ist auch das Seitenverhältnis irrelevant.

Da sich um ein binäres LP handelt, würde ich Dir zu einem Simplex-Algorithmus raten, Nach dem Dualitätsprinzip kannst Du es entsprechend als Maximierungsproblem auffassen, das Du als Minimierungsproblem formulierst. Nach Deiner Aussage "variable außer Anzahl & Größe" kann die Lösung schon keine Näherung sein, denn dann müsstest Du auch "halbe" Buttons zulassen.

Aaaah danke Da war der Knoten. Durch die halben Buttons ist es tatsächlich ein Optimierungsalgorithmus und kein Approximationsalgorithmus, das war meine eigentliche Fragestellung.

Das Ausformulieren sollt ihr natürlich nicht machen.

Vielen Dank,

Lars

Nachtrag: Meine Eingangsfrage war zu ungenau formuliert, von daher verstehe ich die Reaktion nun besser.

Nachtrag2:

und die Ausrede "es ist die Hitze" zählt nicht, stell Dir nen Ventilator daneben und lass Dir ne Idee einfallen, die mehr als nur "Iteration" beinhaltet....

stößt dennoch ein wenig auf, da auch das Simplex-Verfahren ein Iterationsverfahren ist. Bearbeitet 13. Juli 2010 von yamukud

[flashpixx]

Nachtrag2: stößt dennoch ein wenig auf, da auch das Simplex-Verfahren ein Iterationsverfahren ist.

Da gebe ich Dir recht, nur im Simplex steckt ja noch etwas mehr drin, als "nur" eine Iteration. Evtl solltest Du nur bedenken, dass der Simplex-Algo O(n^3) ist, d.h. wenn Du die GUI relativ oft refreshen musst, solltest Du Dir evtl was anderes überlegen, als die optimale Anordnung immer neu zu berechnen. Greedy und Backtracking wären auch noch eine Idee, wobei ich Backtracking nicht verwenden würde.

Ja nachdem musst Du das Rad auch nicht neu erfinden, denn um das ganze mal generell zu lösen würde ich Zimpl empfehlen, wo man evtl auch das direkt selbst in den Code einbauen kann.

Auch wenn ich Dich sehr hart auf die "Problemformulierung" hin gewiesen habe, freue ich mich, dass ich Dir nen kleinen Stups geben konnte.

[yamukud]

Zimpl hört sich sehr interessant an, vielen Dank dafür.

Meine jetzige Lösung, die erstmal nur einen einfachen Optimierungsalgorithmus und keinen Simplex beinhaltet (sowas hatte ich am Anfang im Blick, kannte Simplex aber nicht), reicht für meine Zwecke aber erst einmal aus, da die Buttons nur einmal refresht werden wenn nicht genug Platz da ist (Erzeugung von zu vielen beim Start des Programms oder beim Skalieren des Fensters).

Und wie gesagt, das Rad wollte ich eben nicht neu erfinden, somit dieser Thread

Greedy wollte ich eben nicht verwenden, da die Lösung nicht optimal ist und ich den Algorithmus für einen der schlechten halte. (Auch wenn er bei diesem Problem aufgrund des hohen Toleranzbereichs anwendbar wäre)

Die Meinung zu Backtracking teile ich aufgrund der Zeitintensivität.

Gracie,

Lars

[Bubble]

Bevor ich aber etliche Zeit mit einem fakultativen Feature verbringe, das alles andere als nötig ist und zu einem komplexen Programm gehört, bei dem andere Dinge wichtiger sind höre ich mich gerne einmal um, ob es da bereits einen klugen Algorithmus gibt.

Klar. Ist es ein Programm, dass kommerziell entwickelt wird? Dann solltest Du auch angeben, wie viel Dir eine Beratung wert ist, wenn Du selbst schon mal möglichst keine Zeit damit verbringen möchtest, und auf Angebote hoffen.

Praktisches Beispiel: Auf eine Form sollen Buttons vorgegebener Größe platziert werden. Ist der Platz der Form erschöpft soll die Größe der Buttons so angepasst werden, dass möglichst viele Buttons auf diese Form passen.

Ich nehme an, es gibt noch ein paar Nebenbedingungen bezüglich der Schaltflächen-Abmessungen.

[yamukud]

Entschuldigung, da habe ich eine Antwort noch übersehen.

Das Programm wird nicht kommerziell vertrieben.

Dass eine untere Schranke existiert ist klar, wie eben schon gesagt.

Da es gar nicht sooo viele Werte sind, die möglich sind, iteriere ich jetzt sogar dreckig (Probiere mal den jetzigen Wert-1%, passts?, wenn nicht, mach nochmal, ...)

Liebe Grüße,

Lars

[flashpixx]

Ich muss mich noch korrigieren: Das Simplex-Verfahren ist ein O(2^n) Algorithmus und kein polynomieller, wie ich es vorher geschrieben hatte. Bei realen Problemen, ist aber die Laufzeit doch sehr gut

Das mit dem -1% ist klar. Der Simplex-Algo ist recht robust, man kann zeigen, dass wenn sich eine Lösung in einer gewissen Schranke verändert, das nicht zu einer Änderung der gesamten Lösung führt. Diese Infos kann man aber recht einfach aus dem Tableau entnehmen.

Naja, das "sooo viel" lass ich mal etwas im Raum stehen, denn es müssten 2^n Möglichkeiten sein, die man theoretisch hat. bei 2^10 oder 2^100 ist das schon ein Unterschied.