Maximale Rechtecke < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:45 Mi 04.01.2006 | | Autor: | Rapports |
| Aufgabe | Gegeben seien ein (großes) Rechteck [mm] $R=L \times W \subset \mathbb{R}^2$ [/mm] sowie kleinere schwarze Rechtecke [mm] $S_i \subset R$, $i \in I_s$ [/mm] , und weiße Rechtecke [mm] $B_i \subset R$, $i \in I_w$ [/mm].
a) Gesucht sind alle maximalen Rechtecke [mm] $R_j =l_j \times w_j \subset R$, $j=1, 2, ...$ [/mm] mit Mindestgröße [mm] $l_0 \times w_0$ [/mm] , die kein [mm] $S_i$ [/mm] enthalten, d.h. [mm] $R_j \bigcap int S_i = \emptyset$ [/mm] für alle [mm] $i \in I_s$ [/mm] , und höchstens [mm] $k$ [/mm] der [mm] $B_i$ [/mm] , [mm] $i \in I_w$ [/mm] , d.h. [mm] card$\{i \in I_w: R_j \bigcap int B_i \not= \emptyset\}\leq k$ [/mm] , wobei [mm] $k$ [/mm] die Werte 0, 1, ... annehmen kann.
b) Gesucht sind zwei Rechtecke [mm] $R_1$ [/mm] und [mm] $R_2$ [/mm] mit [mm] $R_1 \bigcap int R_2 = \emptyset$ [/mm] , die weder schwarze noch weiße Rechtecke enthalten und deren Gesamtfläche maximal ist.
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
ich sitze zur Zeit an einer Aufgabe in Optimierung, für die ich einen kleinen Denkanstoss benötige.
Am besten erst einmal die Aufgabenstellung:
Gegeben seien ein (großes) Rechteck [mm] $R=L \times W \subset \mathbb{R}^2$ [/mm] sowie kleinere schwarze Rechtecke [mm] $S_i \subset R$, $i \in I_s$ [/mm] , und weiße Rechtecke [mm] $B_i \subset R$, $i \in I_w$ [/mm].
a) Gesucht sind alle maximalen Rechtecke [mm] $R_j =l_j \times w_j \subset R$, $j=1, 2, ...$ [/mm] mit Mindestgröße [mm] $l_0 \times w_0$ [/mm] , die kein [mm] $S_i$ [/mm] enthalten, d.h. [mm] $R_j \bigcap int S_i = \emptyset$ [/mm] für alle [mm] $i \in I_s$ [/mm] , und höchstens [mm] $k$ [/mm] der [mm] $B_i$ [/mm] , [mm] $i \in I_w$ [/mm] , d.h. [mm] card$\{i \in I_w: R_j \bigcap int B_i \not= \emptyset\}\leq k$ [/mm] , wobei [mm] $k$ [/mm] die Werte 0, 1, ... annehmen kann.
b) Gesucht sind zwei Rechtecke [mm] $R_1$ [/mm] und [mm] $R_2$ [/mm] mit [mm] $R_1 \bigcap int R_2 = \emptyset$ [/mm] , die weder schwarze noch weiße Rechtecke enthalten und deren Gesamtfläche maximal ist.
Gesucht ist letztlich ein Algorithmus um dieses Problem zu lösen. Alle Rechtecke (das große. weiße und schwarze) werden zu Beginn eingelesen. Dafür werden die Koordinaten des Punktes links unten und des Punktes rechts oben eingegeben.
Man kann sich das große Rechteck also so vorstellen, daß L in die x- Richtung und W in die y-Richtung eines Koordinatensystems geht. Bisher hatte ich mir überleg in der selben Größe wie das Rechteck Matrizen zu generieren und links unten beginnend in einer Matrix jeweils den Abstand nach oben zum nächsten schwarzen Rechteck, in der nächsten Matrix den Abstand nach rechts zum nächsten schwarzen Rechteck und genau das selbe noch einmal für die Abstände zu weißen Rechtecken zu berechnen.
Als nächstes würde ich die maximalen Rrechtecke versuchen zu berechnen, dabei würde ich beginnend links unten zu erst eine Länge von einem Kästchen annehmen, dann wäre das Rechteck genauso lang, wie in meiner Matrix der Abstand zum nächsten schwarzen Rechteck ist. Dann würde ich eine Länge von 2 wählen, die Höhe wäre dann das Minimum aus bisheriger Höhe und der Höhenangaben die zu diesem 2. Kästchen gehört. Dies würde ich bis zu der Länge machen, die ich in meiner Matrix als Abstand in x-Richtung zum nächsten schwarzen Rechteck für das erste Feld habe. Damit habe ich alle Rechtecke, die ihren Ursprung im ertsen feld haben und keine schwarzen Rechtecke beinhalten.
Dies kann ich dann für all meine Felder machen. Am Ende müßte ich noch prüfen, welche dieser erhaltenen Rechtecke bereits vollständig in einem anderen enthalten sind und somit gleich gestrichen werden können.
Nun weiß ich jedoch nicht, in wieweit das maximal gemeint ist. Muß ich für die möglichen Rechtecke jeweils den Flächeninhalt berechnen und das Maximale heraussuchen?
Zusätzlich weiß ich auch nicht, wie ich die Anzahl an weißen Rechtecken am Besten zählen soll. Habe ich das richtig verstanden, daß jedes Rechteck maximal [mm] $k$ [/mm] weiße Rechtecke enthalten kann?
Bei der b) ist mir leider auch nicht klar, wie ich die lösen muß.
Als erstes kann ich ja nur die Rechtecke verwenden, für die gilt [mm] $k=0$ [/mm]. Mir stellt sich dabei auch die Frage, daß es ja sein kann, daß ich in a) nur die Rechtecke behalten habe, die zu dem jeweiligen Startpunkt die maximale Fläche haben. Damit muß ich ja aber nicht zwangsweise zu einem optimalen Ergebnis bei b) kommen, oder? Muß ich mir also doch alle jemals berechneten Rechtecke merken? Wenn ja, wie kann ich das am Besten programmieren? Ich kann mir für diese Aufgabe eine Programmiersprache meiner Wahl aussuchen.
Oder ist meine Herangehensweise vielleicht sogar im Kompletten zu umständlich und es gibt eine Bessere?
Ich hoffe ich konnte mich wenigstens ein bißchen verständlich ausdrücken!
Danke schon mal im Voraus!
Liebe Grüße Christiane
|
|
| |
|
Hallo Christiane,
also sicherlich handelt es sich um Fragestellungen der Art, wie sie in der
algorithmischen Geometrie ausfuehrlich behandelt werden, so dass Dir vielleicht
ein Blick in entsprechende Literatur (einfuehrende Lehrbuecher zur alg. Geometrie gibt es
hinreichend viele, zB das von Rolf Klein, den ich hier natuerlich zu nennen quasi verpflichtet bin  ) oder auch in Buecher ueber Datenstrukturen und Algorithmen
helfen koennte - zumindest, wenn es darum geht, einen moeglichst effizienten
Algorithmus zu finden.
Ein AdHoc-Ansatz:
Ohne die Aufgabenstellung genau durchdacht zu haben, wuerde ich vielleicht
sowas tun wie die [mm] S_i [/mm] nach den Koordinaten zu sortieren und so schnell die
infragekommenden Bereiche finden, sozusagen in einem SweepLine-Verfahren erst
entlang der x-Achse (frau/man betrachtet die jeweiligen x-Koord. von linken
unteren und rechten oberen Punkten der [mm] S_i, [/mm] dann fuer jeden solchen Wert in y-Richtung ein Intervall suchen, das von keinem [mm] S_i [/mm] geschnitten wird und entlang
dieses Intervalls maximal weit nach rechts gehen, so dass nicht mehr als k der B's
geschnitten werden.
Noch was anderes:
Verdaechtig ist es ein bisschen, wenn Du schreibst, Ihr macht sowas in Optimierung.
Koennte man das Problem nicht auch als ein - zB quadratisches - Programm
schreiben ? Vielleicht sogar als lineares Programm ?
Ich schau da mal, ob das gehen koennte und meld mich spaeter evtl. nochmal.
Vorerst viele Gruesse
und viel Erfolg !
Mathias
|
|
|
|
