Faisons un robot qui résout le Rubik Cube! 2 Algorithme

Quel est cet article?

Cet article est sérialisé ** Faisons un robot qui résout le Rubik Cube! Il fait partie de la collection d'articles appelée **. Cliquez ici pour voir l'image complète

1. Présentation
2. Algorithme (cet article)
3. Logiciel (non publié)
4. Matériel (non publié)

GitHub est ici.

J'ai également créé une vidéo avec le même contenu que cet article.

Cliquez ici pour une collection de vidéos sur cette collection d'articles.

Contenu de cet article

Cette fois, j'expliquerai l'algorithme du programme qui produit la procédure la plus courte (pour le robot) pour résoudre le cube rubic 2x2x2. L'algorithme introduit "la recherche de priorité de largeur" et "IDA *". Avant cela, abordons brièvement l'idée de recherche complète.

Quelle est la "recherche totale" à considérer cette fois?

La recherche complète est littéralement une ** méthode pour rechercher tous les modèles **. Pour un cube rubic 2x2x2, vérifiez tout en tournant {U, U ', U2, F, F', F2, R, R ', R2} à partir d'un certain état, et vérifiez avant sinon tout C'est une méthode de recherche telle que tourner et vérifier tous les {U, U ', U2, F, F', F2, R, R ', R2} pour tous les modèles (strictement, 2 étapes). Il y a 6 étapes chacune pour rechercher les yeux, mais j'en parlerai plus tard). Les U, F et R qui apparaissent ici sont appelés symboles de rotation. Pour plus de détails, consultez la présentation.

Maintenant, dessinons un petit chiffre ici. De cette façon, si l'état du cube est représenté par un cercle (nœud) et que la rotation d'une main à partir de cet état est représentée par un bâton (côté), en répétant la rotation de toutes les mains qui peuvent être recherchées à partir d'un certain état et de cet arbre Un tel chiffre correspond. Dans la figure, il a été ignoré, mais dans le cas de 2x2x2, pour chaque état,

• Le premier coup est {U, U ', U2, F, F', F2, R, R ', R2} 9 coups
• À partir du deuxième coup, si le coup précédent est l'un des {X, X ', X2}, {U, U', U2, F, F ', F2, R, R', R2} \ 6 coups de {X, X ', X2} (\ est le symbole de l'ensemble des différences)

Puisque vous pouvez tourner autant, vous aurez 9 côtés du premier nœud (racine) et 6 côtés l'un de l'autre que le premier nœud.

De plus, le nombre de pas à rechercher après le deuxième coup est réduit, par exemple, si vous tournez X X ', c'est la même chose que de ne rien tourner, si vous tournez XX, c'est la même chose que X2, si vous tournez X X2, c'est la même chose que X'. De plus, si deux aiguilles du même type de symboles de rotation sont alignées, elles seront toujours annulées ou remplacées par un autre symbole de rotation.

Recherche de priorité de largeur

"** Recherche de priorité de largeur " est une méthode typique de recherche complète avec " Recherche de priorité de profondeur **". Les nœuds de la figure précédente sont numérotés intentionnellement à des fins d'explication ici. Comme vous pouvez le voir (?) L'ordre d'examen de chaque nœud est différent entre la recherche de priorité de profondeur et la recherche de priorité de largeur. Expliquons brièvement chacun.

Recherche de priorité de largeur

La recherche de priorité de largeur est indiquée sur la figure 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->... C'est une méthode de recherche pour rechercher. que se passe-t-il? Je pense, ajoutons donc une flèche à la figure précédente. C'est vrai, c'est une recherche qui s'approfondit progressivement. En termes de chiffres sur la figure, le nombre de L.M.N à rechercher augmentera progressivement. En d'autres termes, plus vous vous déplacez depuis le début, plus tard vous serez recherché.

Cette méthode de recherche est souvent utilisée pour ** trouver l'itinéraire le plus court **. La raison en est que si "plus vous tournez de mains, plus vous serez recherché tard", alors "si vous pouvez trouver une solution dans un court laps de temps, la recherche sera terminée lorsque vous la trouverez".

Si vous voulez en savoir plus, je vous recommande l'article ici.

Recherche de priorité de profondeur

L'ordre de recherche de la recherche de priorité de profondeur est le suivant. 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->... Mettons également un chiffre. La recherche de priorité de profondeur est une méthode de recherche qui recherche pour le moment jusqu'à l'endroit le plus profond (le plus long) et, si cela ne fonctionne pas, retourne à un endroit moins profond (essayez de changer la dernière main tournée vers une autre main). est. En d'autres termes, lors de l'examen d'un nœud avec le dernier numéro N, tel que L.M.N pour chaque profondeur, le nœud avec L.M. (N-1 ou moins) a déjà été examiné.

Cette méthode de recherche est relativement facile à mettre en œuvre, peut se terminer plus rapidement que la recherche avec priorité à la largeur (si vous recherchez une solution non optimale (procédure non la plus courte)) et utilise relativement peu de mémoire, je souhaite donc effectuer une recherche complète pour le moment. Je l'utilise souvent quand.

Pour plus d'informations, nous vous recommandons ici et ici.

Résolvez le Rubik Cube avec la recherche de priorité de largeur

Cette fois, je veux trouver le nombre d'étapes le plus court, je vais donc utiliser la recherche de priorité de largeur. Implémentons-le pour le moment. Si vous ne pouvez pas lire Python ici, lisez simplement les commentaires et écoutez-les.

from collections import deque
from copy import deepcopy
from time import time

move_candidate = ["U", "U2", "U'", "F", "F2", "F'", "R", "R2", "R'"] #Candidat à la rotation

#Classe de cube non indispensable dans cet article(J'expliquerai en détail dans l'édition du logiciel)
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 = []

    #Traitement de rotation 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

    #Traitement de rotation 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

    #Changez en fait la disposition des états du puzzle en fonction du numéro de rotation
    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

    #Convertir le numéro de rotation en symbole de rotation
    def num2moves(self):
        res = ''
        for i in self.Moves:
            res += move_candidate[i] + ' '
        return res
    
    #Créer un numéro unique à partir du tableau cp
    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
    
    #Créer un numéro unique à partir du tableau co
    def co2i(self):
        res = 0
        for i in self.Co:
            res *= 3
            res += i
        return res

#L'état du puzzle(R U R' U')3(Ce 3 est R U R' U'Signifie qui a été retourné 3 fois)État tourné
#Commencez par un fouillis d'énigmes et explorez jusqu'à ce qu'elles soient terminées
puzzle = Cube()
#CP est une abréviation de Corner Permutation. Représente la position des pièces d'angle.
puzzle.Cp = [1, 0, 2, 5, 4, 3, 6]
#CO est une abréviation pour Corner Orientation. Indique l'orientation des pièces d'angle.
puzzle.Co = [2, 1, 0, 0, 0, 0, 0]

#L'état du puzzle à l'état résolu
solved = Cube()
solved.Cp = [0, 1, 2, 3, 4, 5, 6]
solved.Co = [0, 0, 0, 0, 0, 0, 0]

#mesure du temps
strt = time()

#Recherche de priorité de largeur
que = deque([puzzle])
while que:
    #Supprimer l'état de la file d'attente
    status = que.popleft()

    #L le numéro de la dernière étape_Mettez-le en mov
    l_mov = -1 if not status.Moves else status.Moves[-1]

    #Liste des étapes à suivre
    t = (l_mov // 3) * 3
    lst = set(range(9)) - set([t, t + 1, t + 2])
    for mov in lst:
        #En fait, déplacez le puzzle
        n_status = status.move(mov)

        #J'ai trouvé la réponse!
        if n_status.Cp == solved.Cp and n_status.Co == solved.Co:
            print(n_status.num2moves())
            print(time() - strt, 'Secondes')
            exit()
        
        #Si aucune réponse n'est trouvée, ajoutez l'état à la file d'attente
        que.append(n_status)

Cela fait un peu long, mais le sujet principal est juste sous les 30 dernières lignes. En dehors de cela, c'est une classe pour exprimer des cubes. Je parlerai en détail dans la section logiciel.

Dans ce programme, brouiller l'image ((RUR'U ') 3, 3 signifie faire RUR'U' 3 fois, ce mouvement est aussi appelé 3sexy car RUR'U 'est appelé mouvement sexy) , Je mesure le temps.

Voyons le résultat de l'exécution.

F R F2 R2 U2 R F'
2.8320679664611816 secondes

Tout d'abord, la solution n'est pas 3sexy (c'est vrai, les cubes 2x2x2 peuvent être résolus avec jusqu'à 11 mouvements). Et cela prend du temps. Pour trouver la cause de cela, introduisons le concept de ** montant de calcul ** au lieu d'aller dans l'arrière-pays d'Amazon.

Montant du calcul

En termes simples, c'est le nombre de fois où la boucle tourne. $ O (nombre) $ Je vais l'écrire comme. De plus, dans ce cas, la longueur de la solution (= profondeur de recherche) est importante, donc les autres multiples constants sont ignorés.

La boucle qui tourne dans la recherche de priorité de largeur est une instruction while. Cela tourne autant de fois que le nombre de la que, donc le montant du calcul est $ O (nombre d'états dans \ mathrm {que}) $ Ce sera. Calculons. Premièrement, neuf côtés se développent à partir du premier nœud. Et après la profondeur 2 (2e mouvement), 6 côtés se développent à partir de chaque nœud. Par conséquent, en supposant que la profondeur est de $ N $, le montant du calcul de ce programme est O(9\times 6^{N-1}) est. Au fait, ce brouillage semble avoir été résolu à 7 mains. Remplaçons $ N = 7 $. O(9\times 6^6)=O(4.2\times10^5) Cette fois, la quantité de calcul a ralenti, probablement parce que chaque processus est lourd. À propos, des cubes 2x2x2 peuvent être préparés avec un maximum de 11 mains (nombre de Dieu), alors substituons également $ N = 11 $. O(9\times 6^{10})=O(5.4\times10^8) Pas comme ça. Cela ne se terminera pas presque pour toujours! !! Par conséquent, ** l'élagage ** est introduit pour accélérer le processus.

Taille

L'élagage signifie que lorsque vous recherchez à une certaine profondeur, si vous savez que vous ne pouvez pas atteindre une solution (les cubes ne sont pas alignés) même si vous continuez la recherche telle quelle **, la recherche se terminera à ce point.

Cette fois, le nombre d'étapes le plus court en ignorant CO (orientation des coins, orientation des pièces d'angle) et en alignant uniquement CP (permutation d'angle, position des pièces d'angle), et le nombre d'étapes le plus court en ignorant CP et en alignant uniquement CO Calculez les deux à l'avance et élaguez le moment de taille lorsque vous constatez que CP ou CO n'est pas à moins de 11 coups (nombre de Dieu). Je pense que ce sera un gâchis, alors mettons une image à titre d'exemple. La gauche est l'état où seul le CP est préparé, et la droite est l'état où seul le CO est préparé. Pour plus de détails, consultez la section logiciel.

La recherche de priorité de largeur du programme précédent est la suivante.

inf = 100
fac = [1]
for i in range(1, 8):
    fac.append(fac[-1] * i)

#Créer une séquence CP pour l'élagage par recherche de priorité de largeur
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)

#Créer une séquence CO pour l'élagage par recherche de priorité de largeur
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('Prétraitement', time() - strt, 's')

#Recherche de priorité de largeur
que = deque([puzzle])
while que:
    #Supprimer l'état de la file d'attente
    status = que.popleft()

    #L le numéro de la dernière étape_Mettez-le en mov
    l_mov = status.Moves[-1] if len(status.Moves) else -1

    #Liste des étapes à suivre
    t = (l_mov // 3) * 3
    lst = set(range(9)) - set([t, t + 1, t + 2])
    for mov in lst:
        #En fait, déplacez le puzzle
        n_status = status.move(mov)

        #J'ai trouvé la réponse!
        if n_status.Cp == solved.Cp and n_status.Co == solved.Co:
            print(n_status.num2moves())
            print('L'ensemble', time() - strt, 'Secondes')
            exit()
        elif len(n_status.Moves) + max(cp[n_status.cp2i()], co[n_status.co2i()]) < 11:
            #Si vous ne trouvez pas la réponse, ajoutez un état à la file d'attente Vous élaguez avec elif ici
            que.append(n_status)

Voyons le résultat de cette exécution.

Prétraitement 0.433823823928833 s
F R F2 R2 U2 R F'
Général 2.1692698001861572 secondes

Oh, c'est un peu plus rapide. Mais il est encore un peu tard ... Je veux viser moins d'une seconde. Et l'utilisation de la mémoire est également modérée et sévère. Même avec ce programme élagué, l'utilisation de la mémoire semble être d'environ 4,3 Go. C'est là que l'IDA * entre en jeu.

IDA* IDA * est une abréviation pour Iterative Deepening A *. Le contenu spécifique est décrit en détail dans l'article ici, donc je l'omettrai dans mon article, mais personnellement dans cet article Je vais extraire et citer le contenu que je pensais être le plus facile à comprendre.

IDA * peut être exprimé en un mot: "Répéter la recherche de priorité de profondeur (DFS) avec une profondeur maximale limitée tout en augmentant la profondeur". Le mécanisme d'IDA * est d'oublier le nœud une fois recherché. Si vous oubliez le nœud, vous pouvez libérer de la mémoire.

En d'autres termes, si le contenu doit résoudre le Rubik Cube cette fois, la profondeur (travail) sera étudiée de 1 à 11 et la ** recherche de priorité de profondeur ** sera effectuée dans cette plage de profondeur. De plus, si vous recherchez jusqu'à la fin à une profondeur de $ N-1 $ et qu'aucune solution n'est trouvée, oubliez tout ce que vous avez recherché. Puis recherchez à nouveau à une profondeur de $ N $. À première vue, c'est inefficace, mais cela fonctionne étonnamment bien.

J'ai mentionné ci-dessus que la recherche prioritaire en profondeur ne trouve pas toujours la solution optimale. Mais IDA * garantit qu'aucune solution n'existe jusqu'à une profondeur de $ N-1 $ lors de l'examen de la profondeur de $ N $. En d'autres termes, si une solution est trouvée à une profondeur de $ N $, c'est la solution optimale. Il a également mentionné que la recherche avec priorité à la profondeur utilise relativement peu de mémoire. IDA * utilise cette recherche de priorité en profondeur pour réduire considérablement l'utilisation de la mémoire.

Mettons-le en œuvre. Je vais emprunter jusqu'à l'élagage du programme précédent et réécrire après cela.

# IDA*
for depth in range(1, 12):
    stack = [puzzle]
    while stack:
        #Supprimer l'état de la pile. Cette fois, il s'agit d'une recherche prioritaire en profondeur, donc ce n'est pas popleft
        status = stack.pop()

        #L le numéro de la dernière étape_Mettez-le en mov
        l_mov = status.Moves[-1] if len(status.Moves) else -1

        #Liste des étapes à suivre
        t = (l_mov // 3) * 3
        lst = set(range(9)) - set([t, t + 1, t + 2])
        for mov in lst:
            #En fait, déplacez le puzzle
            n_status = status.move(mov)

            #J'ai trouvé la réponse!
            if len(n_status.Moves) == depth - 1 and n_status.Cp == solved.Cp and n_status.Co == solved.Co:
                print(n_status.num2moves())
                print('L'ensemble', time() - strt, 'Secondes')
                exit()
            elif len(n_status.Moves) + max(cp[n_status.cp2i()], co[n_status.co2i()]) < depth:
                #Si vous ne trouvez pas la réponse, ajoutez un état à la pile Vous élaguez avec elif ici
                stack.append(n_status)

La seule chose qui a changé il y a quelque temps a été l'ajout d'une profondeur pour la déclaration et le fait que que est devenu une pile. Les files d'attente et les piles ne sont pas couvertes dans cet article, veuillez donc vous référer aux articles ici.

Eh bien, que diriez-vous du résultat.

Prétraitement 0.352100133895874 s
F R' U2 R2 F2 R' F'
Globalement 0.36607813835144043 secondes

Vitesse explosive ...! !! L'utilisation de la mémoire n'était que de 93 Mo. C'est le meilleur IDA *.

En outre, il a été souligné que l'on peut s'attendre à une économie de mémoire supplémentaire en écrivant la recherche de priorité de profondeur de manière récursive et en gérant la liste des numéros de rotation (symboles de rotation) actuellement étudiés comme une seule pile. Ceci n'est pas couvert ici car cela changera l'implémentation de manière significative et il est souhaitable de faire quelques changements de classe. Dans la section logiciel, nous présenterons un programme qui reflète ce point.

De plus, si le nombre de divisions est important, par exemple 3x3x3 au lieu de 2x2x2, il faudra du temps pour trouver une solution avec IDA * seul, il est donc courant d'utiliser un algorithme à deux phases.

Résumé

Merci d'avoir lu jusqu'ici. J'ai essayé d'écrire l'algorithme pour résoudre le Rubik Cube aussi simplement que possible (bien que je ne puisse pas expliquer IDA *, qui est le premier algorithme que j'ai appris à fabriquer ce robot cette fois, si facilement (et moi). Je ne comprends pas beaucoup), alors je l'ai cassé un peu). Si vous aimez les algorithmes, pourquoi ne pas commencer à utiliser le Rubik Cube? Et si vous aimez Rubik Cube, pourquoi ne pas commencer à étudier les algorithmes?