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).

Importer des fonctions de base

Importez les fonctions introduites dans Fonctions de base

from basic_functions import *

Variables globales

Variables et tableaux placés globalement.

'''Lire le tableau'''
''' Load arrays '''

with open('cp_cost.csv', mode='r') as f:
    cp_cost = [int(i) for i in f.readline().replace('\n', '').split(',')]
with open('co_cost.csv', mode='r') as f:
    co_cost = [int(i) for i in f.readline().replace('\n', '').split(',')]
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(',')])
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(',')])
neary_solved_idx = []
with open('neary_solved_idx.csv', mode='r') as f:
    for line in map(str.strip, f):
        neary_solved_idx.append([int(i) for i in line.replace('\n', '').split(',')])
neary_solved_solution = []
with open('neary_solved_solution.csv', mode='r') as f:
    for line in map(str.strip, f):
        if line.replace('\n', '') == '':
            neary_solved_solution.append([])
        else:
            neary_solved_solution.append([int(i) for i in line.replace('\n', '').split(',')])


len_neary_solved = len(neary_solved_idx)
solution = []
solved_cp_idx = 0
solved_co_idx = 0

L'opération d'élagage et de retournement du puzzle, et l'état d'être prêt dans peu de temps sont lus à partir du fichier CSV.

De plus, le tableau `` solution '' est utilisé pour la recherche de solution, et la solution est stockée dans ce tableau en ajoutant / supprimant des éléments ici.

Créer un tableau d'états de puzzle à partir d'états de couleur

C'est un peu compliqué. Listez manuellement les couleurs de chaque partie du puzzle et leur ordre (l'ordre dans lequel les couleurs apparaissent lorsque vous regardez les pièces dans le sens des aiguilles d'une montre à partir de la diagonale au-dessus), et recherchez les pièces correspondantes une par une. Aller.

C'est une erreur si toutes les couleurs n'apparaissent pas dans 4 couleurs, si les mêmes pièces apparaissent plus d'une fois ou s'il y a des pièces qui ne rentrent dans aucune des pièces candidates. La gestion des erreurs ici était assez gênante.

'''Créer un tableau d'état de puzzle à partir des informations de couleur'''
''' Create CO and CP arrays from the colors of stickers '''

def create_arr(colors):
    #Vérifiez si toutes les couleurs apparaissent 4 chacune
    for i in j2color:
        cnt = 0
        for j in colors:
            if i in j:
                cnt += j.count(i)
        if cnt != 4:
            return -1, -1
    cp = [-1 for _ in range(8)]
    co = [-1 for _ in range(8)]
    set_parts_color = [set(i) for i in parts_color]
    #Remplissez CP et CO un par un
    for i in range(8):
        tmp = []
        for j in range(3):
            tmp.append(colors[parts_place[i][j][0]][parts_place[i][j][1]])
        tmp1 = 'w' if 'w' in tmp else 'y'
        co[i] = tmp.index(tmp1)
        if not set(tmp) in set_parts_color:
            return -1, -1
        cp[i] = set_parts_color.index(set(tmp))
    tmp2 = list(set(range(7)) - set(cp))
    if tmp2:
        tmp2 = tmp2[0]
        for i in range(7):
            if cp[i] > tmp2:
                cp[i] -= 1
    return cp, co

Je suis désolé d'utiliser beaucoup de noms de variables sans signification. Il est difficile de penser à des noms de variables, mais je vais vous parler de moi-même dans le passé.

Trouvez la distance entre l'état du puzzle et la solution

Puisqu'il est utilisé pour l'élagage pendant l'exploration, il est nécessaire de connaître la distance entre l'état du puzzle et la solution.

'''Renvoie la distance entre cet état et la solution'''
''' Returns the distance between the state and the solved state '''

def distance(cp_idx, co_idx):
    #Renvoie la valeur maximale de chaque coût minimum lorsque seuls CP et CO sont alignés
    return max(cp_cost[cp_idx], co_cost[co_idx])

Cette fonction renvoie les valeurs maximales de «Coût minimum pour aligner uniquement CP» et «Coût minimum pour aligner uniquement CO». Ce nombre est égal ou inférieur au coût d'alignement réel du CP et du CO, n'est-ce pas? Si la valeur retournée par la fonction `` distance '' est $ h (cp, co) $ et le coût réel est $ h ^ * (cp, co) $

h(cp, co) \leq h^*(cp, co)

à propos de ça. À ce stade, on dit que c'est ** acceptable **, et la procédure la plus courte peut toujours être recherchée.

Tourne le puzzle

L'acte de tourner le puzzle se fait au niveau de l'index. En d'autres termes, au lieu de créer un tableau d'énigmes et de les remplacer, vous pouvez simplement regarder le tableau en utilisant les nombres qui représentent l'état du puzzle. Utilisez la table créée lors du précédent pré-calcul.

'''Changer l'état du puzzle à l'aide de la table de transition'''
''' Change the state using transition tables '''

def move(cp_idx, co_idx, twist):
    return cp_trans[cp_idx][twist], co_trans[co_idx][twist]

Où co_trans et `` cp_trans sont des tableaux qui représentent des transitions. à propos de ça,

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

est. Faites une transition à chacun des CP et CO.

Recherche de bisection

La dichotomie est utilisée pour rechercher un tableau qui énumère les «états disponibles à faible coût et leurs solutions» créés dans Pre-calcul.

Ce tableau est trié par la valeur combinée de CP et CO ($ cp \ times2187 + co $: où 2187 est la valeur maximale de CO + 1). Cependant, cette clé n'est pas représentée sous la forme d'un entier continu et il est difficile de trouver le nombre souhaité parmi eux.

Par conséquent, nous utilisons une dichotomie. La dichotomie est le nombre de calculs de $ \ log_2N $ (où le 2 du bas est souvent omis), à proprement parler, une boucle, pour trouver l'élément désiré dans un tableau trié d'éléments $ N $. J'ai fini. Si vous le regardez normalement, vous pouvez imaginer qu'il est extrêmement rapide étant donné qu'il nécessite un maximum de $ N $ boucles. À titre d'exemple, regardons la valeur de $ \ log N $ à $ N = 100, 100000, 1000000000 = 10 ^ 2, 10 ^ 5, 10 ^ 9 $.

N	\log N
10^2	6.6
10^5	16.6
10^9	29.9

Au fur et à mesure que $ N $ croît, une énorme différence apparaît.

'''Recherche de bisection'''
''' Binary search '''

def bin_search(num):
    #Neary en dichotomie_Trouvez l'index souhaité dans résolu
    l = 0
    r = len_neary_solved
    while r - l > 1:
        c = (l + r) // 2
        if neary_solved_idx[c][0] == num:
            return c
        elif neary_solved_idx[c][0] > num:
            r = c
        else:
            l = c
    if r == len_neary_solved:
        return -1
    if num == neary_solved_idx[l][0]:
        return l
    elif num == neary_solved_idx[r][0]:
        return r
    else:
        return -1

Recherche de priorité de profondeur

Le contenu de la recherche IDA *, qui est le corps principal de la recherche de solution, utilise une recherche prioritaire en profondeur (à proprement parler, cela peut être un peu différent). La recherche de priorité de profondeur peut être écrite proprement en l'implémentant de manière récursive, je l'ai donc implémentée de manière récursive. En gros, utilisez les fonctions introduites jusqu'à présent pour effectuer une rotation, calculez le coût, puis rappelez-vous. À ce stade, il suffit d'ajouter / supprimer des éléments (numéros de rotation) au tableau solution``` placé dans la variable globale, et lorsqu'ils sont alignés (lorsque True``` est retourné) Le tableau solution '' est la solution. C'est le point rafraîchissant de la récurrence.

'''Recherche de priorité de profondeur'''
''' Depth-first search '''

def search(cp_idx, co_idx, depth, mode):
    global solution
    #Utilisez la rotation dans le sens perpendiculaire à la dernière main
    twist_idx_lst = [range(6, 12), range(6), range(12)]
    for twist in twist_idx_lst[mode]:
        #Faites pivoter le puzzle
        cost = cost_lst[twist]
        n_cp_idx, n_co_idx = move(cp_idx, co_idx, twist)
        #Mettre à jour la profondeur restante
        n_depth = depth - cost - grip_cost
        #Calculez la valeur à utiliser pour la prochaine récurrence
        n_mode = twist // 6
        n_dis = distance(n_cp_idx, n_co_idx)
        if n_dis > n_depth:
            continue
        #Ajouter des éléments au tableau de procédures global
        solution.append(twist)
        #Si vous êtes dans un état où vous pouvez l'obtenir à un faible coût calculé à l'avance
        if n_dis <= neary_solved_depth <= n_depth:
            tmp = bin_search(n_cp_idx * 2187 + n_co_idx)
            if tmp >= 0 and neary_solved_solution[tmp][0] // 6 != solution[-1] // 6:
                solution.extend(neary_solved_solution[tmp])
                return True, grip_cost + neary_solved_idx[tmp][1]
        #Explorer la prochaine profondeur
        tmp, ans_cost = search(n_cp_idx, n_co_idx, n_depth, n_mode)
        if tmp:
            return True, ans_cost
        #Si aucune solution n'est trouvée, pop l'élément du tableau de procédure globale
        solution.pop()
    return False, -1

Recherche IDA *

C'est finalement Honmaru. Cela dit, la recherche IDA * n'est pas une mise en œuvre compliquée, car elle n'effectue que des recherches à priorité de profondeur plusieurs fois tout en augmentant la profondeur maximale.

S'il est à l'état "bientôt prêt" avant la recherche, il ne sera pas recherché. Lors de la recherche, la recherche de priorité à la profondeur est effectuée en augmentant la `` profondeur '' dans l'ordre à partir de 1. Lorsqu'une solution est trouvée, la recherche est abandonnée et la solution (convertie pour faciliter le processus suivant) est renvoyée.

''' IDA*chercher'''
''' IDA* algorithm '''

def solver(colors):
    global solution
    #Rechercher les index CP et CO
    cp, co = create_arr(colors)
    if cp == -1 or co == -1:
        return -1, -1
    cp_idx = cp2idx(cp)
    co_idx = co2idx(co)
    #Si vous connaissez déjà la réponse avant d'explorer
    if distance(cp_idx, co_idx) <= neary_solved_depth:
        tmp = bin_search(cp_idx * 2187 + co_idx)
        if tmp >= 0:
            return [twist_lst[i] for i in neary_solved_solution[tmp]], neary_solved_idx[tmp][1]
    res_cost = 0
    # IDA*
    for depth in range(1, 34):
        solution = []
        tmp, cost = search(cp_idx, co_idx, depth, 2)
        if tmp:
            res_cost = depth + cost
            break
    if solution == []:
        return -1, res_cost
    return [twist_lst[i] for i in solution], res_cost

Résumé

Cette fois, j'ai expliqué le programme de recherche de solutions, qui est le plus intéressant (je pense) de ce robot. Je pense que la méthode décrite ici peut être utilisée pour résoudre diverses autres énigmes. J'espère que cela sera utile pour ceux qui veulent résoudre des énigmes.

[PYTHON] Logiciel mis à jour pour Rubik Cube Robot 3. Recherche de solutions