3

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

4

4 に答える 4

2

素朴なアプローチは、ソースノードをルートとして、そのすべての接続を子としてツリーを構築することです。スペースの量によっては、移動中にサイクルを削除する必要がある場合があります。これは、各ビットがグラフ内の個別のノードに対応するビットビットを使用して行うことができます。ターゲットノードに到達したら、親リンクをたどってルートに戻ることができます。これがパスです。幅優先であるため、サイクルを排除しなくても、最短経路であることが保証されます。

于 2008-09-11T20:16:10.373 に答える
1

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

通常、訪問されたノードのセットと訪問されていない子ノードのセット (つまり、見られたノードのセット) の結合は、ハッシュ テーブルに格納されます。これは、「新しい」状態が以前に見られたかどうかをすばやく判断し、その場合は無視できるようにするためです。状態の数が非常に多い場合は、実際にビット配列が必要になる場合があります (Joseph Bui ( 57509で言及されているように))、ただし、状態をその配列のインデックスとして (直接的または間接的に) 使用できない場合は、ハッシュ関数を使用して状態をインデックスにマップする必要があります。後者の場合、特定の状態が別の (そして見られる) ノードと同じインデックスにマップされているため、特定の状態を完全に無視する可能性があるため、これには注意する必要があります。また、パスを取得するには、ビット配列の使用をほとんど無効にする親情報を保存する必要があります。

未訪問だが確認済みのノードのセットは、キューとして保存できます。(配列はほとんど空であり、次のセット ビットを見つけるのは比較的コストがかかるため、ビット配列はこのセットには役に立ちません。)

于 2008-09-11T22:42:48.680 に答える
1

この質問にも当てはまる解決策をここに提出しました。

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

于 2008-09-12T15:17:31.783 に答える
0

.NET 3.5 を使用している場合は、Hashsetを使用して重複するノードが展開されないようにすることを検討してください。これは、グラフに循環がある場合に発生します。グラフの内容についてある程度の知識がある場合は、展開されるノードの数を減らすためにA* 検索を実装することを検討してください。頑張ってください。うまくいくことを願っています。

あなたがまだツリーウェアのファンなら、Peter Norvig と Stuart Russell による人工知能: A Modern Approach など、グラフとグラフ検索のトピックに関する優れた本がたくさんあります。

私の応答のリンクにはバグがあるようです。ハッシュセット: http://msdn.com/en-us/library/bb359438.aspxおよび A* 検索: http://en.wikipedia.org/wiki/A* _search_algorithm

于 2008-10-04T00:17:50.553 に答える