Quel est cet article?

Je développe actuellement un robot qui résout un cube rubic 2x2x2. Ceci est une collection d'articles de commentaires sur le programme du robot. J'ai écrit une fois une collection d'articles représentés par l'article ici, mais depuis cette fois, le logiciel a été considérablement mis à jour, je vais donc introduire un nouveau programme. pense.

Le code applicable est disponible ici [https://github.com/Nyanyan/soltvvo/tree/master/Soltvvo3.2).

Importation de bibliothèques etc.

Importez la bibliothèque et les fonctions de base (https://qiita.com/Nyanyan_Cube/items/e225e8e31897d81a1401)

from collections import deque
import csv

from basic_functions import *

Créer une table de transition d'état

La fonction de transition d'état créée dans l'article précédent est un peu lente. Il faudra du temps pour utiliser cette fonction pour faire passer l'état des centaines de milliers et des millions de fois dans le futur. Par conséquent, pour terminer la transition d'état immédiatement (avec le montant de calcul $ O (1) $), créez un tableau de transition d'état.

Tableau de transition[Numéro de l'état avant la rotation][Numéro de rotation] =Numéro d'état après rotation

Créez une séquence de transition qui devient.

'''Créer une table de transition d'état'''
''' Create state transition tables '''

def create_cp_trans():
    #Séquence de transition CP
    # 8!Décrit comment effectuer la transition avec 12 types de rotation pour chacun des états individuels
    cp_trans = [[-1 for _ in range(12)] for _ in range(fac[8])]
    #Tournez le nombre idx qui représente l'état avant la transition
    for idx in range(fac[8]):
        if idx % 1000 == 0:
            print(idx / fac[8])
        #Créer une séquence CP à partir d'idx et la tourner
        cp = idx2cp(idx)
        for i, twist in enumerate(twist_lst):
            twisted_cp = [j for j in cp]
            for each_twist in twist:
                twisted_cp = move_cp(twisted_cp, each_twist)
            #Convertir le tableau CP en numéro unique
            twisted_idx = cp2idx(twisted_cp)
            cp_trans[idx][i] = twisted_idx
    #Enregistrer dans un fichier CSV
    with open('cp_trans.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in cp_trans:
            writer.writerow(line)
    print('cp trans done')

def create_co_trans():
    #Le contenu du processus est de créer_cp_Seul le trans CP est devenu CO
    co_trans = [[-1 for _ in range(12)] for _ in range(3 ** 7)]
    for idx in range(3 ** 7):
        if idx % 1000 == 0:
            print(idx / 3 ** 7)
        co = idx2co(idx)
        for i, twist in enumerate(twist_lst):
            twisted_co = [j for j in co]
            for each_twist in twist:
                twisted_co = move_co(twisted_co, each_twist)
            twisted_idx = co2idx(twisted_co)
            co_trans[idx][i] = twisted_idx
    with open('co_trans.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in co_trans:
            writer.writerow(line)
    print('co trans done')

Remplissez efficacement le tableau à l'aide de la fonction qui bascule entre le tableau d'état et le numéro d'état dans la fonction de base, et enregistrez le dernier tableau créé dans un fichier CSV.

Le twist_lst``` utilisé pour la rotation est l'arrangement qui apparaissait dans les [Fonctions de base] précédentes (https://qiita.com/Nyanyan_Cube/items/e225e8e31897d81a1401), et est le symbole de rotation original du puzzle. C'est un résumé de.

Faire un tableau d'élagage

Lors de la recherche réelle d'une solution à un casse-tête, la recherche est arrêtée lorsqu'il est connu que "la solution ne peut jamais être trouvée même si vous cherchez plus loin". C'est ce qu'on appelle la taille.

C'est ce tableau d'élagage qui est utilisé pour vérifier si "aucune solution ne peut être trouvée par une recherche plus approfondie". Dans cette séquence, CP et CO sont enregistrés séparément, et combien de coûts supplémentaires sont nécessaires pour chaque état. À propos, CP et CO sont séparés car le nombre d'états augmentera de manière explosive et l'utilisation de la mémoire deviendra énorme si les deux sont pris en compte.

'''Faire un tableau d'élagage'''
''' Create prunning tables '''

def create_cp_cost():
    #Lire le tableau de transition d'état
    cp_trans = []
    with open('cp_trans.csv', mode='r') as f:
        for line in map(str.strip, f):
            cp_trans.append([int(i) for i in line.replace('\n', '').split(',')])
    # 8!Calculez le coût pour chaque état
    cp_cost = [1000 for _ in range(fac[8])]
    #La recherche de priorité de largeur est effectuée, donc la première de la file d'attente(Aligné)Mettez l'état
    solved_cp_idx = [cp2idx(i) for i in solved_cp]
    que = deque([[i, 0] for i in solved_cp_idx])
    for i in solved_cp_idx:
        cp_cost[i] = 0
    cnt = 0
    #Recherche de priorité de largeur
    while que:
        cnt += 1
        if cnt % 1000 == 0:
            print(cnt, len(que))
        #Obtenir l'état de la file d'attente
        cp, cost = que.popleft()
        twists = range(12)
        #Rotation et calcul du coût
        for twist, cost_pls in zip(twists, cost_lst):
            twisted_idx = cp_trans[cp][twist]
            n_cost = cost + grip_cost + cost_pls
            #Mettez à jour la baie en cas de mise à jour des coûts et ajoutez-la à la file d'attente
            if cp_cost[twisted_idx] > n_cost:
                cp_cost[twisted_idx] = n_cost
                que.append([twisted_idx, n_cost])
    #Enregistrer dans un fichier CSV
    with open('cp_cost.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        writer.writerow(cp_cost)
    print('cp cost done')

def create_co_cost():
    #Le contenu du processus est de créer_cp_Seul le trans CP est devenu CO
    co_trans = []
    with open('co_trans.csv', mode='r') as f:
        for line in map(str.strip, f):
            co_trans.append([int(i) for i in line.replace('\n', '').split(',')])
    co_cost = [1000 for _ in range(3 ** 7)]
    solved_co_idx = list(set([co2idx(i) for i in solved_co]))
    que = deque([[i, 0] for i in solved_co_idx])
    for i in solved_co_idx:
        co_cost[i] = 0
    cnt = 0
    while que:
        cnt += 1
        if cnt % 1000 == 0:
            print(cnt, len(que))
        co, cost = que.popleft()
        twists = range(12)
        for twist, cost_pls in zip(twists, cost_lst):
            twisted_idx = co_trans[co][twist]
            n_cost = cost + grip_cost + cost_pls
            if co_cost[twisted_idx] > n_cost:
                co_cost[twisted_idx] = n_cost
                que.append([twisted_idx, n_cost])
    with open('co_cost.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        writer.writerow(co_cost)
    print('co cost done')

Le traitement de base est effectué par recherche de priorité de largeur. Placez les 24 types d'états initialement alignés (il y a 24 états différents selon la direction de visualisation même dans le même puzzle), et obtenez l'état de la file d'attente dans l'instruction `` while ''. Sera traité séquentiellement.

Pour le processus de rotation, utilisez le tableau de transition dans l'état créé précédemment. Bien sûr, vous pouvez le faire sans l'utiliser, mais cela prend un ordre de grandeur plus long.

Énumérez les états qui seront prêts dans peu de temps

Dans la recherche de solution, j'utilise IDA *, qui est l'algorithme le plus approprié pour la recherche de solution du cube Rubik. Voir / items / 60f3699db96dba4a4bf5)), ce programme cherche une solution pour minimiser le coût: ** une valeur proche du temps qu'il faut pour résoudre l'énigme **. Son utilisation rend la recherche plus lourde que l'utilisation d'autres indicateurs tels que l'effort. Par conséquent, lorsque le casse-tête était résolu à un certain coût ou plus, la recherche était terminée à cet endroit et les solutions précalculées étaient combinées pour former la solution complète. Il est nécessaire de décider combien "d'états pouvant être résolus en peu de temps" sont listés en fonction de la mémoire et du temps de calcul.

Cette énumération d'état doit être créée en utilisant une rotation inverse à partir de l'état où les énigmes sont terminées. Par conséquent, créez d'abord un tableau de transition d'état pour la rotation inverse. Après cela, c'est l'histoire principale.

Partie 1 Créer un tableau de transition d'état par rotation inverse

Comme mentionné ci-dessus, créez un tableau de transition d'état pour la rotation inverse de la procédure de puzzle. À ce stade, vous vous demandez peut-être si vous pouvez réutiliser le tableau de transition que vous avez créé précédemment, mais en raison de la structure du robot, la rotation inverse n'est pas incluse dans le tableau créé précédemment. Cela est dû à la structure que le robot peut toujours faire tourner le puzzle uniquement dans le sens antihoraire. Pour plus de détails, veuillez consulter Version matérielle de "Faisons un robot qui résout le Rubik Cube!".

'''Créer un tableau de transition d'état lorsque la procédure inverse est activée'''
''' Create state transition tables for reverse twists'''

def create_cp_trans_rev():
    #Le processus de base est de créer_cp_Identique à trans
    cp_trans_rev = [[-1 for _ in range(12)] for _ in range(fac[8])]
    for idx in range(fac[8]):
        if idx % 1000 == 0:
            print(idx / fac[8])
        cp = idx2cp(idx)
        for i, twist in enumerate(twist_lst):
            twisted_cp = [j for j in cp]
            for each_twist in twist:
                twisted_cp = move_cp(twisted_cp, each_twist)
            twisted_idx = cp2idx(twisted_cp)
            # create_cp_Contrairement aux trans, cp_trans_rev[twisted_idx][i]Mettre à jour
            cp_trans_rev[twisted_idx][i] = idx
    with open('cp_trans_rev.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in cp_trans_rev:
            writer.writerow(line)
    print('cp trans rev done')

def create_co_trans_rev():
    #Le processus de base est de créer_co_Identique à trans
    co_trans_rev = [[-1 for _ in range(12)] for _ in range(3 ** 7)]
    for idx in range(3 ** 7):
        if idx % 1000 == 0:
            print(idx / 3 ** 7)
        co = idx2co(idx)
        for i, twist in enumerate(twist_lst):
            twisted_co = [j for j in co]
            for each_twist in twist:
                twisted_co = move_co(twisted_co, each_twist)
            twisted_idx = co2idx(twisted_co)
            # create_co_Contrairement aux trans, co_trans_rev[twisted_idx][i]Mettre à jour
            co_trans_rev[twisted_idx][i] = idx
    with open('co_trans_rev.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in co_trans_rev:
            writer.writerow(line)
    print('co trans rev done')

État précédent Il est très similaire au programme lorsque la disposition des fibres a été faite, mais il y a une différence.

Tableau de transition d'état de rotation inverse[Numéro après rotation][Numéro de rotation] =Numéro avant rotation

C'est là que vous devez.

Partie 2 Énumérez les états qui seront bientôt prêts

Utilisez la recherche de priorité de largeur pour énumérer les états. Mais,

Numéro d'état
Coût de cet état à l'achèvement
Procédure de cet état à l'achèvement

C'est un peu gênant car il faut tenir beaucoup de paramètres.

De plus, même si vous avez déjà visité, vous pourrez peut-être le compléter à un coût inférieur à celui de votre visite précédente. Pour réduire la quantité de calcul dans ce cas, utilisez neary_solved_idx, neary_solved_cost_dic, neary_solved_idx_dic '' (bien que cette méthode soit un peu redondante et je pense qu'il y a un meilleur moyen).

Dans la recherche de solution réelle, les éléments de ce tableau sont obtenus en utilisant une dichotomie utilisant une combinaison de nombres CP et CO. Par conséquent, le tableau résultant est trié puis enregistré.

'''Énumérez les états qui seront prêts dans peu de temps'''
''' Create array of states that can be solved soon '''

def create_neary_solved():
    #Lire le tableau de transition de procédure inverse
    cp_trans_rev = []
    with open('cp_trans_rev.csv', mode='r') as f:
        for line in map(str.strip, f):
            cp_trans_rev.append([int(i) for i in line.replace('\n', '').split(',')])
    co_trans_rev = []
    with open('co_trans_rev.csv', mode='r') as f:
        for line in map(str.strip, f):
            co_trans_rev.append([int(i) for i in line.replace('\n', '').split(',')])
    # neary_Mettez à jour le tableau résolu, mais préparez d'autres tableaux pour accélérer le calcul
    neary_solved = []
    neary_solved_idx = set()
    neary_solved_cost_dic = {}
    neary_solved_idx_dic = {}
    #Créer une file d'attente pour la recherche de priorité de largeur
    solved_cp_idx = [cp2idx(i) for i in solved_cp]
    solved_co_idx = [co2idx(i) for i in solved_co]
    que = deque([])
    for i in range(24):
        twisted_idx = solved_cp_idx[i] * 2187 + solved_co_idx[i]
        neary_solved_idx.add(twisted_idx)
        neary_solved_cost_dic[twisted_idx] = 0
        neary_solved_idx_dic[twisted_idx] = len(neary_solved)
        neary_solved.append([twisted_idx, 0, []])
        que.append([solved_cp_idx[i], solved_co_idx[i], 0, [], 2])
    twists = [range(6, 12), range(6), range(12)]
    cnt = 0
    while que:
        cnt += 1
        if cnt % 1000 == 0:
            print(cnt, len(que))
        #Obtenir l'état de la file d'attente
        cp_idx, co_idx, cost, move, mode = que.popleft()
        for twist in twists[mode]:
            #Obtenir l'état et le coût après la rotation, mettre à jour la liste des procédures
            cost_pls = cost_lst[twist]
            twisted_cp_idx = cp_trans_rev[cp_idx][twist]
            twisted_co_idx = co_trans_rev[co_idx][twist]
            twisted_idx = twisted_cp_idx * 2187 + twisted_co_idx
            n_cost = cost + grip_cost + cost_pls
            n_mode = twist // 6
            n_move = [i for i in move]
            n_move.append(twist)
            if neary_solved_depth >= n_cost and not twisted_idx in neary_solved_idx:
                #Si tu le vois à nouveau
                neary_solved_idx.add(twisted_idx)
                neary_solved_cost_dic[twisted_idx] = n_cost
                neary_solved_idx_dic[twisted_idx] = len(neary_solved)
                neary_solved.append([twisted_idx, n_cost, list(reversed(n_move))])
                que.append([twisted_cp_idx, twisted_co_idx, n_cost, n_move, n_mode])
            elif neary_solved_depth >= n_cost and neary_solved_cost_dic[twisted_idx] > n_cost:
                #Si vous l'avez déjà vu, mais que vous pouvez y accéder à un coût inférieur à ce moment-là
                neary_solved_cost_dic[twisted_idx] = n_cost
                neary_solved[neary_solved_idx_dic[twisted_idx]] = [twisted_idx, n_cost, list(reversed(n_move))]
                que.append([twisted_cp_idx, twisted_co_idx, n_cost, n_move, n_mode])
    #Étant donné que la partie solveur utilise une recherche de 2 minutes, effectuez un tri par index à l'avance.
    neary_solved.sort()
    #Enregistrer l'index et le coût au format CSV
    with open('neary_solved_idx.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in [i[:2] for i in neary_solved]:
            writer.writerow(line)
    #Enregistrer la procédure dans un tableau CSV
    with open('neary_solved_solution.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in [i[2] for i in neary_solved]:
            writer.writerow(line)
    print('neary solved done')

Résumé

Cette fois, nous avons précalculé différentes séquences utilisées pour la recherche de solution du cube Rubik. En fait, le tableau cible est créé en exécutant toutes les fonctions introduites. Le solveur lit ces tableaux et les utilise dans la recherche de solution.

[PYTHON] Logiciel mis à jour pour Rubik Cube Robot 2. Pré-calcul