[PYTHON] Lassen Sie uns einen Roboter bauen, der den Zauberwürfel löst! 2 Algorithmus
Was ist dieser Artikel?
Dieser Artikel ist serialisiert ** Lassen Sie uns einen Roboter bauen, der den Zauberwürfel löst! Es ist Teil der Artikelsammlung mit dem Namen **. Klicken Sie hier für das ganze Bild
- Übersicht
- Algorithmus (dieser Artikel)
- Software (unveröffentlicht)
- Hardware (unveröffentlicht)
GitHub ist hier.
Ich habe auch ein Video mit dem gleichen Inhalt wie dieser Artikel erstellt.
Klicken Sie hier für eine Videosammlung zu dieser Artikelsammlung.
Inhalt dieses Artikels
Dieses Mal werde ich den Algorithmus des Programms erklären, das die kürzeste Prozedur (für den Roboter) zum Lösen des 2x2x2-Rubikwürfels ausgibt. Der Algorithmus führt "Breitenprioritätssuche" und "IDA *" ein. Lassen Sie uns vorher kurz auf die Idee der vollständigen Suche eingehen.
Was ist diesmal "Gesamtsuche"?
Die vollständige Suche ist buchstäblich eine ** Methode zum Durchsuchen aller Muster **. Überprüfen Sie bei einem 2x2x2-Rubikwürfel alles, wenn Sie {U, U ', U2, F, F', F2, R, R ', R2} aus einem bestimmten Zustand drehen, und überprüfen Sie vorher, ob nicht alle Es ist eine Suchmethode wie das Drehen und Überprüfen aller {U, U ', U2, F, F', F2, R, R ', R2} auf alle Muster (streng genommen 2 Schritte). Es gibt jeweils 6 Schritte, um nach den Augen zu suchen, aber darüber werde ich später sprechen. Die hier angezeigten U, F und R werden als Rotationssymbole bezeichnet. Einzelheiten entnehmen Sie bitte der Übersicht.
Lassen Sie uns hier eine kleine Figur zeichnen.
Wenn der Zustand des Würfels durch einen Kreis (Knoten) dargestellt wird und eine Hand aus diesem Zustand durch einen Balken (Seite) gedreht wird, wiederholen Sie das Drehen aller Hände, die von einem bestimmten Zustand und diesem Baum aus durchsucht werden können Eine solche Zahl entspricht. In der Abbildung wurde es übersprungen, aber im Fall von 2x2x2 für jeden Zustand
- Der erste Zug ist {U, U ', U2, F, F', F2, R, R ', R2} 9 Züge
- Ab dem zweiten Zug, wenn der vorherige Zug einer von {X, X ', X2}, {U, U', U2, F, F ', F2, R, R', R2} \ ist 6 Züge von {X, X ', X2} (\ ist das Symbol der Differenzmenge)
Da Sie so viel drehen können, haben Sie 9 Seiten vom ersten Knoten (Wurzel) und 6 Seiten voneinander als vom ersten Knoten.
Außerdem wird die Anzahl der Schritte, die nach dem zweiten Zug gesucht werden müssen, verringert. Wenn Sie beispielsweise X X 'drehen, entspricht dies dem Nicht-Drehen. Wenn Sie XX drehen, entspricht dies X2. Wenn Sie X X2 drehen, entspricht dies X'. Wenn zwei Zeiger derselben Art von Rotationssymbolen in einer Reihe stehen, wird dies immer aufgehoben oder durch ein anderes Rotationssymbol ersetzt.
Suche nach Breitenpriorität
"** Suche nach Breitenpriorität " ist eine typische Methode der vollständigen Suche zusammen mit " Suche nach Tiefenpriorität **". Die Knoten in der vorherigen Abbildung sind zur Erläuterung hier absichtlich nummeriert. Wie Sie sehen können (?) Die Reihenfolge der Untersuchung jedes Knotens unterscheidet sich zwischen der Suche nach Tiefenpriorität und der Suche nach Breitenpriorität. Lassen Sie uns jeden kurz erklären.
Suche nach Breitenpriorität
Die Suche nach der Breitenpriorität ist in der Abbildung dargestellt
1->1.1->1.2->1.3->...1.9->1.1.1->1.1.2->...1.1.6->1.2.1->1.2.2->...1.3.1->...1.1.1.1->...
Es ist eine Suchmethode zum Suchen. was zur Hölle? Ich denke, also fügen wir der vorherigen Abbildung einen Pfeil hinzu.
Das ist richtig, es ist eine Suche, die allmählich tiefer wird.
In Bezug auf die Zahlen in der Figur wird die Anzahl der zu durchsuchenden L.M.N. allmählich zunehmen. Mit anderen Worten, je mehr Sie sich von Anfang an bewegen, desto später werden Sie durchsucht.
Diese Suchmethode wird häufig verwendet, um ** die kürzeste Route zu finden **. Dies liegt daran, dass "je mehr Hände Sie drehen, desto später werden Sie gesucht", "wenn Sie in kurzer Zeit eine Lösung finden können, wird die Suche beendet, wenn Sie sie finden."
Wenn Sie mehr wissen möchten, empfehle ich den Artikel hier.
Tiefenprioritätssuche
Die Suchreihenfolge der Tiefenprioritätssuche ist wie folgt.
1->1.1->1.1.1->1.1.1.1->...1.2->1.2.1->1.2.1.1->...1.2.2->1.2.2.1->...
Lassen Sie uns auch eine Zahl setzen.
Die Tiefenprioritätssuche ist eine Suchmethode, die vorerst zum tiefsten (längsten) Ort sucht und, wenn sie nicht funktioniert, zu einem flacheren Ort zurückkehrt (versuchen Sie, die zuletzt gedrehte Hand in eine andere Hand zu ändern). ist.
Mit anderen Worten, wenn Sie einen Knoten mit der letzten Nummer N betrachten, z. B. L.M.N. für jede Tiefe, haben Sie bereits den L.M.-Knoten (N-1 oder weniger) betrachtet.
Diese Suchmethode ist relativ einfach zu implementieren, endet möglicherweise schneller als die Suche mit Breitenpriorität (wenn Sie nach einer nicht optimalen Lösung suchen (nicht kürzeste Prozedur)) und benötigt relativ wenig Speicher, daher möchte ich vorerst eine vollständige Suche durchführen. Ich benutze es oft wenn.
Für weitere Informationen empfehlen wir hier und hier.
Löse den Zauberwürfel mit der Suche nach Breitenpriorität
Dieses Mal möchte ich die kürzeste Anzahl von Schritten finden, daher verwende ich die Suche nach Breitenpriorität. Lassen Sie es uns vorerst implementieren. Wenn Sie Python hier nicht lesen können, lesen Sie einfach die Kommentare und hören Sie sie sich an.
from collections import deque
from copy import deepcopy
from time import time
move_candidate = ["U", "U2", "U'", "F", "F2", "F'", "R", "R2", "R'"] #Kandidat für die Rotation
#Würfelklasse in diesem Artikel nicht unbedingt erforderlich(Ich werde in der Software Edition ausführlich erklären)
class Cube:
def __init__(self):
self.Co = [0, 0, 0, 0, 0, 0, 0]
self.Cp = [0, 1, 2, 3, 4, 5, 6]
self.Moves = []
#Rotationsverarbeitung CP
def move_cp(self, num):
surface = [[0, 1, 2, 3], [2, 3, 4, 5], [3, 1, 5, 6]]
replace = [[2, 0, 3, 1], [3, 2, 1, 0], [1, 3, 0, 2]]
idx = num // 3
res = Cube()
res.Cp = [i for i in self.Cp]
for i, j in zip(surface[idx], replace[num % 3]):
res.Cp[i] = self.Cp[surface[idx][j]]
res.Moves = [i for i in self.Moves]
res.Moves.append(num)
return res
#Rotationsverarbeitung CO
def move_co(self, num):
surface = [[0, 1, 2, 3], [2, 3, 4, 5], [3, 1, 5, 6]]
replace = [[2, 0, 3, 1], [3, 2, 1, 0], [1, 3, 0, 2]]
pls = [2, 1, 1, 2]
idx = num // 3
res = Cube()
res.Co = [i for i in self.Co]
for i, j in zip(surface[idx], replace[num % 3]):
res.Co[i] = self.Co[surface[idx][j]]
if num // 3 != 0 and num % 3 != 1:
for i in range(4):
res.Co[surface[idx][i]] += pls[i]
res.Co[surface[idx][i]] %= 3
res.Moves = [i for i in self.Moves]
res.Moves.append(num)
return res
#Ändern Sie tatsächlich die Zustandsanordnung des Puzzles entsprechend der Rotationsnummer
def move(self, num):
res = Cube()
res.Co = self.move_co(num).Co
res.Cp = self.move_cp(num).Cp
res.Moves = [i for i in self.Moves]
res.Moves.append(num)
return res
#Rotationsnummer in Rotationssymbol konvertieren
def num2moves(self):
res = ''
for i in self.Moves:
res += move_candidate[i] + ' '
return res
#Erstellen Sie eine eindeutige Nummer aus dem cp-Array
def cp2i(self):
res = 0
marked = set([])
for i in range(7):
res += fac[6 - i] * len(set(range(self.Cp[i])) - marked)
marked.add(self.Cp[i])
return res
#Erstellen Sie eine eindeutige Nummer aus dem Co-Array
def co2i(self):
res = 0
for i in self.Co:
res *= 3
res += i
return res
#Der Zustand des Puzzles(R U R' U')3(Diese 3 ist R U R.' U'Bedeutet, dass dreimal gedreht wurde)Staat drehte sich um
#Beginnen Sie mit einem Durcheinander von Rätseln und erkunden Sie diese, bis sie vollständig sind
puzzle = Cube()
#CP ist eine Abkürzung für Corner Permutation. Repräsentiert die Position von Eckteilen.
puzzle.Cp = [1, 0, 2, 5, 4, 3, 6]
#CO ist eine Abkürzung für Corner Orientation. Zeigt die Ausrichtung der Eckteile an.
puzzle.Co = [2, 1, 0, 0, 0, 0, 0]
#Der Zustand des Puzzles im gelösten Zustand
solved = Cube()
solved.Cp = [0, 1, 2, 3, 4, 5, 6]
solved.Co = [0, 0, 0, 0, 0, 0, 0]
#Zeitmessung
strt = time()
#Suche nach Breitenpriorität
que = deque([puzzle])
while que:
#Status aus der Warteschlange entfernen
status = que.popleft()
#L die Nummer des letzten Schritts_Setzen Sie es in mov
l_mov = -1 if not status.Moves else status.Moves[-1]
#Liste der Schritte, die als nächstes ausgeführt werden müssen
t = (l_mov // 3) * 3
lst = set(range(9)) - set([t, t + 1, t + 2])
for mov in lst:
#Bewegen Sie das Puzzle tatsächlich
n_status = status.move(mov)
#Ich habe die Antwort gefunden!
if n_status.Cp == solved.Cp and n_status.Co == solved.Co:
print(n_status.num2moves())
print(time() - strt, 'Sekunden')
exit()
#Wenn keine Antwort gefunden wird, fügen Sie der Warteschlange den Status hinzu
que.append(n_status)
Es ist ein bisschen lang gewesen, aber das Hauptthema ist knapp unter den letzten 30 Zeilen. Davon abgesehen ist es eine Klasse zum Ausdrücken von Würfeln. Ich werde im Software-Bereich ausführlich darauf eingehen.
In diesem Programm verschlüsseln Sie das Bild ((RUR'U ') 3, 3 bedeutet, RUR'U' 3 Mal auszuführen. Dieser Zug wird auch als 3sexy bezeichnet, da RUR'U 'als sexy Zug bezeichnet wird.) Ich messe die Zeit.
Sehen wir uns das Ausführungsergebnis an.
F R F2 R2 U2 R F'
2.8320679664611816 Sekunden
Erstens ist die Lösung nicht 3sexy (das ist richtig, 2x2x2 Würfel können mit bis zu 11 Zügen gelöst werden). Und es hat lange gedauert. Um die Ursache dafür zu finden, führen wir das Konzept des ** Berechnungsbetrags ** ein, anstatt ins Hinterland von Amazon zu gehen.
Berechnungsbetrag
Einfach ausgedrückt, es ist die Häufigkeit, mit der die Schleife umrundet wird. $ O (Nummer) $ Ich werde es schreiben als. Auch in diesem Fall ist die Länge der Lösung (= Suchtiefe) wichtig, sodass andere konstante Vielfache ignoriert werden.
Die Schleife, die bei der Suche nach der Breitenpriorität auftritt, ist eine while-Anweisung. Dies dreht sich so oft wie die Nummer in der Warteschlange, so dass der Rechenaufwand beträgt
$ O (Anzahl der Zustände in \ mathrm {que}) $
Es wird sein. Berechnen wir.
Erstens wachsen vom ersten Knoten aus neun Seiten. Und nach Tiefe 2 (2. Zug) wachsen 6 Seiten von jedem Knoten. Unter der Annahme, dass die Tiefe $ N $ beträgt, beträgt der Rechenaufwand für dieses Programm
Beschneidung
Beschneiden bedeutet, dass bei einer Suche bis zu einer bestimmten Tiefe die Suche an diesem Punkt beendet wird, wenn Sie wissen, dass Sie keine Lösung erreichen können (die Würfel sind nicht ausgerichtet), auch wenn Sie die Suche so fortsetzen, wie sie ist **.
Diesmal die kürzeste Anzahl von Schritten beim Ignorieren von CO (Eckenausrichtung, Ausrichtung von Eckteilen) und Ausrichten nur von CP (Eckenpermutation, Position von Eckteilen) und die kürzeste Anzahl von Schritten beim Ignorieren von CP und Ausrichten von nur CO Berechnen Sie die beiden im Voraus und beschneiden Sie den Schnittmoment, wenn Sie feststellen, dass CP oder CO nicht innerhalb von 11 Zügen liegen (Gottes Zahl). Ich denke, es wird ein Chaos, also lassen Sie uns ein Bild als Beispiel geben. Das linke ist der Zustand, in dem nur CP vorbereitet wird, und das rechte ist der Zustand, in dem nur CO vorbereitet wird. Einzelheiten finden Sie im Abschnitt Software.
Die Suche nach der Breitenpriorität des vorherigen Programms ist wie folgt.
inf = 100
fac = [1]
for i in range(1, 8):
fac.append(fac[-1] * i)
#Erstellen Sie eine CP-Sequenz zum Beschneiden anhand der Suche nach Breitenpriorität
cp = [inf for _ in range(fac[7])]
cp_solved = Cube()
cp_solved.Cp = solved.Cp
cp[cp_solved.cp2i()] = 0
que = deque([cp_solved])
while len(que):
status = que.popleft()
num = len(status.Moves)
l_mov = status.Moves[-1] if num else -1
t = (l_mov // 3) * 3
lst = set(range(9)) - set([t, t + 1, t + 2])
for mov in lst:
n_status = status.move_cp(mov)
n_idx = n_status.cp2i()
if cp[n_idx] == inf:
cp[n_idx] = num + 1
que.append(n_status)
#Erstellen Sie eine CO-Sequenz zum Beschneiden nach Breitenprioritätssuche
co = [inf for _ in range(3 ** 7)]
co_solved = Cube()
co_solved.Co = solved.Co
co[co_solved.co2i()] = 0
que = deque([co_solved])
while len(que):
status = que.popleft()
num = len(status.Moves)
l_mov = status.Moves[-1] if num else -1
t = (l_mov // 3) * 3
lst = set(range(9)) - set([t, t + 1, t + 2])
for mov in lst:
n_status = status.move_co(mov)
n_idx = n_status.co2i()
if co[n_idx] == inf:
co[n_idx] = num + 1
que.append(n_status)
print('Vorverarbeitung', time() - strt, 's')
#Suche nach Breitenpriorität
que = deque([puzzle])
while que:
#Status aus der Warteschlange entfernen
status = que.popleft()
#L die Nummer des letzten Schritts_Setzen Sie es in mov
l_mov = status.Moves[-1] if len(status.Moves) else -1
#Liste der Schritte, die als nächstes ausgeführt werden müssen
t = (l_mov // 3) * 3
lst = set(range(9)) - set([t, t + 1, t + 2])
for mov in lst:
#Bewegen Sie das Puzzle tatsächlich
n_status = status.move(mov)
#Ich habe die Antwort gefunden!
if n_status.Cp == solved.Cp and n_status.Co == solved.Co:
print(n_status.num2moves())
print('Das ganze', time() - strt, 'Sekunden')
exit()
elif len(n_status.Moves) + max(cp[n_status.cp2i()], co[n_status.co2i()]) < 11:
#Wenn Sie die Antwort nicht finden, fügen Sie der Warteschlange einen Status hinzu. Sie beschneiden hier mit elif
que.append(n_status)
Lassen Sie uns das Ergebnis dieser Ausführung sehen.
Vorbehandlung 0.433823823928833 s
F R F2 R2 U2 R F'
Insgesamt 2.1692698001861572 Sekunden
Oh, es ist etwas schneller. Aber es ist noch ein bisschen spät ... Ich möchte weniger als eine Sekunde anstreben. Und die Speichernutzung ist auch moderat und schwerwiegend. Selbst mit diesem beschnittenen Programm scheint die Speichernutzung etwa 4,3 GB zu betragen. Hier kommt IDA * ins Spiel.
IDA* IDA * ist eine Abkürzung für Iterative Deepening A *. Der spezifische Inhalt wird im Artikel hier ausführlich beschrieben, daher werde ich ihn in meinem Artikel weglassen, aber persönlich in diesem Artikel Ich werde den Inhalt extrahieren und zitieren, den ich für am einfachsten zu verstehen hielt.
In einem Wort lautet IDA * "Tiefenprioritätssuche (DFS) mit begrenzter maximaler Tiefe wiederholen, während die Tiefe erhöht wird". Der Mechanismus von IDA * besteht darin, den einmal durchsuchten Knoten zu vergessen. Wenn Sie den Knoten vergessen haben, können Sie Speicher freigeben.
Mit anderen Worten, wenn der Inhalt dieses Mal den Rubik-Würfel lösen soll, wird die Tiefe (Arbeit) von 1 bis 11 untersucht und die ** Suche nach Tiefenpriorität ** wird innerhalb dieses Tiefenbereichs durchgeführt. Wenn Sie bis zum Ende in einer Tiefe von $ N-1 $ suchen und keine Lösung gefunden wird, vergessen Sie alles, wonach Sie gesucht haben. Suchen Sie dann erneut in einer Tiefe von $ N $. Auf den ersten Blick ist es ineffizient, aber es funktioniert überraschend gut.
Ich habe oben erwähnt, dass die Suche mit Tiefenpriorität nicht immer die optimale Lösung findet. IDA * garantiert jedoch, dass bei der Untersuchung der Tiefe von $ N $ keine Lösung bis zu einer Tiefe von $ N-1 $ existiert. Mit anderen Worten, wenn eine Lösung in einer Tiefe von $ N $ gefunden wird, ist dies die optimale Lösung. Er erwähnte auch, dass die Suche mit Tiefenpriorität relativ wenig Speicher benötigt. IDA * verwendet diese Suche mit Tiefenpriorität, um die Speichernutzung erheblich zu reduzieren.
Lassen Sie es uns implementieren. Ich werde bis zum Beschneiden des vorherigen Programms ausleihen und danach neu schreiben.
# IDA*
for depth in range(1, 12):
stack = [puzzle]
while stack:
#Entfernen Sie den Status vom Stapel. Diesmal handelt es sich um eine Suche mit Tiefenpriorität, daher ist sie nicht popleft
status = stack.pop()
#L die Nummer des letzten Schritts_Setzen Sie es in mov
l_mov = status.Moves[-1] if len(status.Moves) else -1
#Liste der Schritte, die als nächstes ausgeführt werden müssen
t = (l_mov // 3) * 3
lst = set(range(9)) - set([t, t + 1, t + 2])
for mov in lst:
#Bewegen Sie das Puzzle tatsächlich
n_status = status.move(mov)
#Ich habe die Antwort gefunden!
if len(n_status.Moves) == depth - 1 and n_status.Cp == solved.Cp and n_status.Co == solved.Co:
print(n_status.num2moves())
print('Das ganze', time() - strt, 'Sekunden')
exit()
elif len(n_status.Moves) + max(cp[n_status.cp2i()], co[n_status.co2i()]) < depth:
#Wenn Sie die Antwort nicht finden, fügen Sie dem Stapel einen Status hinzu, den Sie hier mit elif beschneiden
stack.append(n_status)
Das einzige, was sich vor einiger Zeit geändert hat, war das Hinzufügen einer Tiefe für Anweisungen und die Tatsache, dass que zu einem Stapel wurde. Warteschlangen und Stapel werden in diesem Artikel nicht behandelt. Lesen Sie daher die Artikel hier.
Wie wäre es mit dem Ergebnis?
Vorbehandlung 0.352100133895874 s
F R' U2 R2 F2 R' F'
Insgesamt 0.36607813835144043 Sekunden
Explosive Geschwindigkeit ...! !! Die Speichernutzung betrug nur 93 MB. Es ist die beste IDA *.
Darüber hinaus wurde darauf hingewiesen, dass eine weitere Speicherersparnis erwartet werden kann, indem die Suche nach der Tiefenpriorität rekursiv geschrieben und die Liste der Rotationsnummern (Rotationssymbole), die derzeit untersucht werden, als ein Stapel verwaltet wird. Dies wird hier nicht behandelt, da dies die Implementierung erheblich verändert und es wünschenswert ist, einige Klassenänderungen vorzunehmen. Im Software-Bereich werden wir ein Programm vorstellen, das diesen Punkt widerspiegelt.
Wenn die Anzahl der Unterteilungen groß ist, z. B. 3x3x3 anstelle von 2x2x2, dauert es einige Zeit, eine Lösung nur mit IDA * zu finden. Daher wird häufig ein Zweiphasenalgorithmus verwendet.
Zusammenfassung
Vielen Dank, dass Sie so weit gelesen haben. Ich habe versucht, den Algorithmus zum Lösen des Rubik-Würfels so einfach wie möglich zu schreiben (obwohl ich IDA * nicht erklären kann, den ersten Algorithmus, den ich dieses Mal so einfach (und ich) über die Herstellung dieses Roboters gelernt habe. Ich bin nicht sehr vertraut damit), also habe ich es ziemlich kaputt gemacht. Wenn Sie Algorithmen mögen, warum nicht Rubik Cube starten? Und wenn Sie Rubik Cube mögen, warum nicht anfangen, Algorithmen zu studieren?
Recommended Posts