java - 系列生成・幅優先探索

Question

基本的に私がやっていることは、すべての可能な動きの幅優先探索でルービックキューブを解こうとすることです。これが立方体を解く最良の方法ではないことはわかっていますが、非常に短いシーケンスにのみ必要であり (したがって、検索の深さが 3 よりも深くなる可能性は低い)、次のもの以外を保存する必要はありません。現在のシーケンス。

増え続ける数字の文字列 (0,1,2,00,01,02...) を出力する方法を見つけようとしているので、それぞれを関数にプラグインして、その特定のシーケンスの移動はキューブを解決しますが、シーケンスを無期限に続行する方法を見つけるのに苦労しています。

これまでのところ、ネストされた for ループしか管理できませんでしたが、検索が深くなるたびに別のループが必要になります。この問題にどのようにアプローチできるか、誰にもわかりませんか?

漠然としていて申し訳ありませんが、私がやろうとしていることについてエッセイを書くことができましたが、それをシンプルにしようと思いました.

score 0 · Accepted Answer

関数が入力としてシーケンスを指定して後続の移動のリストを生成するような再帰的なソリューションが必要なようです。この場合、必要な回数だけ、関数を独自の出力で呼び出し続けることができます。

score 0 · Accepted Answer

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

[更新]関数に深さを指定するintを渡します。再帰するたびに、値をデクリメントします。ゼロかどうかを確認し、ゼロの場合は戻ります。

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

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

score 0 · Accepted Answer

幅優先検索に関するウィキペディアの記事 ( http://en.wikipedia.org/wiki/Breadth_first_search ) で示唆されているように、FIFO キューは再帰よりも優れたアプローチである可能性があります。

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

イテレータが必要な場合は、if ブロックを yield return と交換し、メソッドシグネチャを変更できます。Java では、イテレータインターフェイスを実装する必要があると思います (Philip Uren のクラスに似ています)。

score 0 · Accepted Answer

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

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

java - 系列生成・幅優先探索

4 に答える 4

Related

Reference