[PYTHON] So erstellen Sie ein Programm zum Lösen des Rubik Cube ab PC Koshien 2014 Floppy Cube
Einführung
Ich bin Nyanyan, ein Hardware- / Software-Ingenieur, der die Konkurrenz der Speed Cubes genießt, die Rubic Cubes schnell lösen. Dieses Mal werde ich Problem des Floppy Cube von PC Koshien 2014 und von dort aus Rubik Cube usw. erklären. Ich werde die ** allgemeine Schreibmethode ** des Programms erklären, das das dreidimensionale Rätsel löst.
Ich mache derzeit einen Roboter, der (wahrscheinlich) am schnellsten einen 2x2x2-Rubikwürfel löst, und ich konnte dieses Problem mit dem Wissen lösen, das ich dort kultiviert hatte. Dieses Wissen ist für dieses Problem übertrieben, aber ich schreibe diesen Artikel, weil ich ihn gerne vorstellen würde.
Problemübersicht
Was ist ein Floppy-Würfel?
Es ist ein Puzzle wie auf dem Bild. Es wird manchmal "Rubik Cube mit nur einem Schritt" genannt, und das ist richtig. Der Punkt ist, dass es vier Achsen gibt (nach oben, unten, links und rechts), die durch Drehen um 180 Grad ausgerichtet werden können.
Laut der englischen Version des Wikis beträgt die Anzahl der Kombinationen $ 192 $ (was ziemlich viel ist, wenn man bedenkt, dass ein normaler Rubik-Cube $ 4,3 \ times10 ^ {19} $ ist. Gottes Zahl (bis zu $ N $, die Sie immer bekommen können, wenn Sie eine Hand haben) ist $ 8 $.
Problem
Der vollständige Text der Frage lautet hier. Der Farbzustand jeder Seite des Diskettenwürfels wird als Liste von Zahlen angegeben. Geben Sie daher bitte aus, wie viele Zeiger Sie von diesem Zustand aus ausrichten können. Mit einem Speicherlimit von $ 131072 $ KB und einem Zeitlimit von $ 1 $ Sekunden können Sie bis zu 30 Puzzle-Zustände erhalten (dh Sie müssen Antworten innerhalb von durchschnittlich $ 33 $ ms pro Puzzle ausgeben).
Der Zustand des Puzzles wird durch eine Liste von Zahlen angegeben. Diese Sequenz ist die Anzahl der Puzzle-Aufkleber (farbige Bereiche) $ 30 $ ($ 9 $ auf der Vorder- und Rückseite $ \ times 2 = 18 $, $ 3 $ an den Seiten $ \ times4 = 12 $ für insgesamt $ 30 $ ), Jede Farbe wird durch die Zahl $ 1,2,3,4,5,6 $ dargestellt. Von den Zahlen, die diese Farbe darstellen, ist $ 1,3 $ die Vorder- / Rückseite und die anderen die Seitenfarben.
Unter der Annahme, dass das Array, das diese Farbe darstellt, $ p $ ist, ist die Entsprechung zwischen den Zahlen (beginnend mit $ 0 $) und den Flächen von $ p $ wie in der folgenden Abbildung gezeigt.
Hier ist der vollständige Zustand im Beispielfall.
1 1 1 1 1 1 1 1 1 2 2 2 4 4 4 6 6 6 5 5 5 3 3 3 3 3 3 3 3 3
Die Eingabe erfolgt wie folgt:
Anzahl der eingegebenen Rätsel N.(<=30)
Leer getrennte Puzzle-Zustandssequenz p_1
p_2
...
p_n
Lösen wir das Problem.
Intuitive, aber weniger vielseitige Methode
Die erste Methode, die Sie möglicherweise entwickeln, ist eine einfache Simulation und eine Suche mit Breitenpriorität. Es ist weniger vielseitig, aber relativ einfach zu implementieren (obwohl das Simulieren der Rotation sehr mühsam ist).
Schätzen Sie den Rechenaufwand für ein Puzzle. Der nächste Schritt, den Sie für jeden Status ausführen können, besteht darin, entweder um 180 USD nach oben, unten, links oder rechts zu drehen, sodass 4 USD anfallen (danach werden wir dies ausarbeiten, um den Rechenaufwand weiter zu reduzieren). Und da Sie es für bis zu $ 8 $ von Hand bekommen können, ist der Rechenaufwand höchstens
Es wird sein. Selbst wenn 30 Puzzle-Zustände angegeben sind, beträgt der Berechnungsbetrag $ O (2,0 \ times10 ^ 6) $, was zeitlich zu sein scheint.
Der schwierige Teil dieser Methode ist nun die Implementierung der tatsächlichen Bewegung des Puzzles. Diesmal wird die Rotationsoperation durch Manipulieren der Eingabesequenz $ p $ selbst ausgedrückt. Diese Methode ist umständlich und nicht vielseitig, daher werde ich später eine andere Methode verwenden. Flop-Würfel verwenden immer eine Drehung von $ 180 $, sodass Sie sie implementieren können, indem Sie die beiden Aufkleber (Elemente in der Sequenz) richtig auswählen und austauschen. Das Ergebnis der Implementierung ist hier (Code siehe Link) .. Ich habe vorerst AC gemacht. Die Ausführungszeit betrug $ 0,35 $ Sekunden und die Speichernutzung betrug $ 14580 $ KB.
** Gute Punkte dieser Methode ** 1, Wenn Sie es implementieren können, ohne einen Fehler darüber zu machen, wo und wo ausgetauscht werden soll, ist der Rest nur eine Suche mit Breitenpriorität, daher ist es eine einfache Idee ** Schlechte Punkte dieser Methode **
- Die Implementierung, wo und wo getauscht werden soll, ist nicht wesentlich und faul (ich habe auch einen Fehler gemacht)
- Da es sich um eine Suche mit Breitenpriorität handelt, wird der Speicher unverändert verwendet
- Nicht vielseitig (das Schreiben eines Programms zum Lösen eines normalen Rubik-Würfels auf diese Weise macht die Rotationsimplementierung sehr faul)
Verbesserung der intuitiven Methode
Lassen Sie uns nun das vorherige Programm verbessern. Tatsächlich kann dieses Programm den Rechenaufwand leicht reduzieren.
** Drehen Sie nicht dieselbe Hand, die Sie kurz zuvor gedreht haben ** ** Zum Beispiel kurz vor dem Auf- und Abdrehen und dann nicht vor dem Aufdrehen ** ** Wenn du es nicht in 7 Zügen bekommst, ist die Antwort immer 8 (weil du es in 8 Zügen bekommen kannst) **
Durch die Implementierung dieser drei können Sie den Rechenaufwand reduzieren. Lassen Sie uns den Rechenaufwand für ein Puzzle genau schätzen. Betrachten Sie den Fall von maximal (8 Hände). (* Es ist nicht mathematisch streng. Tatsächlich wird der Rechenaufwand wahrscheinlich leicht zunehmen.)
Der Rechenaufwand im vorherigen Programm betrug $ O (6.6 \ times10 ^ 4) $, sodass ich ihn erheblich reduzieren konnte.
Das Ergebnis, das ich versucht habe, ist hier. Die Ausführungszeit betrug $ 0,08 $ Sekunden und der Speicher $ 6704 $ KB. Zeit und Speicher haben sich erheblich verbessert (obwohl der obige Code AC ist).
Denken Sie an eine generische Methode
Überblick
Obwohl es ein Nachteil ist, gibt es eine allgemeine Methode zum Schreiben von Rätseln wie folgt (diejenigen, die Rubik Cube mögen, wissen es vielleicht).
- Denken Sie an ** Teile ** anstelle von Aufklebern
- Konzentrieren Sie sich auf die ** Position ** und ** Ausrichtung ** der Teile
- Da das Puzzle aus Teilen verschiedener Formen besteht, ** beachten Sie die obige Methode für jede Form der Teile **
Denken wir konkret mit diesem Diskettenwürfel.
Es gibt drei Arten von Floppy-Cube-Teilen mit Aufklebern (farbig): "Ecke", "Kante" und "Mitte". Lassen Sie uns über jeden etwas mehr nachdenken.
Ecke Es bewegt sich, wenn es gedreht wird. Die Richtung (vorne und hinten) ändert sich beim Drehen
** Kante ** Es bewegt sich nicht, selbst wenn es gedreht wird (weil es sich um den Randteil dreht) Die Richtung (vorne und hinten) ändert sich beim Drehen
Center Bewegt sich auch bei Drehung nicht Die Richtung ändert sich auch bei Drehung nicht
In Anbetracht dieser Tatsachen können wir sehen, dass die folgenden drei Arten von Informationen alles sind, was benötigt wird, um den Zustand des Puzzles darzustellen.
- Positionen der vier Eckteile (CP = Eckpermutation)
- Ausrichtung jedes der vier Eckteile (CO = Eckenausrichtung)
- Ausrichtung jedes der vier Randteile (EO = Kantenausrichtung)
** Nachtrag Obwohl kein strenger Beweis erbracht wurde, scheint es, dass CO automatisch ausgerichtet wird, wenn CP ausgerichtet wird. In dem Artikel werde ich es so belassen, wie es unter Berücksichtigung von CO geschrieben wurde, aber ich werde auch einen Einreichungslink veröffentlichen, der CO nicht als zusätzlichen Hinweis betrachtet. ** **.
Während des eigentlichen Rotationsprozesses wird das Array gemäß den folgenden Regeln manipuliert.
Position Den Positionen der Eckteile (oben links, oben rechts, unten rechts, unten links) werden Zahlen (Namen) von 0 bis 4 zugewiesen. Nummerieren Sie die Eckteile selbst von 0 bis 4. Zum Beispiel bedeutet das i-te Element cp [i] des CP-Arrays cp, dass der Teil an Position i cp [i] heißt.
Richtung Nummerieren Sie die Eck- / Randteile von 0 bis 4. Zum Beispiel 0, wenn die Teile zur Vorderseite zeigen (Richtung zum Ausrichten) und 1, wenn die Teile zur Rückseite zeigen. Wenn beispielsweise das i-te Element co [i] des CO-Arrays 0 ist, zeigt der Teil an der Stelle i nach oben, und wenn er 1 ist, zeigt er nach hinten.
Implementierung
Es ist einfacher, Klassen zu verwenden, da die Zustände eines Puzzles durch mehrere Arrays dargestellt werden. Wenn Sie die der Position des Teils zugewiesene Nummer beispielsweise im Uhrzeigersinn einstellen, müssen Sie beim Schreiben des zu drehenden Prozesses nicht manuell herausfinden, wohin Sie sich bewegen müssen. Der Nachteil dieser Methode ist, dass es etwas umständlich ist, die Farbinformationen für jeden von Ihnen eingegebenen Aufkleber in drei Arrays zu konvertieren: CP, CO und EO.
Ergebnis
Der Code, den ich geschrieben habe, und das Ausführungsergebnis sind hier. Die Laufzeit betrug $ 0,12 $ Sekunden und die Speichernutzung betrug $ 6860 $ KB.
** Die Addition AC wurde auch für Programme durchgeführt, die CO nicht berücksichtigen. Der Einreichungslink lautet hier. Die Ausführungszeit betrug $ 0,09 $ Sekunden und die Speichernutzung betrug $ 6767 $ KB. ** **.
Reduzieren Sie den Rechenaufwand
Lassen Sie uns hier die Vielseitigkeit nutzen, die der Vorteil des zuvor erwähnten Allzweckcodes ist, um eine Vorberechnung durchzuführen, und ihn dann verwenden, um den Rechenaufwand zu beschneiden und zu reduzieren.
Das Beschneiden wird erreicht, indem die Suche gestoppt wird, wenn bekannt ist, dass die Anzahl der Züge nicht innerhalb der Acht des Gottes liegt. Berechnen Sie für jeden Zustand von CP, CO und EO im Voraus, wie viele Schritte verwendet werden können, um nur CP für CP, nur CO für CO und nur EO für EO vorzubereiten. Und während der Suche nach der Breitenpriorität
** Anzahl der bisher durchgeführten Schritte + Maximale Anzahl der Schritte, die erforderlich sind, um CP, CO und EO unabhängig voneinander auszurichten **
Wird berechnet und wenn dies die Anzahl von 8 Zügen Gottes überschreitet, wird die weitere Suche nach diesem Knoten (Zustand) gestoppt.
Das Übermittlungsergebnis, das dies implementiert, ist hier. Die Ausführungszeit betrug $ 0,16 $ Sekunden und die Speichernutzung betrug $ 6804 $ KB. ** Die Addition AC wurde auch für Programme durchgeführt, die CO nicht berücksichtigen. Der Einreichungslink lautet hier. Die Ausführungszeit betrug $ 0,13 $ Sekunden und die Speichernutzung betrug $ 6544 $ KB. ** **.
Diese Bereinigungsmethode ähnelt dieser Zeit, da sie eine Vorberechnung durchführt und die eindeutige Anzahl jeder der CP-, CO- und EO-Sequenzen bei jeder Suche berechnet.
- Die Anzahl der nächsten Züge, die von einem Knoten (Status) gedreht werden können, ist gering
- Die maximale Suchtiefe (dh Gottes Zahl) ist gering (klein).
Manchmal gibt es nicht viel Nutzen. Diesmal hat sich die Ausführungszeit etwas erhöht. Dieser Schnitt hat jedoch unermessliche Vorteile, wenn Sie versuchen, Rätsel zu lösen, die komplexer sind als Floppy-Würfel.
Reduzieren Sie die Speichernutzung-IDA *
Wir sprechen hier darüber, wie man mit der lächerlichen Speichernutzung umgeht, wenn man eine Suche mit breiter Priorität verwendet, wenn man ein anderes Rätsel löst, das kein Floppy-Würfel ist. Als ich beispielsweise eine Suche mit Breitenpriorität mit einem 2x2x2-Rubic-Cube durchführte, verbrauchte das von mir geschriebene Programm etwa 4 GB Speicher.
Was hier herauskommt, ist eine Suchmethode namens IDA *. Für Details ist der Artikel hier detailliert und empfohlen. Ich werde einen Teil dieses Artikels vorstellen.
In einem Wort lautet IDA * "Wiederholung der Tiefenprioritätssuche (DFS) mit begrenzter maximaler Tiefe bei zunehmender Tiefe". Der Mechanismus von IDA * besteht darin, den einmal durchsuchten Knoten zu vergessen. Wenn Sie den Knoten vergessen haben, können Sie Speicher freigeben.
Wenn in IDA * eine Suche mit Tiefenpriorität bis zu einer Tiefe von $ N-1 $ durchgeführt wird und keine Lösung gefunden wird, wird die maximale Tiefe auf $ N $ erhöht und die Suche von Anfang an neu gestartet. Auf diese Weise
- Das zurückgegebene Ergebnis ist immer der kürzeste Aufwand (die kürzeste Prozedur kann mit einer kleinen Änderung der Implementierung ausgegeben werden).
- Sehr geringe Speichernutzung
Es gibt einen Vorteil.
Bei flachen Knoten (Zuständen) wird dieselbe Suche jedoch viele Male wiederholt, sodass der Rechenaufwand geringfügig zunimmt. Da jedoch der Zustand des Puzzles als Exponentialfunktion in Bezug auf die Tiefe zunimmt, ist die Zunahme des Rechenaufwands nicht so groß. Lassen Sie uns in diesem Fall den Rechenaufwand genau schätzen. Angenommen, Sie befinden sich in einem Puzzle mit 7 Händen. Bei der Suche nach der Breitenpriorität betrug der Berechnungsaufwand etwa $ O (2.1 \ times10 ^ 3) $, wenn das Bereinigen ignoriert wurde. Und in IDA *
ist. Es gibt keinen großen Unterschied im Vergleich.
Das Ergebnis der Implementierung ist hier. Die Ausführungszeit beträgt $ 0,09 $ Sekunden und ist damit schneller als das vorherige Programm. Die Speichernutzung wurde von 6544 KB für Suchvorgänge mit Breitenpriorität auf 6044 KB reduziert. ** Die Addition AC wurde auch für Programme durchgeführt, die CO nicht berücksichtigen. Der Einreichungslink lautet hier. Die Ausführungszeit betrug $ 0,07 $ Sekunden und die Speichernutzung betrug $ 6036 $ KB. ** **.
Zusammenfassung
Vielen Dank, dass Sie so weit gelesen haben. Insbesondere ist die in der zweiten Hälfte eingeführte Methode eine sehr allgemeine Methode, für Floppy-Würfel jedoch zu übertrieben. Schreiben Sie auf jeden Fall ein Programm, das mit dieser Methode 2x2- und 3x3-Rubinwürfel löst, und erleben Sie die Vielseitigkeit dieser Methode. Für 2x2 schrieb ich Lass uns einen Roboter bauen, der den Zauberwürfel löst! 2 Algorithmen, 3x3 ist 7y2ns [Schreiben wir ein Programm zur Lösung des Rubikwürfels (Teil 2: IDA * -Suche)](https: / Wir empfehlen den Artikel /qiita.com/7y2n/items/24785b985e9c30862014).
Recommended Posts