7

いくつかの異常な特性を持つグラフ アルゴリズムを探しています。

グラフの各エッジは、「上」エッジまたは「下」エッジのいずれかです。

有効なパスは、無数の「上」の後に無数の「下」が続くか、またはその逆になります。ただし、一度しか方向を変えることはできません。

たとえば、有効なパスは A "up" B "up" C "down" E "down" F で、無効なパスは A "up" B "down" C "up" D です。

2 つのノード間の最短の有効なパスを見つけるための適切なアルゴリズムは何ですか? 等しい長さの最短経路をすべて見つけるのはどうですか?

4

5 に答える 5

11

ヒューリスティックがないと仮定すると、ダイクストラのアルゴリズムのバリエーションで十分です。新しいエッジを検討するたびに、その「祖先」に関する情報を保存してください。次に、不変条件 (一方向のみの変更) をチェックし、違反している場合はバックトラックします。

ここでの祖先は、最短パスに沿って現在のノードに到達するためにトラバースされたすべてのエッジです。祖先情報を格納する良い方法の 1 つは、数値のペアとして保存することです。U が上で D が下の場合、特定のエッジの祖先は でUUUDDDDあり、ペアになり3, 4ます。不変式のため、3 番目の数値は必要ありません。

ダイクストラのアルゴリズムを使用したため、複数の最短経路を見つけることは既に処理されています。

于 2008-09-09T21:14:27.100 に答える
4

おそらく、グラフを通常の有向グラフに変換してから、既存のアルゴリズムを使用できます。

1 つの方法は、グラフを 2 つのグラフに分割することです。1 つはすべてのアップ エッジを持ち、もう 1 つはすべてのダウン エッジを持ち、グラフ 1 のすべてのノードとグラフ 2 の対応するノードの間に有向エッジがあります。

最初にグラフ 1 から開始し、グラフ 2 で終了し、その後その逆を解いてから、最短の解を確認します。

于 2008-09-09T21:15:55.630 に答える
2

標準のBFSがここで動作するはずだと思う人もいるでしょう。開いているリストにノードを追加するときはいつでも、ノードが使用している方向 (上または下) と、まだ方向が切り替わったかどうかを示すブール値フラグを保持する構造体にノードをラップできます。これらを使用して、そのノードからのどの出力エッジが有効かを判断できます。

同じ長さのすべての最短パスを見つけるには、これまでに横断したエッジの数を構造体に含めます。最初の最短パスを見つけたら、パスの長さを書き留めて、開いているリストにノードを追加するのをやめます。現在の長さのすべてのパスをチェックするまで、リストの残りのノードを調べ続けてから停止します。

于 2008-09-09T21:16:26.720 に答える
2

特別に細工されたコスト (G スコア) とヒューリスティック (H スコア) 機能を備えたA*で処理できます。

コストについては、パスの方向変更の数を追跡し、2 回目の変更に無限のコストを追加できます (つまり、それらの分岐の検索をカットします)。

ヒューリスティックは、特にヒューリスティックを許容可能 (目標までの最小距離を決して過大評価しない) かつ単調に保ちたい場合は、もう少し検討が必要です。(A* が最適解を見つけることを保証する唯一の方法。)

ヒューリスティックを作成するために利用できるドメインに関する情報が他にもあるのではないでしょうか? (つまり、グラフ内のノードの x、y 座標?)

もちろん、解決したいグラフのサイズに応じて、最初に幅優先検索やダイクストラのアルゴリズムなどのより単純なアルゴリズムを試すことができます。基本的にすべての検索アルゴリズムで実行でき、すべての検索アルゴリズムに対してコスト関数 (または同様のもの) が必要になります。とりあえず。

于 2008-09-09T21:22:44.753 に答える
1

ライブラリなどに標準的なグラフ検索機能がある場合はGraph.shortest(from, to)、C#/疑似コードでループして最小化できます。

[ (fst.shortest(A, C) + nxt.shortest(C, B)) 
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(min)

最小パスを覚えておく必要があり、標準関数がデータを返す場合は、発音することもできます

[ [fst, nxt, C, fst.shortest(A, C), nxt.shortest(C,B)]
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(myMin)

wheremyMinは 2 つのタプルを比較し、距離が短い方を残すか、両方を残す必要があり、スマート関数である[fst, nxt, C, AC, BD]と想定します。reduce

グラフが大きく、メモリをまったく使用しない場合 (動的に生成された場合に発生する可能性があります)、これにはいくらかのメモリ オーバーヘッドがありますが、実際には速度のオーバーヘッドはありません。

于 2009-06-12T09:32:59.187 に答える