Laden...

Möglichst großes Quadrat in einem Minenfeld

Erstellt von vbtricks vor 16 Jahren Letzter Beitrag vor 16 Jahren 3.996 Views
vbtricks Themenstarter:in
205 Beiträge seit 2006
vor 16 Jahren
Möglichst großes Quadrat in einem Minenfeld

Salut,

vielleicht kann mir ja jemand bei meinem Problem weiterhelfen.

Ich habe ein Minenfeld, wobei ich die Koordinaten der Minen als Liste habe. Nun möchte in diesem Feld ein möglichst großes Quadrat finden, sodass keine der Minen auf diesem Quadrat ist.

Meine erste Idee war, dass ich mir jeweils zwei Punkte nehme und dann ein Rechteck einpasse, das die beiden Punkte und die rechte untere Ecke auf dem Rand hat. Anschließend prüfe ich, ob die anderen Punkte auf diesem Rechteck liegen. Tun sie das schneide ich rechts und unten von dem aktuellen Rechteck entsprechend viel abschneide. Das liefert aber keine korrekten Resultate.

Warum das so ist, ist mir klar, allerdings stehe ich wieder ohne konkrete Lösungsidee da. Im Anhang habe ich mal das Projekt mit obiger (falscher) Idee.

Danke im Voraus,

Stefan

2.921 Beiträge seit 2005
vor 16 Jahren

Bist Du sicher, dass du nach dem größten Quadrad und nicht nach dem größten RECHTECK suchst!?

Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.

vbtricks Themenstarter:in
205 Beiträge seit 2006
vor 16 Jahren

Salut,

ja, da bin ich mir sicher. Im Endeffekt soll das größte Quadrat rauskommen. Im Algorithmus selbst verwende ich erst mal Rechtecke, das ist richtig.

Ich habe jetzt doch noch eine Idee gehabt. Und zwar prüfe ich, ob die X- oder die Y-Koordinate des aktuellen Testpunkts im aktuellen Rechteck weiter entfernt von der linken oberen Ecke des Rechtecks entfernt ist. Anschließend "werfe" ich nur den Teil des aktuellen Rechtecks hinter der größeren Koordinate weg.

Rein optisch sieht das schon ganz gut aus. Muss mir da aber noch Gedanken über die Korrektheit machen. Außerdem ist das ganze noch kubisch vom Aufwand, das würde ich gerne noch reduzieren. Für weitere Ideen wäre ich deshalb dankbar.

Ein aktualisiertes Beispiel findet sich im Anhang.

Stefan

49.485 Beiträge seit 2005
vor 16 Jahren

Hallo vbtricks,

erweitere Mal deine Paint-Handler um folgenden Code. Ich denke diese Hilfslinien werden dich auf den richtigen Weg führen. Im Prinzip muss deine Aufgabe dann sein, die sich optisch ergebenden Rechtecke zu größeren Rechtecken zusammenzufassen, solange kein Punkt störend im Weg steht.


foreach (PointF curPoint in points) {
   e.Graphics.DrawLine(Pens.Gray, 0, curPoint.Y, 300, curPoint.Y);
   e.Graphics.DrawLine(Pens.Gray, curPoint.X, 0, curPoint.X, 300);
}

herbivore

PS: Was auch noch zu bedenken ist: Es kann mehr als ein maximales Quadrat geben.

vbtricks Themenstarter:in
205 Beiträge seit 2006
vor 16 Jahren

Salut,

hm, laufzeittechnisch ist das aber doch eher schlechter, oder? Rechtecke bekomme ich dann (#Punkte + 1)^2 viele.

Anschließend kommt jedes dieser Rechtecke als obere linke Kachel in Betracht.

Und dann muss ich noch prüfen, wie viele Rechtecke ich dran basteln kann, d.h. ich gehe jede Zeile unterhalb der Kachel durch und schaue, wie weit ich nach rechts komme.

Das ist im worst case doch dann aber auch nochmal n2, macht nach meiner Milchmädchenrechung n4.
Lass mich da aber natürlich auch gern korrigieren...

Stefan

49.485 Beiträge seit 2005
vor 16 Jahren

Hallo vbtricks,

ich denke, mit n3 wird man auch nicht hinkommen. Ich glaube also, dass dein n3 Ansatz nicht 100%ig korrekt ist.

herbivore

1.271 Beiträge seit 2005
vor 16 Jahren

Hallo vbtricks,

Mich stört eines: Es gibt auch gedrehte Quadrate! Ist es Absicht, dass du die ausgeklammert hast? Ich weiß, das wär extrem viel Aufwand, das auch zu machen. Ob es nötig ist, kommt natürlich ganz auf das an, was du erreichen willst (was mich übrigens brennend interessieren würde!!! Also wenn du es sagen darfst/willst, dann tu dir keinen Zwang an 😉).

Gruß,
Thomas

A wise man can learn more from a foolish question than a fool can learn from a wise answer!
Bruce Lee

Populanten von Domizilen mit fragiler, transparenter Außenstruktur sollten sich von der Translation von gegen Deformierung resistenter Materie distanzieren!
Wer im Glashaus sitzt, sollte nicht mit Steinen werfen.

vbtricks Themenstarter:in
205 Beiträge seit 2006
vor 16 Jahren

Salut,

@herbivore
Es reicht ein einziges Gegenbeispiel um den Algorithmus zu vernichten, die Korrektheit zu beweisen ist schon um einiges schwieriger. Deshalb hatte ich ja geschrieben, dass es "optisch" ganz gut aussieht (wobei man natürlich über diese Formulierung streiten kann).
Um mir das Testen zu erleichtern, habe ich die Start- und Stop-Buttons eingebaut, die per Timer immer einen Zufallspunkt in das aktuelle größte Quadrat setzen. Wenn der Algorithmus nicht korrekt wäre, würde ich ja dann irgendwann noch eine größere freie Fläche sehen, die der Algorithmus nicht findet.

Dass es mehrere gleichgroße größte Quadrate geben kann, stört mich nicht, ich benötige nur eines. Auch interessieren mich nur achsenparallele Quadrate. Hätte ich vielleicht dazuschreiben sollen...

Die Aufgabe habe ich übrigens aus einer Aufgabensammlung zur theoretischen Informatik. Ist aber ganz interessant, sich mal mit Problemen zu beschäftigen, die auf den ersten Blick leicht zu lösen aussehen, aber eine effiziente Lösung dann einiges an Überlegung benötigt.
War mein Praxisbeispiel so weit aus der Luft gegriffen? 😉

Stefan

49.485 Beiträge seit 2005
vor 16 Jahren

Hallo vbtricks,

meinen Einwand mit dem n^3 nehme ich zurück. Insgesamt muss ich feststellen, dass ich das Problem nicht richtig durchdacht hatte. Insbesondere hatte ich nicht richtig wahrgenommen/berücksichtigt, dass du als linke obere Ecke einen Mix aus zwei Punkten verwendest und nicht die Punkte selbst. Ich stimme dir zu, dass deine verbessere Version es "optisch" gut aussieht.

Die Komplexität kannst du senken, in dem du in der Schleife


foreach (Point leftPoint in myPoints) { ...

ersetzt durch


Dictionary <int, bool> dictLeft = new Dictionary <int, bool> ();
foreach (Point leftPoint in myPoints) {
   dictLeft [leftPoint.X] = true;
}
foreach (int iX in dictLeft.Keys) { ...

Analog für topPoint (wobei man die Dictionaries natürlich nur einmal zu Anfang berechnen muss).

Dann ist die Komplexität nicht mehr bezüglich der Zahl der Punkte, sondern bezüglich der Zahl der unterschiedlichen X-Koordinaten kubisch (analog für Y-Koordinaten). Unterschiedliche Punkte gibt es potentiell 90.000, unterschiedliche X-Koordinaten nur 300. Damit sollte sich die Komplexität bezüglich der Zahl der Punkte von n3 auf n2 drücken lassen.

Für die Reduzierung der inneren Schleife kann ich mir vorstellen, dass man hier über Sortierung was machen kann. Wenn man also zwei Listen von Punkten hat, einmal sortiert nach der X- und einmal sortiert nach der Y-Koordinate. Dann müsste es möglich sein, die Liste nicht stumpf durchzugehen, sondern anhand dieser beiden Listen, den Punkt, der das aktuelle Quadrat am meisten beschneidet (z.B. durch binäre Suche) schneller zu finden.

Wenn das wirklich klappt, dann wäre man bei n*log (n). Und das wäre insgesamt schon eine sehr deutliche Verbesserung.

herbivore

vbtricks Themenstarter:in
205 Beiträge seit 2006
vor 16 Jahren

Salut,

die Idee mit den Dictionaries ist natürlich in dem Fall, dass wie im Beispiel nur endlich viele X/Y-Koordinaten vorkommen, eine deutliche Verbesserung.

Bei der binären Suche nach dem Beschneidungspunkt kann ich dir nicht ganz folgen. Als Beispiel mal (Bild siehe Anhang)
(70,70)
(100,260)
(250,110)
(250,120)
(240,240)
(200,260)
(150,260)

sortiert nach X
(70,70)
(110,260)
(150,260)
(200,260)
(240,240) <<< beschränkt am meisten
(250,110)
(250,120)

sortiert nach Y
(70,70)
(250,110)
(250,120)
(240,240) <<<
(110,260)
(150,260)
(200,260)
Da sehe ich nicht, wie ich groß abkürzen könnte. Ich könnte jeweils nach der notwendigen Startkoordinate suchen (d.h. der Eintrag mit dem minimalen X/Y-Wert, sodass er im potentiellen Rechteck enthalten ist). Aber im schlimmsten Fall muss ich dann ja immer noch n-Einträge durchgehen.

Wenn ich für die Anzahl der Koordinaten keine endliche Menge habe (also z.B. die Menge der rationalen Zahlen, werde ich wohl kaum Optimierungsmöglichkeiten bei meinem Ansatz haben? Die Dictionaries helfen mir da ja nicht weiter, da ich z.B. alle Punkte auf einer Geraden haben könnte, folglich hat dann mindestens eines der beiden Dictionaries für jede Dimension n Elemente, im schlimmsten Fall beide.

Stefan

49.485 Beiträge seit 2005
vor 16 Jahren

Hallo vbtricks,

der Vorschlag mit der binären Suche bzw. der Sortierung war auch erstmal nur eine Idee. Mindestens hätte die Sortierung doch den Vorteil, dass man Punkte, die mit mindestens einer Koordinate links bzw. oberhalb des gerade untersuchten, linken oberen Punktes liegen durch binäre Suche schnell ausschließen kann. Wenn man von diese Stelle in der Liste an beginnt, einschränkende Punkte anzuwenden, dann sollte man automatisch tendenziell die Punkte zu erst probieren, die das Quadrat möglichst stark einschränken. Sobald man ein eingeschränktes Quadrat gefunden hat, kann man wiederum per binärer Suche schnell feststellen, welche Punkte kein zusätzliche Einschränkung bringen, weil mindestens eine Koordinate rechtes oder unterhalb des gerade betrachteten Quadrats liegt. Ist die Idee jetzt etwas klarer?

herbivore

vbtricks Themenstarter:in
205 Beiträge seit 2006
vor 16 Jahren

Salut,

ja, das ist natürlich richtig. Wobei ich dann im worst case vermutlich auch wieder auf O(n) komme. In der Praxis steckt mit deinem Ansatz aber noch einiges an Potential im Problem 😉.

Stefan