グラフ検索アルゴリズム

Question

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

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

有効なパスは、不特定の数の「上り」の後に不特定の数の「下降」を続けることも、その逆も可能です。ただし、方向を複数回変えることはできません。

たとえば、有効なパスは、「c "" "e"を下る "b" b "b" b "c" d down fである可能性があります。

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

Answer 1

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

ここでの祖先は、最短パスに沿って、現在のノードに到達するために通過したすべてのエッジです。祖先情報を保存する良い方法の 1 つは、数値のペアとして保存することです。U がアップ、D がダウンの場合、特定のエッジの祖先は次のとおりである可能性があります。 UUUDDDD, 、どちらがペアになりますか 3, 4. 。不変条件のため、3 番目の数値は必要ありません。

ダイクストラのアルゴリズムを使用しているため、複数の最短経路の検索はすでに行われています。

Answer 2

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

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

まずグラフ 1 で開始してグラフ 2 で終了する方法を解き、次にその逆を解いてから、最短の解を確認します。

Answer 3

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

同じ長さの最短パスをすべて検索するには、これまでに通過したエッジの数を構造体に含めます。最初の最短パスを見つけたら、パスの長さをメモし、開いているリストへのノードの追加を停止します。現在の長さのパスをすべて確認するまで、リストの残りのノードを調べ続けてから停止します。

Answer 4

あ* 特別に作成されたコスト (G スコア) とヒューリスティック (H スコア) 関数を使用して、これに対処できます。

コストについては、パス内の方向変更の数を追跡し、2 回目の変更で無限のコストを追加できます (つまり、それらのブランチの検索を中止します)。

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

おそらく、ヒューリスティックの作成に利用できるドメインに関する詳細情報があるでしょうか?(すなわち。グラフ内のノードの x、y 座標?)

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

Answer 5

標準のグラフ検索機能がある場合は、次のようにします。 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)

どこ myMin 2つを比較する必要があります [fst, nxt, C, AC, BD] タプルを作成し、距離が短いタプルを残すか、その両方を仮定します。 reduce 賢い機能です。

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