Dieser Artikel ist der 17. Tagesartikel von Speedcubing Adventskalender 2019. [Serie] Schreiben wir ein Programm zur Lösung des Rubik-Würfels (Teil 1) Wir werden fortfahren.
Im ersten Teil habe ich eine Klasse erstellt, die den Status / die Operation des Rubik-Würfels ausdrückt, und eine Methode zum Bedienen des Status geschrieben. Nachdem Sie den Würfel programmgesteuert drehen können, fahren wir mit der Suche fort.
Im zweiten Teil werden wir Round-Robin suchen, damit wir die Lösung des Rubik-Würfels noch in keinem Zustand finden können, aber auch kleine Rätsel wie Pyraminx und 2x2x2-Würfel können auf diese Weise gelöst werden.
In Bezug auf die Umgebung entspricht Python 3.6 oder höher dem ersten Teil.
Fortsetzung des ersten Teils eine Colaboratory-Notebook-Version des unten angezeigten Codes Ich habe mich auch vorbereitet. Wenn Sie also auf "[In Play Ground öffnen]" klicken und während der Ausführung fortfahren, müssen Sie keine Umgebung erstellen, und es wird einfacher.
Der Rubik-Würfel hat ungefähr 4,3 * 10 ^ 19 Zustände, und die kürzeste Anzahl von Zügen beträgt durchschnittlich ungefähr 18. Es ist bekannt, dass es im schlimmsten Fall in 20 Händen abgeschlossen ist (vgl. Https://www.cube20.org/).
Round-Robin ist eine Skala, die in einer realistischen Zeit nicht erreicht werden kann. Schreiben wir jedoch zunächst ein Programm, um den Rubik-Würfel mit Round-Robin zu lösen und ihn basierend darauf zu verbessern.
Aufgrund der großen Anzahl von Status im Rubik Cube verbraucht die Suche nach Breitenpriorität zu viel Speicher. Um den Rubik-Würfel im Round-Robin-Verfahren zu lösen, [Wiederholung der Suche nach vertiefender Tiefenpriorität](https://ja.wikipedia.org/wiki/%E5%8F%8D%E5%BE%A9%E6%B7%B1% E5% 8C% 96% E6% B7% B1% E3% 81% 95% E5% 84% AA% E5% 85% 88% E6% 8E% A2% E7% B4% A2) kann verwendet werden. Dies ist eine Methode zum Wiederholen einer Suche mit Tiefenpriorität (Suche nach Tiefenbeschränkungen), die die Suchtiefe (Lösungslänge) begrenzt, indem die Grenztiefe schrittweise erhöht wird.
Zuerst muss ich eine Funktion schreiben, um zu beurteilen, ob der Status, der im Suchprozess angezeigt wird, ein abgeschlossener Status ist. Wenn alle EO, CO, EP und CP vollständig sind, bedeutet dies, dass das Produkt vollständig ist. Daher habe ich eine Funktion geschrieben, um dies zu bestimmen.
def is_solved(state):
return (state.eo == [0] * 12 #Alle EOs sind verfügbar
and state.co == [0] * 8 #Alle CO ist verfügbar
and state.ep == list(range(12)) #Alle EPs sind verfügbar
and state.cp == list(range(8)) #Alle CPs sind verfügbar
)
Schreiben Sie eine Funktion, die sich auf den vorherigen Zug bezieht und zurückgibt, ob der Vorgang als nächster Zug verwendet werden kann.
In einem einfachen Fall ist es nicht möglich, dieselbe Oberfläche kontinuierlich zu drehen. (Wie "R'R2") Außerdem ist "U D U" dasselbe wie "U2 D", also ist es schlecht. Um dies zu vermeiden, legen Sie beim kontinuierlichen Drehen von Angesicht zu Angesicht die Reihenfolge in der Wörterbuchreihenfolge der Gesichtsnamen fest (wie die Reihenfolge "D U" ist gut, die Reihenfolge "U D" ist jedoch nicht möglich).
inv_face = {
"U": "D",
"D": "U",
"L": "R",
"R": "L",
"F": "B",
"B": "F"
}
def is_move_available(prev_move, move):
"""
Bestimmen Sie, ob die Operation als nächster Zug verwendet werden kann, indem Sie den vorherigen Zug berücksichtigen
-Drehen Sie nicht die gleiche Oberfläche kontinuierlich(e.g. R'R2 ist nicht möglich)
-Korrigieren Sie die Reihenfolge beim Drehen von Angesicht zu Angesicht(e.g.D U ist gut, U D aber nicht)
"""
if prev_move is None:
return True #Für den ersten Zug ist jede Operation möglich
prev_face = prev_move[0] #Die Oberfläche drehte sich zur Seite
if prev_face == move[0]:
return False #Gleiche Seite ist nicht möglich
if inv_face[prev_face] == move[0]:
return prev_face < move[0] #Von Angesicht zu Angesicht ist eine lexikalische Reihenfolge akzeptabel
return True
Ich habe es so geschrieben.
In start_search beginnt es bei 0 Zügen, ruft die Implementierung der Tiefenbegrenzungssuche auf, während die Anzahl der Züge schrittweise erhöht wird, und gibt sie zurück, wenn eine Lösung gefunden wird.
Das Argument "Tiefe" von "Tiefe_begrenzte_Suche" stellt die verbleibende Tiefe dar, und während diese verringert wird, wird die Suche rekursiv fortgesetzt, so dass bei Tiefe = 0 die Anzahl der aktuell durchsuchten Schritte erreicht wird.
Bereiten Sie einen Stapel vor, um die Lösung (Prozedur) zu verwalten, über die Sie nachdenken. Wenn Sie die Operation beim Eingeben des nächsten Knotens während des Suchvorgangs drücken und beim Beenden einfügen, befindet sich die aktuell gesuchte Lösung immer in diesem Stapel, und es ist nicht erforderlich, für jeden Status eine Lösung zu haben.
class Search:
def __init__(self):
self.current_solution = [] #Stapeln Sie das gesuchte Verfahren
def depth_limited_search(self, state, depth):
if depth == 0 and is_solved(state):
# is_Wenn gelöst True ist, ist es vollständig und gibt True zurück, da die Lösung gefunden wurde.
# depth==0 ist nicht erforderlich, aber Tiefe>Sie müssen die Entscheidungsfunktion nicht jedes Mal aufrufen, da Sie bereits wissen, dass 0 keine Lösung hat
return True
if depth == 0: #Gibt False zurück, wenn die Lösung nach Erreichen der Tiefe 0 nicht gefunden wird
return False
# depth=Suche weiter bis 0
prev_move = self.current_solution[-1] if self.current_solution else None #Bedienung vor
for move_name in move_names:
if not is_move_available(prev_move, move_name):
continue
self.current_solution.append(move_name)
if self.depth_limited_search(state.apply_move(moves[move_name]), depth - 1):
return True
self.current_solution.pop()
def start_search(self, state, max_length=20):
for depth in range(0, max_length): #Wiederholen Sie die Suche nach Tiefenbeschränkungen, während Sie die Anzahl der Schritte schrittweise von 0 erhöhen
print(f"# Start searching length {depth}")
if self.depth_limited_search(state, depth):
#Wenn eine Lösung gefunden wird, geben Sie sie an dieser Stelle zurück
return " ".join(self.current_solution)
return None
In dieser Implementierung kann in einer realistischen Zeit keine Lösung für gewöhnliches zufälliges Scramble gefunden werden, daher werde ich ein geeignetes 6-Hand-Scramble geben. Die Lösung wurde in 34 Sekunden gefunden. Die Lösung besteht natürlich darin, das Scramble in die entgegengesetzte Richtung zu drehen.
import time
scramble = "R U R' F2 D2 L"
scrambled_state = scamble2state(scramble)
search = Search()
start = time.time()
solution = search.start_search(scrambled_state)
print(f"Finished! ({time.time() - start:.2f} sec.)")
if solution:
print(f"Solution: {solution}.")
else:
print("Solution not found.")
Finished! (34.11 sec.)
Solution: L' D2 F2 R U' R'.
Das Beschneiden ist eine Technik, um die Suche zu beschleunigen. Mit Ihren Vorkenntnissen des Rubik-Würfels können Sie immer mehr aufrunden, wenn Sie es für sinnlos halten, weiter zu erforschen. Diese Art der sachkundigen iterativen Suche nach vertiefender Tiefenpriorität wird als IDA * -Suche bezeichnet (vgl. Https://en.wikipedia.org/wiki/Iterative_deepening_A *).
Was ist zum Beispiel, wenn Sie zum Zeitpunkt von "Tiefe = 1" keine Teile haben (1 Bewegung nach links)? Versuchen Sie, den Zauberwürfel manuell aus dem fertigen Zustand zu verschieben. Wenn Sie mit einem Zug nach links nicht mindestens vier Ecken und acht Kanten haben, können Sie dies bei Ihrem nächsten Zug nicht mehr tun. Daher ist es sinnlos, mit der Suche nach dem nächsten Zug fortzufahren, "Tiefe = 0".
In ähnlicher Weise können bei "Tiefe = 2" (2 Züge nach links) alle Ecken unterbrochen werden (z. B. "LR"). Wenn Sie jedoch keine 4 Kanten haben, bleiben 2 Züge übrig. Es gibt keine Möglichkeit, dies zu tun.
Wenn Sie mit "Tiefe = 3" (3 Züge nach links) an diesem Punkt nicht mindestens 2 Kanten haben, können Sie nicht mit 3 Zügen nach links fertig werden.
Lassen Sie uns das Beschneiden mit diesem Wissen implementieren.
def count_solved_corners(state):
"""
Zählen Sie die Anzahl der ausgerichteten Ecken
"""
return sum([state.cp[i] == i and state.co[i] == 0 for i in range(8)])
def count_solved_edges(state):
"""
Zählen Sie die Anzahl der ausgerichteten Kanten
"""
return sum([state.ep[i] == i and state.eo[i] == 0 for i in range(12)])
def prune(depth, state):
"""
Gibt True zurück, wenn es keinen Sinn macht, weiterzumachen
"""
if depth == 1 and (count_solved_corners(state) < 4 or count_solved_edges(state) < 8):
#Wenn weniger als 4 Ecken mit der verbleibenden 1 Hand ausgerichtet sind oder wenn weniger als 8 ausgerichtete Kanten vorhanden sind, werden sie nicht mehr ausgerichtet
return True
if depth == 2 and count_solved_edges(state) < 4:
#Wenn weniger als 4 Kanten mit den verbleibenden 2 Händen ausgerichtet sind, werden sie nicht mehr ausgerichtet
return True
if depth == 3 and count_solved_edges(state) < 2:
#Wenn weniger als 2 Kanten mit den verbleibenden 3 Händen ausgerichtet sind, werden sie nicht mehr ausgerichtet
return True
return False
class Search:
def __init__(self):
self.current_solution = []
def depth_limited_search(self, state, depth):
if depth == 0 and is_solved(state):
return True
if depth == 0:
return False
#Beschneidung(Nur das Hinzufügen dieser beiden Zeilen hat sich geändert)
if prune(depth, state):
return False
prev_move = self.current_solution[-1] if self.current_solution else None #Bedienung vor
for move_name in move_names:
if not is_move_available(prev_move, move_name):
continue
self.current_solution.append(move_name)
if self.depth_limited_search(state.apply_move(moves[move_name]), depth - 1):
return True
self.current_solution.pop()
def start_search(self, state, max_length=20):
for depth in range(0, max_length):
print(f"# Start searching length {depth}")
if self.depth_limited_search(state, depth):
return " ".join(self.current_solution)
return None
Die Suche, die 34 Sekunden dauerte, dauert jetzt weniger als 1 Sekunde. Wie Sie sehen können, ist das Beschneiden sehr mächtig.
scramble = "R U R' F2 D2 L"
scrambled_state = scamble2state(scramble)
search = Search()
start = time.time()
solution = search.start_search(scrambled_state)
print(f"Finished! ({time.time() - start:.2f} sec.)")
if solution:
print(f"Solution: {solution}.")
else:
print("Solution not found.")
Finished! (0.21 sec.)
Solution: L' D2 F2 R U' R'.
Allein damit können kleine Rätsel wie Pyraminx- und 2x2x2-Würfel in realistischer Zeit gelöst werden. Einige Enthusiasten möchten vielleicht Teile des Rubik-Würfels erkunden (z. B. Schritte überqueren oder 2x2x3-Blöcke ausrichten), aber wenn es kurz ist, ist dies der richtige Weg. Wenn Sie die erste Lösung finden und so ändern, dass sie nicht sofort zurückgegeben wird, können Sie nach mehreren Arten von Lösungen suchen.
Ich habe ein Programm geschrieben, um den Rubik-Würfel auf Umwegen zu lösen, und ich konnte ihn durch Beschneiden ein wenig beschleunigen, aber es ist weit davon entfernt, in kurzer Zeit aus irgendeinem Zustand eine Lösung zu finden.
Zwei-Phasen-Algorithmus wird häufig als Algorithmus verwendet, um die suboptimale Lösung des Rubik-Würfels in einer realistischen Zeit zu finden. Es ist eine Methode, die Lösung des Rubik-Würfels in zwei Phasen zu zerlegen und diese jeweils im Round-Robin-Verfahren zu lösen.
In Phase 1 können Sie den Zauberwürfel frei bewegen und in einen Zustand bringen, in dem er nur mit der Bewegung von <U, D, R2, L2, F2, B2> abgeschlossen werden kann. In Phase2 werden wir nur die Bewegungen von <U, D, R2, L2, F2, B2> verwenden, um es zum Abschluss zu bringen.
Phase 1 sind die schlechtesten 12 Züge, ungefähr 10 Züge, Phase 2 kann im schlimmsten Fall in 18 Zügen abgeschlossen werden, etwa 13 bis 14 Züge (vgl. Http://kociemba.org/math/symmetric.htm).
Je tiefer die Suchtiefe (Prozedurlänge) ist, desto exponentieller nimmt der Suchbereich zu. Daher sind etwa 18 Schritte erforderlich, um ein Round-Robin-Verfahren ohne Aufteilung der Phase durchzuführen, während nach 10 und 13 Zügen gesucht wird. Es wird schneller sein, wenn Sie es in Suchen unterteilen.
Es ist wichtig, dass der Zwei-Phasen-Algorithmus ordnungsgemäß in zwei Phasen zerlegt und in zwei Schritte unterteilt wird, die weniger Aufwand erfordern. Es ist jedoch auch wichtig, dass die Anzahl der Zustände in jeder Phase durch Teilen der Phase in zwei erhöht wird. Die Anzahl der Zustände kann reduziert werden, der Zustand kann indiziert werden und eine Zustandsübergangstabelle kann im Voraus erstellt werden, und die Tabelle zum Beschneiden kann auch im Voraus berechnet werden. Bei der Implementierung des zweiten Teils wird bei jeder Suche eine Instanz der State-Klasse erstellt, und dieser Teil ist tatsächlich langsam. Sie können dies verbessern, indem Sie den Status indizieren.
Eine weitere Funktion ist, dass Sie der optimalen Lösung immer näher kommen können, wenn Sie sich die Zeit für die Suche nehmen. Die Implementierung des Zweiphasenalgorithmus wird im zweiten Teil belassen.
Recommended Posts