c++.de :: Wie kann man die optimalen Kachelgrößen berechnen?

Gruum Mitglied 20:08:01 24.02.2012 Titel:

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?

SeppJ Moderator 20:42:48 24.02.2012 Titel:

Gruum schrieb:

Die Summe der Längen aller Kanten soll möglichst klein sein.

Auch wenn ich es jetzt nicht beweisen will, so würde ich doch mal intuitiv ganz stark vermuten, dass dies bedeutet, dass die Zahl der Kacheln möglichst klein sein muss. Daher wäre die optimale Breite der größte Teiler der Breite des großen Rechtecks und die optimale Höhe der größte Teiler von dessen Höhe.

Das ist natürlich jeweils die Breite bzw. die Höhe selbst. Ich nehme im folgenden mal an, dass du diese ausschließen möchtest.

Finden kannst du diese Zahl, indem du den kleinsten Primfaktor der Breite/Höhe suchst. Die gesuchte Breite/Höhe ist dann die Breite/Höhe geteilt durch diesen Primfaktor.
Beispiele:
Großes Rechteck 16x9

optimale Kachelgröße 8x3
Großes Rechteck 21x17

optimale Kachelgröße 7x1

knivil Mitglied 20:48:26 24.02.2012 Titel:

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.

Gruum Mitglied 00:57:15 25.02.2012 Titel:

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.

Jester Moderator 12:15:28 25.02.2012 Titel:

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

Michael E. Mitglied 12:28:14 25.02.2012 Titel:

Jester: Sehr schöner Gedankengang :live:

Jester Moderator 13:22:09 25.02.2012 Titel:

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.

SeppJ Moderator 13:41:42 25.02.2012 Titel:

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?

Jester Moderator 14:11:09 25.02.2012 Titel:

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.

Gruum Mitglied 02:38:20 26.02.2012 Titel:

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.