Wie kann man die optimalen Kachelgrößen berechnen?
-
knivil schrieb:
Bug: "die gleiche Höhe wie sein linker Nachbar ". Kacheln an der linken Seite haben keinen linken Nachbarn. D.h. duerfen beliebig sein, sofern das Constraint "Flaecheinhalt nicht verletzt wird. Gleiches gilt fuer obere Kacheln. Daraus folgt eine quadratische Kachelung mit Anpassung an den Raendern wird am besten sein.
Das Problem ist, dass es so wenig Quadratzahlen gibt. Aber egal es müssen ja nicht alle Zeilen gleich hoch und nicht alle Spalten gleich breit sein, also kann man jede x_i-te Spalte/Zeile um eins kleiner oder größer machen.
Naja,ich weiss jetzt wie ich es mache. Auch wenn der Flächeninhalt nicht immer genau eingehalten wird, das ist sowieso nicht in jedem Fall möglich und darum ging es mit auch nicht wirklich.
-
Gruum schrieb:
Gegeben ist ein Rechteck. Nun will ich das Rechteck mit kleineren Rechtecken, deren Flächeninhalte in einem bestimmten Bereich liegen, ausfüllen. Jedes Rechteck muss die gleiche Breite wie sein oberer Nachbar und die gleiche Höhe wie sein linker Nachbar haben. Die Summe der Längen aller Kanten soll möglichst klein sein. Alle vorkommenden Zahlen (Flächeninhalte und Seitenlängen) müssen natürliche Zahlen sein.
Wie mach ich das am besten?Das heißt doch, dass die ränder der kacheln ein gitter induzieren, das dir dein rechteck zerschneidet. Außer an den rändern (aber wir können links mit rechts und oben mit unten zusammenpacken) ist jede kante dieses gitters rand von zwei kacheln. So eine ganze gitter-zeile/spalte hängt natürlich nur vom großen rechteck ab. Um die zahlen zu minimieren mußt du also so wenig zeilen und spalten wie möglich haben (das impliziert SeppJs Vermutung, dass man wenig kacheln will).
-
Jester: Sehr schöner Gedankengang
-
Damit lässt sich die frage denke ich, sekbst wenn nur bestimmte werte für breiten und höhen zugelassen sind mit einem dynamischen programm lösen. Wenn nicht alle Kombinationen von höhen und breiten für kacheln zugelassen sind (z.b. 3*5 ist zu groß, es geht aber 3*4 und 2*6, weil zum beispiel die fläche kleiner ist) wirds etwas kniffliger sollte aber immer noch gehen. Man kann zeitgleich auchnnoch die tatsächlich abgedeckte fläche minimieren, um den überschuß kleinzuhalten. Das ist zwar alles nur pseudo-polynomiell (polynomiell in der grösse der großen box) sollte aber vermutlich reichen.
-
Kann Gruum mal das Problem genau beschreiben? Wenn keine vollständige Abdeckung gesucht ist, dann teilt man eben die Fläche in 4 Kacheln (oder 2, falls zugelassen ist, dass die Kacheln auch gleiche Breite exklusiv oder Höhe haben können wie das große Rechteck und rundet ab. Dann bleibt eben eine kleiner Rand unabgedeckt, falls die Breite/Höhe nicht durch Zwei teilbar war. Wenn man die Kantenzahl möglichst klein halten will und Überdeckung egal ist, fügt man ein 1x1 Rechteck ein und hat dann eben ganz viel Restfläche.
Wie sind diese verschiedenen Faktoren zu bewerten? Was ist das genaue Ziel?
-
Ich denke es ist eher gemeint, dass notfalls ein überstand vorhanden sein darf, man aber das rechteck schon komplett erwischen muß und weiters die maximalen längen beschränkt sind.
-
Also das sind jetzt mal meine Gedanken dazu:
Es gibt Zeilen und Spalten. Es müssen nicht alle Zeilen gleich hoch sein und nicht alle Spalten gleich breit, aber es gibt einen vorgegebenen Flächeninhalt den jedes, durch die Zeilen und Spalten entstandene, Rechteck mit einer gewissen Toleranz haben muss.
Die Summe der Längen aller Kanten ist dann am kleinsten wenn die Anzahl der Zeilen plus die Anzahl der Spalten am kleinsten ist. Das ist dann der Fall, wenn die Rechtecke möglichst quadratisch sind.
Die Lösung wird wohl so aussehen, dass man
n Spalten mit der Breite b,
m Spalten mit der Breite b+1,
o Zeilen mit der Höhe h und
p Zeilen mit der Höhe h+1 nimmt.
b*h und (b+1)*(h+1) müssen beide die Bedingung für den Flächeninhalt erfüllen (falls n,m,o und p nicht 0 sind).
Für eine bestimmte Anzahl von Zeilen und Spalten kann man jetzt einfach n,m,o,p,b und h berechnen und dann gucken ob die Bedingung für den Flächeninhalt erfüllt ist. Man könnte jetzt die Anzahl der Zeilen und Spalten systematisch durchgehen und gucken welche Werte das beste Ergebnis liefern. Oder man könnte einfach raten und z.B. die Anzahl der Zeilen und Spalten ausgehend von einem Quadrat mit dem vorgegebenen Flächeninhalt berechnen.
-
Gruum schrieb:
Die Summe der Längen aller Kanten ist dann am kleinsten wenn die Anzahl der Zeilen plus die Anzahl der Spalten am kleinsten ist.
Das bezweifle ich.
P.S. : Uch bin immer noch nicht sicher, was überhaupt das Problem ist. Denn wenn ich dein Problem richtig verstanden habe (und mehr Erklärung als der Einstiegsbeitrag kam nicht), dann steht in der allerersten Antwort schon die Lösung. Also: Warum habe ich da das falsche Problem gelöst?
-
SeppJ schrieb:
Gruum schrieb:
Die Summe der Längen aller Kanten ist dann am kleinsten wenn die Anzahl der Zeilen plus die Anzahl der Spalten am kleinsten ist.
Das bezweifle ich.
Da hast du recht, das gilt nur, wenn das große Rechteck ein Quadrat ist. Die Summe der Kanten ist proportional zur Anzahl der Zeilen mal Breite des großen Rechtecks plus Anzahl der Spalten mal Höhe des großen Rechtecks. Aber das hatte ich so eigentlich auch gedacht, ich wusste es nur nicht.
SeppJ schrieb:
P.S. : Uch bin immer noch nicht sicher, was überhaupt das Problem ist. Denn wenn ich dein Problem richtig verstanden habe (und mehr Erklärung als der Einstiegsbeitrag kam nicht), dann steht in der allerersten Antwort schon die Lösung. Also: Warum habe ich da das falsche Problem gelöst?
Bei deinem ersten Beitrag gehst du davon aus, dass jedes kleine Rechteck exakt gleich groß sein muss, das wird aber nicht gefordert. Und den vorgegebenen Flächeninhalt für die kleinen Rechtecke beachtest du nicht.
-
Und was misfällt dir an meiner Lösung?
