java - Java での幅優先検索

Question

割り当てのためにJavaで幅優先検索を実行する必要があります。タイルの 5x5 グリッドがあります (合計 24 個 - 1 個のタイルが「空白」のままです)。検索のポイントは、「空白」を上下左右に移動してタイルを再配置し、最終的にタイルを正しい順序に再配置することです。

この検索を行うために、Arraylist 'queue' を作成しました。この配列リストのインデックス 0 の状態を取得し、従うことができる正当な動きをそれぞれ見つけて、それらをそれぞれ配列リストの最後に追加するメソッドがあります。

理論的には、これは「目標状態」が最終的に見つかるまで続きます。問題は、検索を実行すると、「キュー」配列リストがどんどん大きくなり続けることです。今日、私はそれを何時間も実行したままにしましたが、それでも解決策は見つかりませんでした.

これは、おそらく私がこのソリューションを間違った方法で実行したことを示唆しており、Java で幅優先検索を行うためのより良い方法があります。目標状態とあまり変わらない開始状態を使用すると、正しいパスを見つけるのに時間がかかりすぎないため、ソリューションが (最終的には) 機能することはわかっています。ただし、使用する開始状態が与えられましたが、残念ながら、ゴール状態にはほど遠いです!!!

ヒントやヒントをいただければ幸いです。

score 7 · Accepted Answer

まず第一に、ArrayList の代わりに実際の Queue オブジェクトを使用することは間違いありません。Queue インターフェースの Java API ページは次のとおりです。何を選択すればよいかわからない場合は、単純な LinkedList で十分です。ArrayList は、最後から高速に削除するだけなので、パフォーマンスが大幅に低下します。配列内の他の場所から削除すると、すべてを 1 つ下にシフトする必要があります(SLOW ! )。最後にエンキューし、最初にデキューするため、SLOW !

今、あなたはアイテムを使い終わった後にアイテムをデキューする（それらを削除する）ことを明示的に言及していませんでした。

特に幅優先検索を使用する必要がありますか? 正しく計算すると、25 あります。(階乗) の組み合わせ、つまり 15511210043330985984000000 の組み合わせです。これは、理論的には、幅優先検索を行っている場合、アルゴリズムが終了する可能性が低いことを意味します。深さ優先検索は許可されていませんか? 幅優先検索を使用する必要がある場合、それを高速化する唯一の方法は、最適解につながる可能性がない状態を取り除くことです。あなたがそれについてどうするかわかりません。

score 2 · Accepted Answer

重複チェックなしの幅優先検索は、間違いなくあなたが見ているような結果をもたらすでしょう。実際、実装したアルゴリズムが決して終了しないことを証明するのはかなり簡単です。お気軽にお待ちください... :-)

必要なのは、Set事前に調べた位置を格納するための補助データ構造 (できれば ) です。したがって、コードの一部は次のようになります。

public Queue<Position> queue = new LinkedList<Position>();
public Set<Position> done = new HashSet<Position>();

public Position[] findPath(Position start, Position goal) {
    if (done.contains(start)) return null;

    done.add(start);
    // add subsequent states to `queue`
    ...
}

他の回答で述べたように、この場合、深さ優先検索がはるかに優れたソリューションです。位置が到達可能であると仮定するとgoal、最も不自然な位置を除いて、指数関数的に優れた検索時間が得られるはずです。

score 1 · Accepted Answer

一見すると、状態が重複し、グラフ内でサイクルが発生する可能性があるように見えます。2 つの州が同じかどうか、また以前にどちらかを訪れたことがあるかどうかを確認するには、何らかの方法を調べる必要があるかもしれません。

編集: アルゴリズムの制限はさておき、他のタイルを乱すことなくブロック X を位置 Y から位置 Z に移動する式がある可能性があります。これがあれば、必要なすべての変換を計算するだけです。私は今、その問題について考えているだけです。

score 0 · Accepted Answer

おそらく、目標指向の深さ優先探索です。9つのエッジタイルを解くことから始め、パズルを4x4グリッドに減らします。次に、その7つのエッジタイルを解決し、3x3グリッドに縮小します。これは、元のアルゴリズムで簡単に選択できるはずです。

score 0 · Accepted Answer

私が今それをしている方法は次の通りです：

2つの配列リスト; キューに入れて訪問
開始状態は、Visitedarraylistに自動的に追加されます
開始から開始までのすべての可能な合法的な移動が取得され、それぞれが訪問済み配列リストに格納されているものと比較されます。
「訪問済み」状態を作成しない合法的な移動は、キューに追加されます。
arraylistのインデックス0に保持されている状態が取得され、プロセスが繰り返されます。

以前の回答から、おそらくアレイリストを別のコレクションに変更する必要があることがわかりました。しかし、私は状態が重複していないことを確認しています。

score 0 · Accepted Answer

私は「総当たり検索」を行いました - 問題は、5x5 グリッドでは非常に多くの組み合わせがあり、永遠にかかることです。私は仕事に行っている間、それを実行したままにしました... 8時間後、それはまだ続いていました。

私は自分のコードが機能することを知っているので (最終的には、私が言ったように)、喜んで提出します。解決策を見つけるのにかかる時間が心配で、arraylist を使用してキューを作成する以外に、より良いアプローチがあるかどうか疑問に思いました。

score 0 · Accepted Answer

この演習の目的は、深さ優先検索がこの特定のパズルに対するより優れたアプローチであることを認識してもらうことだと思います。

score 0 · Accepted Answer

次は、訪問したリストを作成する場合、状態を自動的にソートする Set (おそらくTreeSet ) を使用して、新しい状態が以前に訪問されたかどうかを検索する方がはるかに高速になることです。

必要なことは、状態クラスにComparableインターフェースを実装させることだけです。（うまくいけば、あなたはすでにこのようなことを期待していて、それをクラスにしました）。まだわからない場合は、このインターフェイスの compareTo メソッドを使用して、オブジェクトの並べ替え順序を定義します。これはもちろん、訪問した Set によって使用されます。そこから、タイルを除いて文字列比較のように機能するように compareTo メソッドを設定できます。

わかりやすくするために、各タイルに文字が割り当てられ、各州のタイルがリストされている場合、次のようになります。

State 1: ABCDEFGHIJKLMNOP
State 2: BCADEFGHIJKLMNOP

当然、状態 1 が最初になります。そのため、その compareTo メカニズムをタイルごとに推定するだけで (タイルには ID やインデックスなどがあるはずですよね?)、並べ替えられた訪問済みリストが作成されます。次に、 Visited.contains(state) を呼び出すと、プログラムは状態が訪問されたかどうかを非常に迅速に計算できます。

score 0 · Accepted Answer

おそらくあなたの課題の範囲内ではありませんが、この種のパズルを解くためのアルゴリズムがあります。基本的に、最後の2行を除くすべての行で機能する2つの動きと、最後の2行で機能する2つの移動があります。このアプローチを使用すると、はるかに高速なソリューションが得られます。

残念ながら、これは課題であるため、ブルートフォース検索を行うことは間違いありません。

score 0 · Accepted Answer

私は実際に両方のコードを書かなければなりません。だから私は深さ優先検索に移ろうとしています。それを行う前に、解決策を見つけるのに永遠に1日かかるコードを作成したことで、コースから外れて笑われないようにしたかっただけです!!!!!!!!

score 0 · Accepted Answer

これをチェックするかどうかは言いませんでしたが、剪定サイクルを行っていないようです。

まず、空白の正方形をある方向に移動することを表す代わりに、移動したタイル番号を指定したとします。(一意であることが保証されています。) 次に、正当な移動が「3」であるとします。つまり、タイル #3 を空きスペースに移動します。その結果、新しい基板レイアウトが生まれました。そこからの合法的な移動は、タイル 3 を再び移動することであり、これで最初の場所に戻ります。

スライダーパズルは、簡単に大きなサイクルを持つことができます。1-2-3-空の 2x2 グリッドがある場合、有効な移動シーケンスは 1-2-3-1-2-3-1-2-3-1-2-3 です。最初に戻ります。

検索で重複するボードをチェックして削除しない場合でも、幅優先検索は終了します (バグがなく、ボードを解決できないパリティエラー (?) がない場合) - N 移動という正しい解決策が存在します。 K 回の一連の動きをすべて処理するのに有限の時間がかかるため、最終的には N に到達し、解が得られます。ただし、各移動の長さの時間は指数関数的に増加します (各ボードから最大 4 つの移動まで)。あなたはおそらくメモリにスラッシングしています。

残念ながら、重複したボードの状態をチェックする力ずくのアプローチは、到着したすべてのボードを保存することです。これは、現在の方法ほど速くはないかもしれませんが、メモリをすぐに使い果たしてしまいます。実際、単なる 5x5 ボードには十分かもしれません。

java - Java での幅優先検索

11 に答える 11

Related

Reference