Sequenzgenerierung/ Breite zuerst suchen

Question

Im Wesentlichen versuche ich, einen Rubik -Würfel mit einer breiten Suche nach allen möglichen Bewegungen zu lösen. Ich weiß, dass dies nicht der beste Weg ist, um den Würfel zu lösen, aber ich brauche ihn nur für sehr kurze Sequenzen (daher ist es unwahrscheinlich, die Stromsequenz.

Ich versuche einen Weg zu finden, immer mehr Zahlenstränge zu drucken (0,1,2,00,01,02 ...), sodass ich einfach jede in eine Funktion einfügen kann, um zu überprüfen, ob diese bestimmte Abfolge von Moves löst den Würfel, aber ich habe Probleme, eine Möglichkeit zu finden, die Sequenz auf unbestimmte Zeit fortzusetzen.

Bisher ist alles, was ich geschafft habe, für Loops verschachtelt, aber jedes Mal, wenn die Suche tiefer wird, muss es eine weitere Schleife geben. Hat jemand eine Idee, wie ich dieses Problem angehen kann?

Tut mir leid, wenn ich zu vage war, könnte ich einen Aufsatz darüber schreiben, was ich versuche zu tun, aber ich dachte, ich würde versuchen, es einfach zu halten.

Answer 1

Ich bin nicht sehr vertraut mit dem, was in den Java -Bibliotheken ist. Entschuldigung, wenn dies etwas implementiert, das bereits da ist, aber wenn ich dies von Grund auf neu schreiben würde, würde ich wahrscheinlich so etwas tun:

public class Enumerator {
    private int maxDepth;
    private int currentDepth;
    private int currentPerm;
    private String alphabet;

    public Enumerator(String alphabet, int d) {
        this.maxDepth = d;
        this.currentDepth = 1;
        this.currentPerm = 0;
        this.alphabet = alphabet;
    }

    public boolean next() {
        int numPermutations = (int) Math.pow(alphabet.length(), this.currentDepth);
        boolean res=false;

        // finished if
        if ((this.currentDepth == this.maxDepth) && 
            (this.currentPerm == numPermutations - 1)) {
            res = false;
        }
        // next perm at this depth
        else if (this.currentPerm < numPermutations - 1) {
            this.currentPerm++;
            res = true;
        }
        // next depth
        else if (this.currentDepth <= this.maxDepth) {
            this.currentDepth++;
            this.currentPerm = 0;
            res = true;
        }
        return res;
    }

    public String getPermutation() {
        int tmpPerm = this.currentPerm;
        String res = "";
        for (int i=0; i<this.currentDepth; i++) {
          int ind = tmpPerm % this.alphabet.length();
          res = this.alphabet.charAt(ind) + res;
          tmpPerm /= this.alphabet.length();
        }
        return res;
    }

    public static void main(String args[]) {
        int depth = 3;
        String alphabet = "012";
        Enumerator e = new Enumerator(alphabet, depth); 
        do {
            System.out.println(e.getPermutation());
        } while (e.next());
    }
}

Auf diese Weise können Sie Sequenzen von Alphabeten willkürlicher Symbole bis zu einer willkürlichen Tiefe aufzählen. Dies macht auch das, was Sie wollen, wenn es über die Tiefe iteriert und für jede Tiefe den gesamten Satz möglicher Sequenzen erzeugt. Es könnte auch mit Rekursion geschehen, wie Gian sagt, was eleganter sein könnte. In Python würde ich dafür eine Generatorfunktion verwenden, aber ich bin mit etwas Ähnlichem in Java nicht vertraut.

Answer 2

Klingt so, als ob Sie eine rekursive Lösung wünschen, sodass Ihre Funktion eine Liste von Nachfolgerbewegungen erzeugt, die eine Sequenz als Eingabe haben. In diesem Fall können Sie die Funktion einfach so oft wie erforderlich aufrufen.

Answer 3

Würde eine rekursive Funktion das nicht tun? Sie können die Tiefe der Rekursion einschränken und sie allmählich vertiefen.

Update] Die Funktion übergeben und die Tiefe angeben; Dekrementieren Sie jedes Mal, wenn Sie wieder aufnehmen, den Wert - prüfen Sie, ob er Null ist, und geben Sie zurück, wenn ja.

Geben Sie für die Werte eine Sammlung von Zeichenfolgen oder Stringbuildern in die rekursive Funktion ein. Jede Ebene liest (und beseitigt) die Werte aus der vorherigen Ebene, wendet alle möglichen nächsten Bewegungen an und platziert die Ergebnisse wieder in die Sammlung (In der Tat könnten Sie dies eher iterativ als rekursiv tun, wenn Sie wollten).

Level 1 generates 0,1,2,...

Level 2 removes 0 and replaces it with 00,01,02,...
Level 2 removes 1 and replaces it with 10,11,12,...
etc

Answer 4

Eine FIFO-Warteschlange könnte ein besserer Ansatz sein als eine Rekursion, wie der Artikel von Wikipedia zur Breite-First-Suche vorgeschlagen wird: http://en.wikipedia.org/wiki/breadth_first_search.

Meine Lösung in C#:

string SolveRubiks()
{
    string[] singleMoves = {"0","1","2"};
    Queue<string> queue = new Queue<string>(singleMoves);
    while (true)
    {
        string moveSequence = queue.Dequeue();
        if (isSolution(moveSequence))
        {
            return moveSequence;
        }
        foreach (string singleMove in singleMoves)
        {
            queue.Enqueue(moveSequence + singleMove);
        }
    }
}

Wenn Sie einen Iterator benötigen, können Sie den If -Block mit einer Ertragsrendite tauschen und die Methodensignatur ändern. In Java müssen Sie eine Iterator -Schnittstelle implementieren (ähnlich wie die Klasse von Philip Uren).