問題タブ [breadth-first-search]

グラフについて何も知らなくても、2 つのノード間の幅優先トラバーサルを追跡するための適切なアプローチを探しています。対 深さ優先 (パンアウトしない場合はパスを破棄できます) では、トラバーサル中にかなりの数の「開かれた」可能性がある場合があります。

BST（二分探索木）でルートからリーフへの最短パスを見つけるための最も簡単な方法は、できれば再帰を使用することです。Javaが好まれ、擬似コードは大丈夫です。

ありがとう！

私は BFS を実装しています。BFS が行うことは、順序付けされたツリーを調べて、パズルの最短の解決策を見つけることです。

これから行うことは、パズルの各ピースの現在の位置を保持するスナップショット オブジェクトを作成することです。このスナップショット オブジェクトをキューに追加し、それが解決策かどうかを確認します。ただし、これらのスナップショットはオンザフライで作成しています。では、スナップショット オブジェクトがキューに入れられたときにその名前を自動的に生成する方法はありますか?

または、私が行った宣言の数を追跡し、それをハードコーディングする必要があります...

スナップショット スナップショット2; スナップショット スナップショット3; スナップショット スナップショット4; 等..

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

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

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

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

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

今、私のループは

私のデータは次のようなものです

幅のみを列挙したい（a1、a2などではなく、a、bなど）。どうすればいいですか？

ツリー/グラフをトラバースするとき、幅優先と深さ優先の違いは何ですか? コーディングや疑似コードの例はどれも素晴らしいでしょう。

誰かが以下の種類の問題を解決するための幅優先探索を説明できますか

4 と 7 の間のすべてのパスを見つける必要があります

メンバ std::list を持つクラス "Class" があります。そのリスト/ツリーで項目、具体的には特定の名前の項目を検索したいと考えています。私のクラスの基本的な表現は次のとおりです。

Class::findItem で次のようなことができます。

しかし、私がやりたいのは、findItem() が検索元に「最も近い」アイテムを返すことです。たとえば、これが私のツリーの場合、各文字はリスト階層の 1 つのレベルを表し、各数字はアイテムの「値」を表します。findItem(3) が C(3) ではなく B(3) を返すようにします。

Prolog のデフォルトの深さ優先検索スキームよりも幅優先を使用する一般的な考え方は何ですか?

無限の枝を取りませんか？

Prolog で幅優先を使用する一般的な方法はありますか? 私はグーグルで検索してきましたが、初心者にとって有用な情報があまり見つかりませんでした.