Path Finding:シングルソース、マルチパス、マルチターゲット、最大深度 – アプローチとアプリケーション

バックグラウンド

Definitions (as used here):

$ qquad $
単一ソース:パスの検索では、アルゴリズムは特定のノードから検索すると単一ソースです。

$ qquad $
マルチターゲット:パスの検索では、指定されたターゲットのそれぞれに対して少なくとも1つのパスを検索する場合、アルゴリズムはマルチターゲットです

$ qquad $
マルチパス:パスを見つけるために、少なくとも1つのパスが存在する場合はそれを返すならばマルチパスであるが、$
n $はその数見つけるには。

$ qquad $ 最大深度:パスの検索には、返されたパスの長さが$ d
$以下である場合、アルゴリズムは最大深度を持ちます指定された深さ。


記法:

$ k $ – 最大深度

$ t $ – ターゲットセット$ {t_1、 dots、t _ { lvert t rvert} } $

$ s $ – 元の頂点

$ n $ – per ターゲットを見つけるパスの数


Goal of the 質問: To determine the best (or a
sufficiently good) approach for finding up to $n$ paths for each of
target ($t_i$) within a max-depth of $k$ for a single-source $s$ in
a directed graph. In addition $n$ paths from each of the
targets to $s$ within a max-depth of $k$.

関数呼び出しの例は次のようになります。

find_path(G, s, t, n, k)

前述の目標を念頭に置いて、興味深い質問を検討することができます。

たとえば、マルチターゲットを検索するよりも、ターゲット(たとえば、シングルソース、マルチパス、シングルターゲット、最大深度)上で並列化する方が常に高速になるのでしょうか?私の直感は躊躇してはいです…しかし、場合によっては意味をなさないかもしれません。たとえば、貪欲な幅の最初の検索(ヒューリスティックで使用される値の重複がない場合)では、ターゲットに関係なくフロンティアは常に同じになります。そのような場合、なぜ複数のターゲットにわたって並列化するのか、どのターゲットを見つけたら$
t_i $よりも「より良い」パスを持つすべてのターゲットにアクセスし、すべてのターゲットが「悪い」ものになるまで続ける必要があります$
t_i $より。

多くのアルゴリズムは「最良パス」問題に焦点を当てています。この場合、$ n
$のベストパスを得るのが難しい場合があります。

スタックオーバーフローに関する質問星の変形</>
a> ユーザーは A *
の複数のバリアントを作成することで同様のことを試みます。ただし、マルチパスも除外されています。

$ n $ – ベストパスは考慮されず、$ n
$パスだけが考慮されます。同様に、depth-first-searchに対するこれらの調整をすべて簡単に行うことができます(マルチターゲットの方が、パラレルDFSはマルチタグセットより高速です)。

深さの最初の検索擬似コード

dfs(source, target, depth, num_p, timeout):
    paths_found = []
    dfs_recur(source, target, 1, depth, num_p, [], paths_found, now, timeout)

dfs_recur(current, goal, current_depth, max_depth, number_of_paths_to_find, current_path, paths_found, start_time, timeout):
   //timeout
    if now - start_time > timeout:
        return 

    current_path.push(current)
   //too deep
    if current_depth > max_depth:
        current_depth.pop()
        return 

   //found
    if current == goal:
        if len(paths_found) < number_of_paths_to_find:
            paths_found.push(current_path)
        current_path.pop()
        return 

   //hack to not miss goal in current depth
    elif goal in V[current]['successors']:
        current_path.push(goal)
        if len(paths_found) < number_of_paths_to_find:
            paths_found.append(current_path)
        current_path.pop()
        return 

   //normal dfs
    else:
        for n in V[current]['successors']:
             dfs_rec(n, goal, current_depth + 1, max_depth, number_of_paths_to_find, current_path, paths_found, start_time, timeout)

私は以下を調べました:

- Finding Top K Shortest Simple Paths with Improved Space Efficiency
- Eppstein k-best
- A* and some of its many variants e.g. A* Prune
- A K-Best Paths Algorithm for Highly Reliable Communication Networks
- Ant colony/Bee sensor based approaches
- bi-directional approaches
- greedy variants of DFS and BFS (with and without max depth cut offs)
- Yen's algorithm with Lawler's improvements

これらのアルゴリズムのどれも私の問題を単なる解決するものではないので、どのアルゴリズムを使うべきか(そして並列しているかどうか)を判断することは難しい。


特定のユースケース:

非常に大きく、スパースではあるが、非常に結びついたグラフがあるとします。$ lvert V rvert
approx50000 $、$ lvert E rvert approx2000000
$したがって、隣接行列(AM)では、希薄度は約0.0008であり、平均して各頂点は40の接続を有する。

次に、探索の前に、ソース頂点上の拡張された近傍を最大深度の範囲に計算する。言い換えれば、$ k $(
“スコープ”)のパス内で頂点に達することができる部分グラフを作成し、それらのエッジのみ(例えば、ソースの先祖の先祖と後継者の後継者のみ)ソースの)。

これは、直観に反して聞こえるかもしれません。もし私が最大長$ k
$の経路を探しているのであれば、なぜ直接経路を探索することができるのかという長所(長さ$ leq k
$のすべての推定経路を持つ)を事前計算するのはなぜですか?私はこれについてはわかりませんが、拡張された近所を計算するのはかなり時間がかかりますし、スコープを制限する時間の使用は、パスの実行時間を、グラフ。例えば3の範囲に限定すると、$
20,000 $頂点と$ 980,000
$エッジのサブグラフが生成される可能性があります。多くのアルゴリズムは二次的なものであるため(または$ lvertと v
rvert log lvert V rvert $)、その削減は価値があると思います。
(私はこれを実証するための具体的な証拠も境界もない)。

質問

最大経路長$ k $の$ t $から$ s $までの各ターゲットへの$ n $ベストパスを見つける最良のアプローチは何ですか?
(並列化が可能)

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です