重み付けされていないダイグラフ上の 2 つのノード間の最短パスを見つけて返そうとするプログラムで幅優先検索を使用しています。
私のプログラムはウィキペディアのページの疑似コードのように動作します
アルゴリズムは、次のように、グラフをトラバースするときにキュー データ構造を使用して中間結果を格納します。それ以外の場合は、まだ検出されていない後続ノード (直接の子ノード) をキューに入れます。キューが空の場合、グラフ上のすべてのノードが調べられました。検索を終了して「見つかりません」を返します。キューが空でない場合は、手順 2 から繰り返します。
そのため、実行されたステップ数を追跡する方法を考えていましたが、Java の制限に問題があります (Java の仕組みについてあまり詳しくありません)。私は当初、ステップとノードを格納する、作成したデータ型で構成されるキューを作成できると考えていました。グラフをトラバースすると、ステップが追跡されます。目標に到達した場合は、単純に手順を戻します。
Javaでこれを機能させる方法がわからないので、その考えを取り除く必要があり、その不安定な Queue = new LinkedList のキューの実装を使用することに移りました。したがって、基本的には通常の整数キューだと思います。作成したデータ型を使用できませんでした。
したがって、より基本的なアプローチを見つける必要があるため、単純なカウンターを使用しようとしましたが、トラバーサル アルゴリズムが最短のパスに到達する前に多くのパスを検索するため、これは機能しません。歩数を追跡する 2 つ目のキューを追加し、いくつかのカウンターを追加しました。ノードが最初のキューに追加されるたびに、カウンターに追加します。つまり、新しいノードを調べていることがわかっているので、遠く離れていません。これらすべてを検査したら、ステップ カウンターを増やすことができます。ノードが最初のキューに追加されるたびに、ステップ値をステップ キューに追加します。ステップ キューはノード キューと同じように管理されるため、ゴール ノードが見つかったときに、対応するステップがキューから取り出されます。
これは機能しませんが、私はそれで多くの問題を抱えていましたが、実際には理由がわかりません.
パニックと欲求不満でほとんどのコードを削除しましたが、誰かが私を必要とする場合は、コードを再作成してここに投稿します.
私のアイデアに近いものはありましたか?どうすればそれらを機能させることができますか? これを行うための標準的で簡単な方法もあると確信していますが、私はそれを理解するのに十分賢くありません。