Das Rätsel "Musterfüllung mit Fliesen

Question

Bei der Programmierung eines Zufallsgenerators für ein kachelbasiertes Spiel bin ich auf ein interessantes Problem gestoßen. Ich habe einen Brute-Force-Solver dafür implementiert, aber er ist exponentiell langsam und definitiv ungeeignet für meinen Anwendungsfall. Ich bin nicht unbedingt auf der Suche nach einer perfekten Lösung, ich bin mit einer "gut genug" Lösung, die gut funktioniert, zufrieden.

Problemstellung:

Angenommen, Sie haben alle oder eine Teilmenge der folgenden Kacheln zur Verfügung (dies ist die Kombination aller möglichen 4-Bit-Muster, die den Richtungen rechts, oben, links und unten zugeordnet sind):

Alt-Text http://img189.imageshack.us/img189/3713/basetileset.png

Sie erhalten ein Raster, in dem einige Zellen markiert sind (wahr) und andere nicht (falsch). Dies könnte zum Beispiel durch einen Perlin-Rausch-Algorithmus erzeugt werden. Ziel ist es, diesen Raum mit Kacheln zu füllen, so dass es möglichst viele komplexe Kacheln gibt. Im Idealfall sollten alle Kacheln miteinander verbunden sein. Für einige Eingabewerte (verfügbare Kacheln + Muster) gibt es möglicherweise keine Lösung. Es gibt immer mindestens eine Lösung, wenn die obere linke, unverbundene Kachel verfügbar ist (d. h. alle Musterzellen können mit dieser Kachel gefüllt werden).

Beispiel:

Bilder von links nach rechts: Verfügbarkeit von Kacheln (grüne Kacheln können verwendet werden, rote nicht), Muster zum Füllen und eine Lösung

Alt-Text http://img806.imageshack.us/img806/2391/sampletileset.png + Alt-Text http://img841.imageshack.us/img841/7/samplepattern.png \= Alt-Text http://img690.imageshack.us/img690/2585/samplesolution.png

Was ich ausprobiert habe:

Meine Brute-Force-Implementierung probiert jede mögliche Kachel überall aus und verfolgt die gefundenen Lösungen. Schließlich wählt sie die Lösung, die die Gesamtzahl der von den einzelnen Kacheln ausgehenden Verbindungen maximiert. Die benötigte Zeit hängt exponentiell von der Anzahl der Kacheln im Muster ab. Die Lösung eines Musters mit 12 Kacheln dauert ein paar Sekunden.

Anmerkungen:

Wie ich schon sagte, ist Leistung wichtiger als Perfektion. Die endgültige Lösung muss jedoch korrekt verbunden sein (keine Kachel, die auf eine Kachel zeigt, die nicht auf die ursprüngliche Kachel zeigt). Um eine Vorstellung vom Umfang zu geben, würde ich gerne ein Muster von 100 Kacheln in etwa 2 Sekunden bearbeiten.

Answer 1

Für Instanzen mit 100 Kacheln könnte ein dynamisches Programm, das auf einer Zerlegung des Eingabegraphen basiert, meiner Meinung nach geeignet sein.

Zersetzung durch Schnitzen

In der Graphentheorie ist eine Carving-Zerlegung eines Graphen eine rekursive binäre Partition seiner Scheitelpunkte. Hier ist zum Beispiel ein Graph

1--2--3
|  |
|  |
4--5

und eine seiner Zerlegungen

     {1,2,3,4,5}
     /         \
  {1,4}        {2,3,5}
  /   \        /     \
{1}   {4}  {2,5}     {3}
           /   \
         {2}   {5}.

Die Breite einer Carving-Zerlegung ist die maximale Anzahl von Kanten, die eine ihrer Partitionen verlassen. In diesem Fall, {2,5} hat ausgehende Kanten 2--1 , 2--3 und 5--4 Die Breite ist also 3. Die Breite einer kd-Baum-Partition eines 10 x 10-Gitters ist 13.

Die Carving-Breite eines Graphen ist die Mindestbreite einer Carving-Zerlegung. Es ist bekannt, dass planare Graphen (insbesondere Untergraphen von Gittergraphen) mit n Scheitelpunkten eine Carving-Breite von O(n) haben, und die Big-O-Konstante ist relativ klein.

Dynamisches Programm

Bei einem n-Vertex-Eingangsgraphen und einer Carving-Zerlegung der Breite w gibt es eine O(2 w n)-Zeit-Algorithmus, um die optimale Kachelauswahl zu berechnen. Diese Laufzeit wächst schnell mit w, so dass Sie versuchen sollten, einige Beispieleingaben von Hand zu zerlegen, um eine Vorstellung von der zu erwartenden Leistung zu bekommen.

Der Algorithmus bearbeitet den Zersetzungsbaum von unten nach oben. X sei eine Partition, und F sei die Menge der Kanten, die X verlassen. Wir erstellen eine Tabelle, die jede der 2 |F| Möglichkeiten für das Vorhandensein oder Nichtvorhandensein von Kanten in F zur optimalen Summe auf X unter den angegebenen Bedingungen (-Unendlich, wenn es keine Lösung gibt). Zum Beispiel, mit der Partition {1,4} haben wir Einträge

{} -> ??
{1--2} -> ??
{4--5} -> ??
{1--2,4--5} -> ??

Für die Blattpartitionen mit nur einem Scheitelpunkt bestimmt die Teilmenge von F die Kachel vollständig, so dass es einfach ist, die Anzahl der Verbindungen einzutragen (wenn die Kachel gültig ist) oder andernfalls -unendlich. Für die anderen Partitionen müssen bei der Berechnung eines Tabelleneintrags alle verschiedenen Konnektivitätsmuster für die Kanten, die zwischen den beiden Kindern verlaufen, ausprobiert werden.

Nehmen wir zum Beispiel an, wir haben Stücke

                       |
.    .-    .-    -.    .
     |                 

Die Tabelle für {1} est

{} -> 0
{1--2} -> 1
{1--4} -> -Infinity
{1--2,1--4} -> 2

Die Tabelle für {4} est

{} -> 0
{1--4} -> 1
{4--5} -> 1
{1--4,4--5} -> -Infinity

Berechnen wir nun die Tabelle für {1,4} . Für {} , ohne den Rand 1--4 haben wir 0 Punkte für {1} (Eintrag {} ) plus Punktzahl 0 für {4} (Eintrag {} ). Mit Rand 1--4 haben wir die Punktzahl -Infinity + 1 = -Infinity (Einträge {1--4} ).

{} -> 0

Für {1--2} ist die Punktzahl 1 + 0 = 1 ohne 1--4 und 2 + 1 = 3 mit.

{1--2} -> 3

Fortsetzung folgt.

{4--5} -> 0 + 1 = 1 (> -Infinity = -Infinity + (-Infinity))
{1--2,4--5} -> 1 + 1 = 2 (> -Infinity = 2 + (-Infinity))

Am Ende können wir die Tabellen verwenden, um eine optimale Lösung zu finden.

Suche nach einer Zerlegung der Schnitzerei

Es gibt ausgefeilte Algorithmen, um gute Carving-Zerlegungen zu finden, aber vielleicht brauchen Sie sie nicht. Versuchen Sie es mit einem einfachen binären Raumaufteilungsschema.

Answer 2

Sehen Sie sich als Grundlage Folgendes an eine frühere Antwort, die ich bei der Suche gegeben habe . Hill-Climbing-Suchprogramme sind ein Werkzeug, das jeder Programmierer in seinem Arsenal haben sollte, da sie viel besser funktionieren als einfache Brute-Force-Löser.

Hier hat selbst ein relativ schlechter Suchalgorithmus den Vorteil, dass er keine illegalen Bretter erzeugt, was die zu erwartende Laufzeit erheblich verkürzt.

Answer 3

Ich glaube, ich habe eine bessere Idee. Ich habe es nicht getestet, aber ich bin mir ziemlich sicher, dass es schneller sein wird als eine reine Brute-Force-Lösung für große Zonen.

Erstellen Sie zunächst eine leere Menge (eine "Menge" ist eine Sammlung, die nur eindeutige Objekte enthält) von Knoten. Diese Sammlung wird verwendet, um festzustellen, welche Kacheln defekte Verbindungen haben, die repariert werden müssen.

Füllen Sie die Datenstrukturen, um das Brett mit den verfügbaren Figuren darzustellen, und verwenden Sie dabei die Figuren, die Sie nach Ihren persönlichen Kriterien für am geeignetsten halten. ohne Rücksicht auf die Korrektheit der Lösung . Dies wird mit ziemlicher Sicherheit zu einem ungültigen Zustand führen, aber für den Moment ist das in Ordnung. Iterieren Sie durch das Brett und finden Sie alle Kacheln, deren Verbindungen ins Leere führen. Fügen Sie sie der Menge der kaputten Spielsteine hinzu.

Durchlaufen Sie nun die Menge. Ändern Sie die Kacheln, auf die er sich bezieht indem sie die Zahl ihrer Verbindungen reduzieren (andernfalls könnte man in eine Endlosschleife geraten), so dass sie keine unterbrochene Verbindung haben, wobei die derzeit verfügbaren Stücke berücksichtigt werden. Überprüfen Sie ihre Nachbarn erneut, und wenn Sie Verbindungen zu anderen Steinen unterbrochen haben, fügen Sie diese ebenfalls zu den unterbrochenen Verbindungen hinzu.

Sobald die Menge der unterbrochenen Verbindungen leer ist, sollten Sie ein gut aussehendes Muster haben. Beachten Sie jedoch, dass es einen wichtigen Vorbehalt gibt: Es könnte dazu neigen, Muster zu stark zu vereinfachen, da in der Phase des "Reparierens" immer versucht wird, die Anzahl der Verbindungen zu reduzieren. Es kann sein, dass man Glück haben muss, um interessante Muster zu erhalten, da dies stark davon abhängt, welches Stück man als erstes auf die einzelnen Kacheln legt.