8

指定された初期状態で 8 パズル ゲームの DFS と BFS を実装する Java のコードを探しています。

1 2 3
8 0 4
7 6 5

と目標状態

2 8 1
0 4 3
7 6 5

初期状態から目標状態までのソリューション パスを出力する必要があります (まだ完了していません)

これは私が持っているコードです。これまでのところ、DFS のみを実装できました。私のプログラムがこれまでに行ったことは、目標状態を見つけると SUCCESS を出力することです。ただし、ここまで到達することはありません。

誰かが私が間違っている場所を教えてもらえますか?

4

3 に答える 3

7

わかりました、あなたのプログラムは予想よりも長くかかっています。まず、無限ループに陥っているのか、単に遅いのかを調べます。そのために、メインループに以下を追加して、プログラムに進行状況を出力させましょう。

    int statesVisited = 0;
    while (OPEN.empty() == false && STATE == false) {
        statesVisited++;
        System.out.println(statesVisited);

次に、プログラムが 1 秒あたり数千の州を訪問したことがわかります。私たちのプロセッサは毎秒数十億の命令を実行するため、これは状態の処理に約百万の CPU 命令が必要であることを意味します。そんなに高くないはずですよね？では、何が原因でしょうか？

一般的に言えば、プロファイラーを使用して、コードのどの部分にこの時間が費やされているかを測定しますが、プログラムが非常に短いため、最初に推測してみることができます。私が最初に推測するのは、私たちが訪れたすべての州を印刷するには、かなりの費用がかかる可能性があるということです。これを確認するために、1000 番目ごとの状態だけを出力してみましょう。

    while (OPEN.empty() == false && STATE == false) {
        statesVisited++;
        if (statesVisited % 1000 == 0) {
            System.out.println(statesVisited);
        }

場所を変えると、最初の 5000 州が 2 秒未満で訪問されていることがわかります。そのため、印刷は確かに重要でした。また、興味深いことにも気付きました。最初の 5000 州は 1 秒以内に訪問されますが、何らかの理由で、プログラムはどんどん遅くなっていくようです。20000 州を訪問した時点で、1000 州を訪問するのに約 1 秒かかり、悪化し続けています。状態の処理がますます高価になるべきではないため、これは予期しないことです。したがって、ループ内の一部の操作がますます高価になっていることがわかります。コードを見直して、それがどの操作であるかを特定しましょう。

コレクションのサイズに関係なく、プッシュとポップには一定の時間がかかります。ただし、Stack.search と LinkedList.contains も使用します。これらの操作は両方とも、スタックまたはリスト全体を反復処理する必要があることが文書化されています。それでは、これらのコレクションのサイズを出力しましょう。

        if (statesVisited % 1000 == 0) {
            System.out.println(statesVisited);
            System.out.println(OPEN.size());
            System.out.println(CLOSED.size());
            System.out.println();
        }

しばらく待つと、次のようになります。

40000
25947
39999

したがって、OPEN には 25000 の要素が含まれ、CLOSED には約 40000 の要素が含まれます。これが、状態の処理がますます遅くなる理由を説明しています。java.util.HashSetしたがって、 orなどのより効率的な contains 操作を使用するデータ構造を選択する必要がありますjava.util.LinkedHashSet(これはハッシュ セットとリンク リストのハイブリッドであり、追加された順序で要素を取得できます)。これを行うと、次のようになります。

public static LinkedHashSet<String> OPEN = new LinkedHashSet<String>();
public static HashSet<String> CLOSED = new HashSet<String>();
public static boolean STATE = false;

public static void main(String args[]) {

    int statesVisited = 0;

    String start = "123804765";
    String goal = "281043765";
    String X = "";
    String temp = "";

    OPEN.add(start);

    while (OPEN.isEmpty() == false && STATE == false) {

        X = OPEN.iterator().next();
        OPEN.remove(X);

        int pos = X.indexOf('0'); // get position of ZERO or EMPTY SPACE
        if (X.equals(goal)) {
            System.out.println("SUCCESS");
            STATE = true;
        } else {
            // generate children
            CLOSED.add(X);

            temp = up(X, pos);
            if (!(temp.equals("-1")))
                OPEN.add(temp);
            temp = left(X, pos);
            if (!(temp.equals("-1")))
                OPEN.add(temp);
            temp = down(X, pos);
            if (!(temp.equals("-1")))
                OPEN.add(temp);
            temp = right(X, pos);
            if (!(temp.equals("-1")))
                OPEN.add(temp);
        }
    }

}

/*
 * MOVEMENT UP
 */
public static String up(String s, int p) {
    String str = s;
    if (!(p < 3)) {
        char a = str.charAt(p - 3);
        String newS = str.substring(0, p) + a + str.substring(p + 1);
        str = newS.substring(0, (p - 3)) + '0' + newS.substring(p - 2);
    }
    // Eliminates child of X if its on OPEN or CLOSED
    if (!OPEN.contains(str) && CLOSED.contains(str) == false)
        return str;
    else
        return "-1";
}

/*
 * MOVEMENT DOWN
 */
public static String down(String s, int p) {
    String str = s;
    if (!(p > 5)) {
        char a = str.charAt(p + 3);
        String newS = str.substring(0, p) + a + str.substring(p + 1);
        str = newS.substring(0, (p + 3)) + '0' + newS.substring(p + 4);
    }

    // Eliminates child of X if its on OPEN or CLOSED
    if (!OPEN.contains(str) && CLOSED.contains(str) == false)
        return str;
    else
        return "-1";
}

/*
 * MOVEMENT LEFT
 */
public static String left(String s, int p) {
    String str = s;
    if (p != 0 && p != 3 && p != 7) {
        char a = str.charAt(p - 1);
        String newS = str.substring(0, p) + a + str.substring(p + 1);
        str = newS.substring(0, (p - 1)) + '0' + newS.substring(p);
    }
    // Eliminates child of X if its on OPEN or CLOSED
    if (!OPEN.contains(str) && CLOSED.contains(str) == false)
        return str;
    else
        return "-1";
}

/*
 * MOVEMENT RIGHT
 */
public static String right(String s, int p) {
    String str = s;
    if (p != 2 && p != 5 && p != 8) {
        char a = str.charAt(p + 1);
        String newS = str.substring(0, p) + a + str.substring(p + 1);
        str = newS.substring(0, (p + 1)) + '0' + newS.substring(p + 2);
    }
    // Eliminates child of X if its on OPEN or CLOSED
    if (!OPEN.contains(str) && CLOSED.contains(str) == false)
        return str;
    else
        return "-1";
}

public static void print(String s) {
    System.out.println(s.substring(0, 3));
    System.out.println(s.substring(3, 6));
    System.out.println(s.substring(6, 9));
    System.out.println();
}

ほぼ瞬時に「成功」​​を出力します。

于 2014-08-10T17:06:03.580 に答える
2

BFS、DFS、A*、IDA* などを使用して、 Hipster ライブラリを使用して 8 パズルを簡単に解くことをお勧めします。ここに完全な例があります(検索戦略の設計に役立つ場合があります)。

興味がある場合、問題を解決するための基本的な手順は、最初に状態空間探索問題をトラバースできるようにする関数を定義し、次に状態空間問題を探索する 1 つのアルゴリズムを選択することです。検索問題を作成するには、次のProblemBuilderクラスを使用できます。

SearchProblem p = 
  ProblemBuilder.create()
    .initialState(Arrays.asList(5,4,0,7,2,6,8,1,3))
    .defineProblemWithExplicitActions()
    .useActionFunction(new ActionFunction<Action, List<Integer>>() {
    @Override
    public Iterable<Action> actionsFor(List<Integer> state) {
        // Here we compute the valid movements for the state
        return validMovementsFor(state);
    }
    }).useTransitionFunction(new ActionStateTransitionFunction<Action, List<Integer>>() {
    @Override
    public List<Integer> apply(Action action, List<Integer> state) {
        // Here we compute the state that results from doing an action A to the current state
        return applyActionToState(action, state);
    }
    }).useCostFunction(new CostFunction<Action, List<Integer>, Double>() {
    @Override
    public Double evaluate(Transition<Action, List<Integer>> transition) {
        // Every movement has the same cost, 1
        return 1d;
    }
    }).build();

問題を定義したら、それを解決するアルゴリズムを選択できます。

System.out.println(Hipster.createDijkstra(p).search(Arrays.asList(0,1,2,3,4,5,6,7,8)));

このプレゼンテーションhttps://speakerdeck.com/pablormier/hipster-an-open-source-java-library-for-heuristic-searchで、8 パズル問題と Hipster でそれを解決する方法の詳細を読むことができます。

于 2014-08-11T11:04:30.610 に答える
1

既に追加されているオープン スタックの組み合わせをプッシュしないでください。(さらに、ArrayDeque の方がよいでしょう。Stack は古いクラスです。javadoc http://docs.oracle.com/javase/7/docs/api/java/util/Stack.htmlを参照してください。

Deque インターフェイスとその実装によって、より完全で一貫性のある LIFO スタック操作のセットが提供されます。これは、このクラスより優先して使用する必要があります。例えば：

Deque スタック = new ArrayDeque(); )

同じ状態を何度も探索しないようにするには、Set をクローズド リストとして使用し、オープン リストに追加しようとしている状態がクローズド リストに追加されていないことを確認する必要があります。

また、操作を実行するために文字列よりも byte[] 配列 (メモリを節約するための int[] ではなく) を使用する方が快適な場合があります。

要約すると、次のようにコードを構成できます。

public class Taquin {
    private byte[][] state = new byte[3][3];

    public Taquin(String s) { ... }
    public List<Taquin> successors() { ... }
    public boolean isSolvable(Taquin goal) { ... }
    //Necessary to use the Set !////////////
    public int hashCode() { ... }
    public boolean equals(Object o) { ... }
    public String toString() { ...state }
    ////////////////////////////////////////

    public void solve(Taquin goal) { 
        if (isSolvable(goal)) {
            Deque<Taquin> open   = new ArrayDeque<>();
            Set<Taquin>   closed = new HashSet<>();
            closed.add(this);
            open.add(this);

            Taquin current = this;
            //if isSolvable is correct you should never encounter open.isEmpty() but for safety, test it
            while (!current.equals(goal) && !open.isEmpty()) {
                current = open.pop();
                System.out.println(current);
                for (Taquin succ : current.successors())
                    //we only add to the open list the elements which were never "seen"
                    if (closed.add(succ))
                        open.add(succ);
            }
            System.out.println("Success");
        } else
            System.out.println("No solution");
    }
}

これには、グラフ内のあらゆる種類の検索に対して一般的であるという利点があります。別のパズルを解きたい場合は、実装していないメソッド (実際には Node インターフェースの一部) を変更するだけです。たとえば、8 パズルでよく使用される A スターなどのアルゴリズムを変更したい場合は、解決方法を変更するだけです。このコード サンプルがお役に立てば幸いです。

于 2014-08-10T16:03:47.873 に答える