Was ist dieser Artikel?

Ich entwickle gerade einen Roboter, der einen 2x2x2 Rubikwürfel löst. Dies ist eine Sammlung von Kommentaren zum Roboterprogramm. Ich habe einmal eine Sammlung von Artikeln geschrieben, die durch den Artikel [hier] repräsentiert werden (https://qiita.com/Nyanyan_Cube/items/60f3699db96dba4a4bf5), aber seitdem wurde die Software erheblich aktualisiert, sodass ich ein neues Programm einführen werde. Überlegen.

Der entsprechende Code ist hier verfügbar [https://github.com/Nyanyan/soltvvo/tree/master/Soltvvo3.2].

Zum Thema passende Artikel

"Lass uns einen Roboter bauen, der den Zauberwürfel löst!"

Aktualisierte Software für Rubik Cube Robot

Grundfunktion
Vorberechnung
Lösungssuche (dieser Artikel)
Statuserkennung
Maschinenbetrieb (Python)
Maschinenbetrieb (Arduino)
Hauptverarbeitung

Dieses Mal werden wir `` `solver.py``` als Edition für die Lösungssuche einführen.

Grundfunktionen importieren

Importieren Sie die in [Grundfunktionen] eingeführten Funktionen (https://qiita.com/Nyanyan_Cube/items/e225e8e31897d81a1401).

from basic_functions import *

Globale Variablen

Global platzierte Variablen und Arrays.

'''Array lesen'''
''' 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

Der Vorgang des Beschneidens und Drehens des Puzzles und der Zustand der Bereitschaft in kurzer Zeit werden aus der CSV-Datei gelesen.

Außerdem wird das Array "Lösung" für die Lösungssuche verwendet, und die Lösung wird in diesem Array gespeichert, indem hier Elemente hinzugefügt / gelöscht werden.

Erstellen Sie aus Farbzuständen ein Puzzle-Status-Array

Das ist etwas kompliziert. Listen Sie die Farben in jedem Teil des Puzzles und ihre Reihenfolge (die Reihenfolge, in der die Farben erscheinen, wenn Sie die Teile von oben diagonal im Uhrzeigersinn betrachten) manuell auf und suchen Sie nacheinander nach den passenden Teilen. Gehen.

Es ist ein Fehler, wenn nicht alle Farben in 4 Farben angezeigt werden, dieselben Teile mehr als einmal angezeigt werden oder Teile vorhanden sind, die nicht in einen der Teilekandidaten passen. Die Fehlerbehandlung hier war ziemlich mühsam.

'''Erstellen Sie ein Puzzle-Status-Array aus Farbinformationen'''
''' Create CO and CP arrays from the colors of stickers '''

def create_arr(colors):
    #Überprüfen Sie, ob alle Farben jeweils 4 erscheinen
    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]
    #Füllen Sie CP und CO nacheinander
    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

Es tut mir leid, viele bedeutungslose Variablennamen zu verwenden. Es ist schwer, sich Variablennamen vorzustellen, aber ich werde Ihnen in der Vergangenheit viel über mich erzählen.

Finden Sie den Abstand zwischen dem Zustand des Puzzles und der Lösung

Da es während der Erkundung zum Beschneiden verwendet wird, muss die Entfernung vom Zustand des Puzzles zur Lösung bekannt sein.

'''Gibt die Entfernung von diesem Zustand zur Lösung zurück'''
''' Returns the distance between the state and the solved state '''

def distance(cp_idx, co_idx):
    #Gibt den Maximalwert aller minimalen Kosten zurück, wenn nur CP und CO ausgerichtet sind
    return max(cp_cost[cp_idx], co_cost[co_idx])

Diese Funktion gibt die Maximalwerte "Minimale Kosten für die Ausrichtung nur von CP" und "Mindestkosten für die Ausrichtung nur von CO" zurück. Diese Zahl ist gleich oder geringer als die Kosten für die tatsächliche Ausrichtung von CP und CO, nicht wahr? Angenommen, der von der Funktion `` `distance``` zurückgegebene Wert ist $ h (cp, co) $ und die tatsächlichen Kosten sind $ h ^ * (cp, co) $

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

darüber. Zu diesem Zeitpunkt wird gesagt, dass es ** akzeptabel ** ist und das kürzeste Verfahren immer gesucht werden kann.

Drehe das Puzzle

Das Drehen des Puzzles erfolgt auf Indexebene. Mit anderen Worten, anstatt eine Reihe von Rätseln zu erstellen und diese zu ersetzen, können Sie die Tabelle einfach anhand der Zahlen betrachten, die den Status des Puzzles darstellen. Verwenden Sie die in der vorherigen [Vorberechnung] erstellte Tabelle (https://qiita.com/Nyanyan_Cube/items/495a32adf4bfe970e100).

'''Ändern Sie den Status des Puzzles mithilfe der Übergangstabelle'''
''' Change the state using transition tables '''

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

Wobei `co_trans``` und` cp_trans``` Arrays sind, die Übergänge darstellen. darüber,

Übergangsarray[Geben Sie die Nummer vor der Drehung an][Rotationsnummer] ==Statusnummer nach der Drehung

ist. Machen Sie jeweils einen Übergang bei CP und CO.

Halbierungssuche

Die Dichotomie wird verwendet, um nach einem Array zu suchen, das "Zustände, die zu geringen Kosten verfügbar sind, und deren Lösungen" auflistet, die in Vorberechnung erstellt wurden.

Dieses Array ist nach dem kombinierten Wert von CP und CO sortiert ($ cp \ times2187 + co $: wobei 2187 der Maximalwert von CO + 1 ist). Dieser Schlüssel wird jedoch nicht als fortlaufende Ganzzahl dargestellt, und es ist schwierig, die gewünschte Zahl unter ihnen zu finden.

Daher verwenden wir eine Dichotomie. Die Dichotomie ist die Anzahl der Berechnungen von $ \ log_2N $ (wobei die unteren 2 häufig weggelassen werden), genau genommen eine Schleife, um das gewünschte Element in einem sortierten Array von $ N $ -Elementen zu finden. Ich bin fertig. Wenn Sie es normal betrachten, können Sie sich vorstellen, dass es überwältigend schnell ist, wenn man bedenkt, dass es maximal $ N $ Schleifen erfordert. Schauen wir uns als Beispiel den Wert von $ \ log N $ bei $ N = 100, 100000, 1000000000 = 10 ^ 2, 10 ^ 5, 10 ^ 9 $ an.

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

Wenn $ N $ wächst, erscheint ein enormer Unterschied.

'''Halbierungssuche'''
''' Binary search '''

def bin_search(num):
    #Fast in Dichotomie_Finden Sie den gewünschten Index in gelöst
    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

Tiefenprioritätssuche

Der Inhalt der IDA * -Suche, die den Hauptteil der Lösungssuche darstellt, verwendet eine Suche mit Tiefenpriorität (genau genommen kann dies etwas anders sein). Die Suche nach Tiefenpriorität kann durch rekursives Implementieren sauber geschrieben werden, daher habe ich sie rekursiv implementiert. Verwenden Sie grundsätzlich die bisher eingeführten Funktionen, um zu drehen, die Kosten zu berechnen und sich dann erneut anzurufen. Zu diesem Zeitpunkt fügen Sie einfach Elemente (Rotationsnummern) zum Array `solution``` hinzu, das in der globalen Variablen platziert ist, und wenn sie ausgerichtet sind (wenn` True``` zurückgegeben wird) `` Das Array "Lösung" ist die Lösung. Dies ist der erfrischende Punkt der Wiederholung.

'''Tiefenprioritätssuche'''
''' Depth-first search '''

def search(cp_idx, co_idx, depth, mode):
    global solution
    #Verwenden Sie die Drehung in der Richtung senkrecht zur letzten Hand
    twist_idx_lst = [range(6, 12), range(6), range(12)]
    for twist in twist_idx_lst[mode]:
        #Drehe das Puzzle
        cost = cost_lst[twist]
        n_cp_idx, n_co_idx = move(cp_idx, co_idx, twist)
        #Aktualisieren Sie die verbleibende Tiefe
        n_depth = depth - cost - grip_cost
        #Berechnen Sie den Wert, der für die nächste Wiederholung verwendet werden soll
        n_mode = twist // 6
        n_dis = distance(n_cp_idx, n_co_idx)
        if n_dis > n_depth:
            continue
        #Fügen Sie dem globalen Prozedurarray Elemente hinzu
        solution.append(twist)
        #Wenn Sie sich in einem Zustand befinden, in dem Sie es zu niedrigen Kosten erhalten können, die im Voraus berechnet wurden
        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]
        #Die nächste Tiefe erkunden
        tmp, ans_cost = search(n_cp_idx, n_co_idx, n_depth, n_mode)
        if tmp:
            return True, ans_cost
        #Wenn keine Lösung gefunden wird, fügen Sie das Element aus dem globalen Prozedurarray hinzu
        solution.pop()
    return False, -1

IDA * Suche

Es ist endlich Honmaru. Die IDA * -Suche ist jedoch keine komplizierte Implementierung, da sie nur mehrmals Suchvorgänge mit Tiefenpriorität durchführt und gleichzeitig die maximale Tiefe erhöht.

Wenn es sich vor der Suche im Status "Bereit" befindet, wird es nicht durchsucht. Bei der Suche wird die Tiefenprioritätssuche durchgeführt, während die Tiefe in der Reihenfolge von 1 erhöht wird. Wenn eine Lösung gefunden wird, wird die Suche abgebrochen und die Lösung (konvertiert, um den nächsten Prozess zu erleichtern) zurückgegeben.

''' IDA*Suche'''
''' IDA* algorithm '''

def solver(colors):
    global solution
    #Finden Sie CP- und CO-Indizes
    cp, co = create_arr(colors)
    if cp == -1 or co == -1:
        return -1, -1
    cp_idx = cp2idx(cp)
    co_idx = co2idx(co)
    #Wenn Sie die Antwort bereits kennen, bevor Sie sie erkunden
    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

Zusammenfassung

Dieses Mal erklärte ich das Lösungssuchprogramm, das meiner Meinung nach das interessanteste (meiner Meinung nach) ist. Ich denke, die hier beschriebene Methode kann verwendet werden, um verschiedene andere Rätsel zu lösen. Ich hoffe, es ist hilfreich für diejenigen, die Rätsel lösen wollen.

[PYTHON] Aktualisierte Software für Rubik Cube Robot 3. Lösungssuche