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 (dieser Artikel)
Lösungssuche
Statuserkennung
Maschinenbetrieb (Python)
Maschinenbetrieb (Arduino)
Hauptverarbeitung

Dieses Mal werden wir `create_array.py `als Vorberechnungsausgabe einführen.

Import von Bibliotheken etc.

Importieren Sie die Bibliothek und die Basisfunktionen (https://qiita.com/Nyanyan_Cube/items/e225e8e31897d81a1401).

from collections import deque
import csv

from basic_functions import *

Erstellen Sie eine Zustandsübergangstabelle

Die im vorherigen Artikel erstellte Zustandsübergangsfunktion ist etwas langsam. Es wird einige Zeit dauern, diese Funktion zu verwenden, um den Zustand in Zukunft hunderttausend und millionenfach zu ändern. Um den Zustandsübergang sofort zu beenden (mit dem Berechnungsbetrag $ O (1) $), erstellen Sie daher ein Zustandsübergangsarray.

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

Erstellen Sie eine Übergangssequenz, die wird.

'''Erstellen Sie eine Zustandsübergangstabelle'''
''' Create state transition tables '''

def create_cp_trans():
    #CP-Übergangssequenz
    # 8!Beschreibt den Übergang mit 12 Rotationstypen für jeden einzelnen Zustand
    cp_trans = [[-1 for _ in range(12)] for _ in range(fac[8])]
    #Drehen Sie die Nummer idx, die den Status vor dem Übergang darstellt
    for idx in range(fac[8]):
        if idx % 1000 == 0:
            print(idx / fac[8])
        #Erstellen Sie eine CP-Sequenz aus idx und drehen Sie sie tatsächlich
        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)
            #Konvertieren Sie das CP-Array in eine eindeutige Nummer
            twisted_idx = cp2idx(twisted_cp)
            cp_trans[idx][i] = twisted_idx
    #In CSV-Datei speichern
    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():
    #Der Inhalt des Prozesses wird erstellt_cp_Nur trans CP wurde 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')

Füllen Sie das Array effizient mit der Funktion, die in der Grundfunktion zwischen dem Statusarray und der Statusnummer umschaltet, und speichern Sie das zuletzt erstellte Array in einer CSV-Datei.

Das für die Rotation verwendete `` `turn_lst``` ist die Anordnung, die in den vorherigen Grundfunktionen verwendet wurde, und ist das ursprüngliche Rotationssymbol des Puzzles. Es ist eine Zusammenfassung von.

Erstellen Sie ein Bereinigungsarray

Wenn Sie tatsächlich nach einer Lösung für ein Rätsel suchen, wird die Suche gestoppt, wenn bekannt ist, dass "die Lösung niemals gefunden werden kann, selbst wenn Sie weiter suchen". Dies wird als Beschneiden bezeichnet.

Mit diesem Bereinigungsarray wird überprüft, ob durch weitere Suche keine Lösung gefunden werden kann. In dieser Sequenz werden CP und CO getrennt aufgezeichnet und wie viel mehr Kosten für jeden Zustand erforderlich sind. CP und CO sind übrigens getrennt, da die Anzahl der Zustände explosionsartig zunimmt und die Speichernutzung enorm wird, wenn beide berücksichtigt werden.

'''Erstellen Sie ein Bereinigungsarray'''
''' Create prunning tables '''

def create_cp_cost():
    #Lesen Sie das Statusübergangsarray
    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!Berechnen Sie die Kosten für jeden Staat
    cp_cost = [1000 for _ in range(fac[8])]
    #Die Suche nach Breitenpriorität wird durchgeführt, also die erste in der Warteschlange(Ausgerichtet)Setzen Sie den Staat
    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
    #Suche nach Breitenpriorität
    while que:
        cnt += 1
        if cnt % 1000 == 0:
            print(cnt, len(que))
        #Status aus Warteschlange abrufen
        cp, cost = que.popleft()
        twists = range(12)
        #Kosten drehen und berechnen
        for twist, cost_pls in zip(twists, cost_lst):
            twisted_idx = cp_trans[cp][twist]
            n_cost = cost + grip_cost + cost_pls
            #Aktualisieren Sie das Array, wenn eine Kostenaktualisierung vorliegt, und fügen Sie es der Warteschlange hinzu
            if cp_cost[twisted_idx] > n_cost:
                cp_cost[twisted_idx] = n_cost
                que.append([twisted_idx, n_cost])
    #In CSV-Datei speichern
    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():
    #Der Inhalt des Prozesses wird erstellt_cp_Nur trans CP wurde 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')

Die Grundverarbeitung erfolgt durch Suche nach Breitenpriorität. Setzen Sie die 24 Arten von Zuständen, die anfänglich ausgerichtet sind (es gibt 24 verschiedene Zustände, abhängig von der Betrachtungsrichtung, auch im selben Puzzle), und erhalten Sie den Status aus der Warteschlange in der Anweisung "` while ". Wird nacheinander verarbeitet.

Verwenden Sie für den Rotationsprozess das Übergangsarray in dem zuvor erstellten Status. Natürlich können Sie es tun, ohne es zu verwenden, aber es dauert eine Größenordnung länger.

Listen Sie die Zustände auf, die in Kürze fertig sein werden

Bei der Lösungssuche verwende ich IDA *, den am besten geeigneten Algorithmus für die Lösungssuche des Rubik-Cubes. Siehe / items / 60f3699db96dba4a4bf5)). Dieses Programm sucht nach einer Lösung, um die Kosten zu minimieren: ** Ein Wert, der nahe an der Zeit liegt, die zum Lösen des Puzzles benötigt wird **. Wenn Sie dies verwenden, ist die Suche schwerer als bei Verwendung anderer Indikatoren, z. B. Aufwand. Wenn das Rätsel zu einem bestimmten Preis oder mehr gelöst wurde, wurde die Suche dort beendet und die vorberechneten Lösungen wurden kombiniert, um die gesamte Lösung zu bilden. Abhängig vom Speicher und der Berechnungszeit muss entschieden werden, wie viele "Zustände, die in kurzer Zeit gelöst werden können" aufgelistet sind.

Diese Zustandsaufzählung muss durch umgekehrte Drehung von dem Zustand erstellt werden, in dem die Rätsel abgeschlossen sind. Erstellen Sie daher zunächst ein Zustandsübergangsarray für die Rückwärtsrotation. Danach ist die Hauptgeschichte.

Teil 1 Erstellen Sie ein Zustandsübergangsarray durch umgekehrte Drehung

Erstellen Sie, wie oben erwähnt, ein Zustandsübergangsarray für die umgekehrte Drehung der Puzzleprozedur. An diesem Punkt fragen Sie sich möglicherweise, ob Sie das zuvor erstellte Übergangsarray wiederverwenden können. Aufgrund der Struktur des Roboters ist die umgekehrte Drehung jedoch nicht in dem zuvor erstellten Array enthalten. Dies liegt an der Struktur, dass der Roboter das Puzzle immer nur gegen den Uhrzeigersinn drehen kann. Weitere Informationen finden Sie unter Hardware-Edition von "Machen wir einen Roboter, der den Zauberwürfel löst!".

'''Erstellen Sie ein Statusübergangsarray, wenn die umgekehrte Prozedur aktiviert ist'''
''' Create state transition tables for reverse twists'''

def create_cp_trans_rev():
    #Der grundlegende Prozess ist erstellen_cp_Gleich wie 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_Im Gegensatz zu trans, cp_trans_rev[twisted_idx][i]Aktualisieren
            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():
    #Der grundlegende Prozess ist erstellen_co_Gleich wie 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_Im Gegensatz zu trans, co_trans_rev[twisted_idx][i]Aktualisieren
            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')

Vorheriger Zustand Es ist dem Programm sehr ähnlich, als die Faseranordnung gemacht wurde, aber es gibt einen Unterschied.

Umkehrrotationszustandsübergangsarray[Nummer nach Drehung][Rotationsnummer] =Nummer vor der Drehung

Hier müssen Sie.

Teil 2 Listen Sie die Zustände auf, die bald fertig sein werden

Verwenden Sie die Suche mit Breitenpriorität, um Zustände aufzulisten. Aber,

Staatsnummer
Kosten von diesem Zustand bis zur Fertigstellung
Verfahren von diesem Zustand bis zum Abschluss

Es ist ein wenig mühsam, weil es notwendig ist, viele Parameter zu halten.

Auch wenn Sie bereits besucht haben, können Sie es möglicherweise zu geringeren Kosten als bei Ihrem vorherigen Besuch fertigstellen. Um den Rechenaufwand in diesem Fall zu verringern, verwenden Sie "Neary_solved_idx", "Neary_solved_cost_dic", "Neary_solved_idx_dic" (obwohl diese Methode etwas redundant ist und ich denke, es gibt einen besseren Weg).

Bei der eigentlichen Lösungssuche werden die Elemente in diesem Array unter Verwendung einer Dichotomie unter Verwendung einer Kombination von CP- und CO-Zahlen erhalten. Daher wird das resultierende Array sortiert und dann gespeichert.

'''Listen Sie die Zustände auf, die in Kürze fertig sein werden'''
''' Create array of states that can be solved soon '''

def create_neary_solved():
    #Lesen Sie das Reverse Procedure Transition Array
    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_Wir werden das gelöste Array aktualisieren, aber andere Arrays vorbereiten, um die Berechnung zu beschleunigen.
    neary_solved = []
    neary_solved_idx = set()
    neary_solved_cost_dic = {}
    neary_solved_idx_dic = {}
    #Erstellen Sie eine Warteschlange für die Suche nach Breitenprioritäten
    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))
        #Status aus Warteschlange abrufen
        cp_idx, co_idx, cost, move, mode = que.popleft()
        for twist in twists[mode]:
            #Status und Kosten nach der Rotation abrufen, Verfahrensliste aktualisieren
            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:
                #Wenn Sie es neu sehen
                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:
                #Wenn Sie es bereits gesehen haben, es aber zu geringeren Kosten als zu diesem Zeitpunkt erreichen können
                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])
    #Da der Solver-Teil eine 2-minütige Suche verwendet, sortieren Sie im Voraus nach Index.
    neary_solved.sort()
    #Speichern Sie Index und Kosten in 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)
    #Speichern Sie die Prozedur in einem CSV-Array
    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')

Zusammenfassung

Dieses Mal haben wir verschiedene Sequenzen vorberechnet, die für die Lösungssuche des Rubik-Würfels verwendet wurden. Tatsächlich wird das Zielarray durch Ausführen aller eingeführten Funktionen erstellt. Der Solver liest diese Arrays und verwendet sie bei der Lösungssuche.

[PYTHON] Aktualisierte Software für Rubik Cube Robot 2. Vorberechnung