シーケンス生成/幅の最初の検索

Question

本質的に私がしていることは、すべての可能な動きを最初に検索することでルービックキューブを解決しようとすることです。これはキューブを解決するための最良の方法ではないことを知っていますが、非常に短いシーケンスには必要なだけです（検索の深さは3より深くなる可能性は低い）。現在のシーケンス。

数の増加する文字列（0,1,2,00,01,02 ...）を印刷する方法を見つけようとしています。動きはキューブを解決しますが、シーケンスを無期限に継続する方法を見つけるのに苦労しています。

これまでのところ、私が管理していたのはループ用にネストされていますが、検索がより深くなるたびに別のループが必要です。誰かが私がこの問題にどのようにアプローチできるか考えていますか？

申し訳ありませんが、あいまいだったら、自分がやろうとしていることについてのエッセイを書くことができましたが、シンプルにしようとすると思いました。

Answer 1

私はJavaライブラリにあるものにあまり精通していないので、これがすでにそこにあるものを実装している場合は謝罪しますが、私がこれをゼロから書いていた場合、おそらくこのようなことをするでしょう。

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());
    }
}

そうすれば、任意のシンボルのアルファベットから任意の深さにシーケンスを列挙できます。また、これは、深さを繰り返し、各深さに対して可能なシーケンスの完全なセットを生成する限り、あなたが望むものをします。また、ジアンが言うように、それは再帰で行うこともできます。 Pythonでは、このためにジェネレーター関数を使用しますが、Javaで同様のものには精通していません。

Answer 2

再帰的なソリューションが必要なように聞こえます。これにより、インプットとしてシーケンスが与えられた後継の動きのリストが生成されるようになります。

Answer 3

再帰機能はこれを行いませんか？再帰の深さを制限し、徐々に深くすることができます。

更新]関数を渡し、深さを指定します。再発するたびに、値を減少させます - ゼロの場合は確認し、その場合は返します。

値については、文字列またはストリングビルダーのコレクションを再帰関数に渡します。各レベルは、前のレベルから値を読み取り（および削除します）、可能なすべての次の動きを追加し、結果をコレクションに戻します（実際、必要に応じて再帰的にではなく、これを繰り返し行うことができます).

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

FIFOキューは、幅広い検索に関するWikipediaの記事で示唆されているように、再帰よりも優れたアプローチかもしれません。 http://en.wikipedia.org/wiki/breadth_first_search.

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);
        }
    }
}

Iteratorが必要な場合は、IFブロックを降伏リターンで交換してメソッドシグネチャを変更できます。Javaでは、Iteratorインターフェイスを実装する必要があると思います（Philip Urenのクラスと同様）。