cycle - 強連結成分を通る最適パスの検索

Question

強く接続された有向グラフがあり、すべてのノードに価格(プラスまたはマイナス)があります。ノード A からノード B への最良の (最高スコア) パスを見つけたいと思います。これに対するアルゴリズムはありますか、それともどうすればよいのでしょうか?

Answer 1

A* アルゴリズムを試しましたか?

これはかなり一般的な経路探索アルゴリズムです。アルゴリズム自体の実装はそれほど難しくありませんが、オンラインで入手できる実装はたくさんあります。

ダイクストラのアルゴリズムは、A* (ヒューリスティック関数 h(x) = 0) の特殊なケースです。

それよりも優れたパフォーマンスを発揮するアルゴリズムは他にもありますが、通常はグラフの前処理が必要です。問題がそれほど複雑ではなく、迅速な解決策を探している場合は、試してみてください。

編集：

負のエッジを含むグラフには、Bellman–Fordアルゴリズムがあります。ただし、負のサイクルを検出すると、パフォーマンスが犠牲になります (A* よりも悪い)。ただし、現在使用しているものよりも優れている可能性があります。

編集2：

ユーザー @templatetypedef は、Bellman-Ford アルゴリズムがここでは機能しない可能性があると述べています。

BF は、負の重みを持つエッジがあるグラフで機能します。ただし、アルゴリズムは負のサイクルを見つけると停止します。これは有用な動作だと思います。負の重みのサイクルを含むグラフで最短経路を最適化することは、ペンローズの階段を下りるようなものです。

「負の無限コスト」でパスに到達する可能性がある場合にどうなるかは、問題によって異なります。