Angenommen, ich habe ein Raster aus Rechtecken mit verschiedenen Formen und Farben und möchte die Anzahl der Rechtecke reduzieren (einigermaßen nahe am Optimum ist in Ordnung, Optimal ist nicht erforderlich), um das gleiche Farblayout darzustellen.
Das obige Bild ist ein sehr vereinfachter Fall, und das Leerzeichen zwischen den Rechtecken dient nur zur Visualisierung - sie wären tatsächlich dicht gepackt.
Was ist ein Ansatz- oder Algorithmusname (gerne googeln), der mir dabei helfen kann?
Antworten:
Erstens können wir Ihre Quellrechtecke in Zellen in Ihrem zugrunde liegenden Raster konvertieren, um die Eingabe einheitlicher zu gestalten. (Effektives Rasterisieren des Problems)
Auf diese Weise können wir Optimierungen finden, die bei der direkten Arbeit mit den Quellrechtecken möglicherweise nicht offensichtlich sind - insbesondere, wenn mehrere Quellrechtecke geteilt werden müssen, um sie unterschiedlich zu kombinieren.
Als nächstes können wir verbundene Bereiche derselben Farbe mithilfe von Tiefen-First-Search- oder Flood-Filling-Algorithmen finden. Wir können jede verbundene Region (ein Polyomino ) isoliert betrachten - nichts, was wir einer anderen Region antun, muss diese beeinflussen.
Eigentlich wollen wir einen Weg finden, dieses Polyomino in Rechtecke zu zerlegen (leider geht es in der meisten Literatur, die ich finden kann, um das gegenteilige Problem: das Zerlegen von Rechtecken in Polyominos! Dies macht es schwierig, nach Leads zu suchen ...)
Eine einfache Methode besteht darin, horizontale Läufe benachbarter Quadrate zu langen, dünnen Rechtecken zu kombinieren. Dann können wir mit der obigen Zeile vergleichen und kombinieren, ob Start und Ende unseres Laufs übereinstimmen - entweder wenn wir jeden Lauf / jede Zeile beenden oder wenn wir jede Zelle als zum aktuellen Lauf hinzufügend betrachten.
Ich weiß noch nicht, wie nahe diese Methode dem Optimum kommt. Es scheint, dass es zu Problemen kommen kann, wenn eine Zeile, die noch nicht berücksichtigt wurde, eine andere Aufteilung vorschlägt als die Zeilen, die bisher gesehen wurden:
Das Erkennen, wann ein Lauf / Rechteck genau von Läufen oben und unten abgedeckt wird, das Aufteilen und Zusammenführen dieser Läufe löst diesen speziellen Fall, aber ich habe nicht untersucht, wie allgemein das Problem ist.
Ich habe mir auch Methoden angesehen, bei denen wir den Umfang des Polyominos durchlaufen und jedes Mal, wenn wir auf eine konkave Ecke stoßen, überqueren, aber dieser Ansatz erscheint mir fehleranfälliger. Um optimale Ergebnisse zu erzielen, müssen anscheinend Schnitte priorisiert werden, die zwei konkave Ecken verbinden, und Formen, die Vertiefungen enthalten, müssen speziell behandelt werden, sodass die Zeilenscanmethode den Vorteil der Einfachheit zu haben scheint.
Eine weitere Methode, die ich mir anschaue, besteht darin, den ersten Lauf in der oberen Reihe zu nehmen und ihn so weit wie möglich nach unten zu verlängern. Nehmen Sie dann den ersten Lauf in der obersten Reihe der verbleibenden Teile. Dies wird jedoch bei umgekehrten T-Formen ausgelöst, sodass es auch nicht optimal ist.
Ich habe das Gefühl, dass es wahrscheinlich eine Möglichkeit gibt, mithilfe der dynamischen Programmierung die optimale Aufteilung zu finden, aber ich habe sie noch nicht gefunden.
quelle