Cet article est l'article du 17ème jour du Calendrier de l'Avent Speedcubing 2019. [Série] Écrivons un programme pour résoudre le Rubik Cube (Partie 1) Nous continuerons.
Dans la première partie, j'ai créé une classe qui exprime l'état / le fonctionnement du cube Rubik et écrit une méthode pour faire fonctionner l'état. Maintenant que vous pouvez faire pivoter le cube par programme, procédons à la recherche.
Dans la deuxième partie, nous chercherons à tour de rôle, nous ne pourrons donc pas encore trouver la solution du cube Rubik dans aucun état, mais de petites énigmes telles que Pyraminx et le cube 2x2x2 peuvent également être résolues de cette manière.
En ce qui concerne l'environnement, Python 3.6 ou supérieur est le même que la première partie.
Dans la continuité de la première partie, un cahier de collaboration du code qui apparaît ci-dessous Je me suis également préparé, donc si vous cliquez sur «[Ouvrir dans Play Ground]» et que vous procédez à l'exécution dans l'ordre, vous n'aurez pas besoin de créer un environnement et ce sera plus facile.
Le Rubik Cube a environ 4,3 * 10 ^ 19 états, et le nombre le plus court de coups est d'environ 18 en moyenne. Il est connu pour être complété en 20 mains dans le pire des cas (c.f. https://www.cube20.org/).
Le round-robin est une échelle qui ne peut pas être égalée dans un temps réaliste, mais d'abord, écrivons un programme pour résoudre le Rubik Cube avec round-robin et l'améliorons en fonction de celui-ci.
En raison du grand nombre d'états dans le Rubik Cube, la recherche de priorité de largeur utilise trop de mémoire. Pour résoudre le round-robin du Rubik Cube, [Répéter la recherche de priorité de profondeur d'approfondissement](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) peuvent être utilisés. Il s'agit d'une méthode de répétition d'une recherche de priorité de profondeur (recherche de contrainte de profondeur) qui limite la profondeur de la recherche (longueur de la solution) en augmentant progressivement la profondeur limite.
Tout d'abord, je dois écrire une fonction pour juger si l'état qui apparaît dans le processus de recherche est un état achevé. Si tous les EO, CO, EP et CP sont complets, cela signifie que le produit est complet, alors j'ai écrit une fonction pour le déterminer.
def is_solved(state):
return (state.eo == [0] * 12 #Tous les OE sont disponibles
and state.co == [0] * 8 #Tout le CO est disponible
and state.ep == list(range(12)) #Tous les EP sont disponibles
and state.cp == list(range(8)) #Tous les CP sont disponibles
)
Écrivez une fonction qui fait référence au coup précédent et retourne si l'opération peut être utilisée comme coup suivant.
Dans un cas simple, il n'est pas possible de faire tourner la même surface en continu. (Tels que «R'R2»)
De plus, ʻU D U est le même que ʻU2 D, donc c'est mauvais.
Pour éviter cela, fixez l'ordre des noms de visage dans l'ordre lexical lorsque vous tournez face à face (comme l'ordre «D U» est bon, mais l'ordre «U D» ne l'est pas).
inv_face = {
"U": "D",
"D": "U",
"L": "R",
"R": "L",
"F": "B",
"B": "F"
}
def is_move_available(prev_move, move):
"""
Déterminez si l'opération peut être utilisée comme coup suivant en considérant le coup précédent
-Ne faites pas tourner la même surface en continu(e.g. R'R2 n'est pas possible)
-Correction de l'ordre lors du tournage face à face(e.g.D U est bon, mais U D ne l'est pas)
"""
if prev_move is None:
return True #Toute opération est possible pour le premier coup
prev_face = prev_move[0] #La surface a tourné d'un côté
if prev_face == move[0]:
return False #Le même côté n'est pas possible
if inv_face[prev_face] == move[0]:
return prev_face < move[0] #En face à face, l'ordre lexical est acceptable
return True
Je l'ai écrit comme ça.
Dans start_search, il part de 0 coups, appelle l'implémentation de la recherche de limite de profondeur tout en augmentant progressivement le nombre de coups, et le renvoie lorsqu'il trouve une solution.
L'argument depth of depth_limited_search représente la profondeur restante, et tout en la réduisant, la recherche se poursuit de manière récursive de sorte que lorsque depth = 0, le nombre de pas en cours de recherche est atteint.
Préparez une pile pour gérer la solution (procédure) à laquelle vous pensez. Si vous poussez l'opération lors de l'entrée dans le nœud suivant dans le processus de recherche et le pop en quittant, la solution en cours de recherche sera toujours dans cette pile, et il n'est pas nécessaire d'avoir une solution pour chaque état.
class Search:
def __init__(self):
self.current_solution = [] #Pile pour mettre la procédure que vous recherchez
def depth_limited_search(self, state, depth):
if depth == 0 and is_solved(state):
# is_Si résolu est True, il est complet, donc il renvoie True car la solution a été trouvée.
# depth==0 n'est pas obligatoire, mais la profondeur>Vous n'êtes pas obligé d'appeler la fonction de décision à chaque fois car vous savez déjà que 0 n'a pas de solution
return True
if depth == 0: #Renvoie False si la solution n'est pas trouvée après avoir atteint la profondeur 0
return False
# depth=Continuer la recherche jusqu'à 0
prev_move = self.current_solution[-1] if self.current_solution else None #Opération devant
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): #Répétez la recherche de limite de profondeur tout en augmentant progressivement le nombre de pas à partir de 0
print(f"# Start searching length {depth}")
if self.depth_limited_search(state, depth):
#Si une solution est trouvée, renvoyez-la à ce stade
return " ".join(self.current_solution)
return None
Dans cette mise en œuvre, aucune solution ne peut être trouvée dans un temps réaliste pour un brouillage aléatoire ordinaire, je vais donc donner un brouillage à 6 mains approprié. La solution a été trouvée en 34 secondes. Naturellement, la solution est de tourner le brouillage dans la direction opposée.
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'.
L'élagage est une technique pour accélérer la recherche. Avec votre connaissance préalable du Rubik Cube, vous pouvez en arrondir de plus en plus si vous trouvez qu'il est inutile d'explorer davantage. Ce type de recherche de priorité de profondeur d'approfondissement itérative bien informée est appelé recherche IDA * (c.f. https://en.wikipedia.org/wiki/Iterative_deepening_A *).
Par exemple, que se passe-t-il si vous n'avez aucune pièce au moment de depth = 1 (1 mouvement vers la gauche)?
Essayez de déplacer manuellement le Rubik Cube de l'état fini. Avec un mouvement à gauche, si vous n'avez pas au moins quatre coins et huit arêtes, vous ne pourrez pas le faire avec votre prochain mouvement.
Par conséquent, il est inutile de poursuivre la recherche du coup suivant, depth = 0.
De même, lorsque depth = 2 (2 mouvements vers la gauche), tous les coins peuvent être cassés (par exemple LR), mais si vous n'avez pas 4 arêtes, vous aurez 2 mouvements à gauche. Il n'y a aucune possibilité de le faire.
Avec depth = 3 (3 coups à gauche), si vous n'avez pas au moins 2 arêtes à ce stade, vous ne pourrez pas terminer avec 3 coups à gauche.
Implémentons la taille en utilisant ces connaissances.
def count_solved_corners(state):
"""
Comptez le nombre de coins alignés
"""
return sum([state.cp[i] == i and state.co[i] == 0 for i in range(8)])
def count_solved_edges(state):
"""
Compter le nombre d'arêtes alignées
"""
return sum([state.ep[i] == i and state.eo[i] == 0 for i in range(12)])
def prune(depth, state):
"""
Renvoie True si cela n'a aucun sens de continuer
"""
if depth == 1 and (count_solved_corners(state) < 4 or count_solved_edges(state) < 8):
#S'il y a moins de 4 coins alignés avec la main restante, ou s'il y a moins de 8 bords alignés, ils ne seront plus alignés
return True
if depth == 2 and count_solved_edges(state) < 4:
#S'il y a moins de 4 bords alignés avec les 2 mains restantes, ils ne seront plus alignés
return True
if depth == 3 and count_solved_edges(state) < 2:
#S'il y a moins de 2 bords alignés avec les 3 mains restantes, ils ne seront plus alignés
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
#Taille(Seul l'ajout de ces deux lignes a changé)
if prune(depth, state):
return False
prev_move = self.current_solution[-1] if self.current_solution else None #Opération devant
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
La recherche qui a duré 34 secondes est désormais inférieure à 1 seconde. Comme vous pouvez le voir, la taille est très puissante.
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'.
Avec cela seul, de petits puzzles tels que Pyraminx et cubes 2x2x2 peuvent être résolus dans un laps de temps réaliste. Certains amateurs voudront peut-être explorer une partie du cube Rubik (comme une procédure de croisement ou une procédure d'alignement de blocs 2x2x3), mais si elle est courte, c'est la voie à suivre. Si vous trouvez la première solution et la modifiez pour qu'elle ne revienne pas immédiatement, vous pouvez rechercher plusieurs types de solutions.
J'ai écrit un programme pour résoudre le Rubik Cube de manière détournée, et j'ai pu l'accélérer un peu en élaguant, mais il est loin de trouver une solution en peu de temps à partir de n'importe quel état.
Two-Phase-Algorithm est largement utilisé comme algorithme pour trouver la solution sous-optimale du cube Rubik dans un temps réaliste. La solution du Rubik Cube est décomposée en deux phases, et chacune est résolue de manière circulaire.
Dans Phase1, vous pouvez déplacer le Rubik Cube librement et l'amener à un état où il peut être complété avec juste le mouvement de <U, D, R2, L2, F2, B2>.
En Phase2, nous n'utiliserons que les mouvements de «<U, D, R2, L2, F2, B2>» pour le mener à bien.
La phase 1 correspond aux 12 pires coups, environ 10 coups, La phase 2 peut être complétée en 18 coups au pire, environ 13-14 coups (c.f. http://kociemba.org/math/symmetric.htm).
Plus la profondeur de recherche (longueur de la procédure) est profonde, plus la plage de recherche augmente de manière exponentielle, il faut donc environ 18 étapes pour effectuer un round-robin sans diviser la phase, tout en recherchant 10 mouvements et 13 mouvements. Ce sera plus rapide si vous le divisez en recherches.
Il est important que l'algorithme à deux phases soit correctement décomposé en deux phases et divisé en deux étapes qui nécessitent moins d'effort, mais il est également important que le nombre d'états dans chaque phase soit augmenté en divisant la phase en deux. Il est possible d'indexer les états et de créer une table de transition d'état à l'avance, et il est également possible de pré-calculer la table pour l'élagage. Dans l'implémentation de la seconde partie, une instance de la classe State est générée chaque fois qu'elle est recherchée, et cette partie est en fait lente. Vous pouvez améliorer cela en indexant l'état.
Une autre caractéristique est que si vous prenez le temps de rechercher, vous pouvez vous rapprocher de plus en plus de la solution optimale. La mise en œuvre de l'algorithme à deux phases sera laissée dans la deuxième partie.
Recommended Posts