Gestern habe ich nur Jigshaw Puzzle gespielt und mich irgendwie gefragt, was ein Algorithmus wäre, um es zu lösen.
Als menschliche Schritte, denen ich gefolgt bin:
Ich habe mich gefragt, was der effiziente Algorithmus wäre, um dieses Puzzle effizient zu lösen und welche Datenstruktur eine optimale effiziente Lösung bietet.
Danke.
Das Lösen von Problemen wie diesem kann täuschend kompliziert sein, besonders wenn keine Einschränkungen bezüglich der Größe und Komplexität des Puzzles gemacht werden.
Hier sind meine Gedanken über einen Ansatz zum Schreiben eines Programms, um ein solches Rätsel zu lösen.
Es gibt vier wichtige Informationen, die Sie einzeln und zusammen als Hinweise zum Lösen eines Puzzles verwenden können:
Welche Art von Informationen wird das Programm liefern? Nehmen wir an, dass jedes Puzzlestück ein kleines rechteckiges Bild mit Transparenzinformationen ist, um den Teil des Puzzlestücks zu identifizieren, der nicht rechteckige Kanten darstellt.
Daraus ist es relativ einfach, die vier Eckstücke zu identifizieren (in einer typischen Stichsäge). Diese hätten genau zwei Kanten mit flachen Konturen (siehe Konturkarte unten).
Als nächstes würde ich Informationen über die Form jeder der vier Kanten eines Puzzlestücks erstellen. Diese Informationen können verwendet werden, um eine Adjazenzmatrix zu erstellen, die angibt, welche Teile zusammenpassen.
Nun können wir diese Adjazenzmatrix beschneiden, um nur diejenigen Teile zu identifizieren, die in ihrer benachbarten Konfiguration glatte Farbübergänge haben. Dies ist etwas schwierig, da es einen Grad an Fuzzy-Anpassung erfordert - da nicht jede Pixel-zu-Pixel-Grenze notwendigerweise einen glatten Farbübergang haben wird.
Unter Verwendung der vier ursprünglich identifizierten Eckstücke sollten wir nun in der Lage sein, die Dimensionen und Positionen aller Teile des Puzzles zu rekonstruieren.
Eine geeignete Datenstruktur zum Darstellen von Kantenformen kann eine Konturkarte sein - im Wesentlichen ein Satz von ganzen Zahlen, die die inkrementellen Deltas im Abstand von der gegenüberliegenden Seite des Bildes zu dem letzten nicht transparenten Pixel auf jeder der vier Seiten des Bildes darstellen Puzzlespielstück. Übereinstimmende Teile sollten spiegelbildliche Konturkarten haben.Wenn man davon ausgeht, dass man sich nicht mit irgendwelchen Computer-Vision-Dingen beschäftigt, wären es sehr kleine Variationen bei der Suche nach dem gesamten Problemraum, d. h. versuchen jedes Stück, bis einer passt und es wiederholt. Die Hauptoptimierung würde nicht das gleiche Stück an der gleichen Stelle versuchen, wenn Sie wissen, dass es nicht passt. Seiten- / Eckstücke machen relativ wenige Teile aus und könnten wahrscheinlich bei keiner größeren Optimierung berücksichtigt werden.
Die Datenstruktur wäre wahrscheinlich eine Art Hash-Matrix, in der Sie schnell überprüfen können, ob Sie bereits ein Stück in einer Position ausprobiert haben.
Eine einfache Optimierung, die Computer Vision beinhaltet, besteht darin, Stücke an jeder Position nach dem Sortieren der Teile zu testen, indem man ihre durchschnittliche Farbe mit benachbarten Positionen vergleicht.
Das ist natürlich nur von der Spitze meines Kopfes.
Ich denke nicht, dass der menschliche Weg für eine Implementierung hilfreich wäre - ein Computer kann alle Teile viele Male pro Sekunde betrachten und ich sehe keinen (großen) Gewinn, wenn er die Teile in Ecken, Kanten und Innereien kategorisiert Stücke, vor allem, weil es nur drei Kategorien gibt und sie haben sehr unterschiedliche Größen.
Angesichts einer Reihe von Bildern aller Stücke würde ich versuchen, einen einfachen Deskriptor für jedes Stück oder jede Kante abzuleiten. Der Deskriptor muss Informationen über die grobe Form und die Farbe des Teils bzw. der vier Kanten enthalten. Bei einem Puzzle mit 1000 Stück gibt es 4000 Kanten und immer zwei müssen gleich sein (ignorieren Sie die Grenze des Puzzles). Folglich muss der Deskriptor 2000 Kanten unterscheiden können, die mindestens 11 Bits benötigen.
Wenn Sie ein Stück in ein 3 x 3-Check-Board-Muster mit neun Feldern teilen, erhalten Sie drei Farben pro Kante - mit acht Bits pro Kanal haben wir bereits 72 Bits. Ich habe zuerst vorgeschlagen, die Farbauflösung zu reduzieren, aber das scheint keine gute Idee zu sein - zum Beispiel könnte ein blauer Himmel wirklich von einer hohen Farbauflösung profitieren. Beachten Sie, dass das Berechnen der Farben wahrscheinlich erfordert, das Stück vom Hintergrund zu trennen und die Kanten an den horizontalen und vertikalen Achsen auszurichten.
In sehr gleichmäßigen Bereichen wie blauem Himmel werden die Farbinformationen wahrscheinlich nicht ausreichen, um gute Übereinstimmungen zu finden, und zusätzliche geometrische Informationen werden benötigt. Ich würde versuchen, die Form der Kante durch ihre Krümmung oder eine abgeleitete Kennzahl zu beschreiben. Vielleicht zehn bis zwanzig Punkte pro Kante. Dies hängt wahrscheinlich wieder von Hintergrundtrennung und Kantenausrichtung ab.
Schließlich kann der Computer den einfachen Teil tun - alle Paare von Kantenbeschreibern vergleichen und die besten Übereinstimmungen finden. Dieser Prozess sollte wahrscheinlich so gesteuert werden, dass er mehr lokal statt einfach bester zuerst wird, denn wenn Sie jemals eine Ecke gefunden haben (richtiges englisches Wort? Ich meine drei Stücke in einer L-Form.), Haben Sie zwei Kanten, die das Stück finden und finden Man kann früh zurückverfolgen, wenn keine gute Übereinstimmung gefunden werden kann (was auf einen zuvor gemachten Fehler oder ein hartes Puzzle hinweist).
Ich dachte daran, eine interessante Lösung zu finden, die die Kosten über eine Reihe von Schritten erhöht.
Teile alle Puzzleteile in zwei Teile. Testen Sie, ob sie zusammenpassen. Wenn nicht, versuchen Sie ein anderes Stück, das es vorher nicht gesehen hat. Wenn dies der Fall ist, legen Sie den Satz in einen richtigen Stapel. Wiederholen Sie dies, bis alle Sätze von zwei eine Übereinstimmung gefunden haben.
Vom richtigen Stapel kombinieren Sie die Menge von Zweien, um eine Menge mit Mengen von zweien zu machen, d. h. {{1,2}, {5,6}}. Sehen Sie, ob mindestens ein Puzzleteil aus einem Satz von zwei zu mindestens einem anderen Puzzleteil aus dem anderen Satz von zwei passt. Wenn nicht, versuchen Sie es mit einem anderen Satz von zwei, die es noch nicht gesehen hat. Wenn dies der Fall ist, kombinieren Sie die beiden Sätze in einem Satz von vier in der richtigen Ausrichtung mit dem Stück, das Sie zusammenfinden und fügen Sie das kombinierte Set in einen richtigen Stapel. Wiederholen Sie dies, bis alle Vierergruppen gefunden wurden.
Wiederholen Sie die Schritte bis zum letzten Problem, wo set n / 2 mit set n / 2 kombiniert wird.
Nicht positiv, wie hoch die Rechenzeit dafür wäre.
Tags und Links algorithm