C＃グラフトラバーサル - 任意の2つのノード間のトラッキングパス

Question

グラフに関する知識がなくても、2つのノード間の幅優先トラバースを追跡する優れたアプローチを探します。デプス - ファースト（パスが外れない場合はパスを捨てることができます）では、トラバーサル中にかなりの「オープン」可能性があります。

Answer 1

単純なアプローチは、ソースノードをルートとして、すべての接続をその子としてツリーを構築することです。あなたが持っているスペースの量に応じて、あなたは行くサイクルを排除する必要があります。これは、各ビットがグラフの別個のノードに対応するビットマップを使って行うことができます。ターゲットノードに到達すると、親リンクをルートに戻すことができます。これがあなたのパスです。最初に幅を広げているので、サイクルを排除しなくても最短パスであることが保証されます。

Answer 2

幅優先検索では、少なくとも2つのものを保存する必要があります。 1つは既に訪問されたノードのセットであり、もう1つは訪問先ノードから直接到達可能であるが訪問されていないノードのセットである。その後、状態を後者のセットから前者のセットに移動し、新しく到達可能な状態を後者のセットに追加します。ルートからいくつかのノードへのパスが必要な場合は、上記のセットに各ノード（ルートを除く）の親ノードも格納する必要があります。

通常、訪問されたノードのセットと訪問されていない子ノードのセット（すなわち、見られるノードのセット）の和集合はハッシュテーブルに格納されます。これは、以前に「新しい」状態が見られたかどうかを素早く判断し、そうであれば無視することができます。本当に大きな数の州がある場合、ビット配列（Joseph Bui（57509）のように）が必要になるかもしれませんが、あなたの州をその配列のインデックスとして（直接的または間接的に）使用できる場合を除いて、ハッシュ後者の場合は、別の（見た）ノードと同じインデックスにマップされているので、特定の状態を完全に無視するかもしれないので、これを慎重にしたいかもしれません。

参照されていないが見えているノードのセットをキューとして保存することができます（ビット配列はこのセットには使用できません）。アレイはほとんど空であり、次のセットビットを見つけることは比較的高価である）

Answer 3

この質問にも該当する解決策over hereを提出しました。

基本的には、訪問したノードのリスト（実際にスタック）を1つだけ保持しています。ソリューションを再帰または保存する直前にノードをリストに追加します。直後には必ずリストから削除してください。

Answer 4

.NET 3.5を使用している場合は、重複するノードが展開されないようにHashsetを使用することを検討してください。これは、グラフにサイクルがある場合に発生します。グラフの内容に関する知識がある場合は、展開するノードの数を減らすためにA* searchを実装することを検討してください。幸運と私はそれがあなたのために働くことを願っています。

まだトロイアのファンであれば、Peter NorvigとStuart RussellによるArtificial Intelligence：A Modern Approachのようなグラフやグラフ検索のトピックに関する多くの優れた書籍があります。 http://msdn.com/en-us/library/bb359438.aspxと*検索：http://en.wikipedia.org/wiki/A*_search_algorithm

私の応答内のリンクは、彼らはHashSetのあるバグを持っているように見えます