algorithm - 最短経路を制限する方法-最大コストのダイクストラアルゴリズム？

Question

最短経路問題に最大コスト値を割り当てるにはどうすればよいのでしょうか。私の問題では、ノードに関連するリスクがあります。リスクを最小限に抑えたいのですが、ノード数が限られているソリューションを見つけてほしいと思います（たとえば、ソリューションがn個のノードを超えないようにしながら、ノードAからノードBへの最小リスクを見つけます）ありがとうございます多くの。

Answer 1

Dijkstra は Best First Search です。つまり、最適なノードまでの距離が決して良くならないことを確認する必要があります。非負のエッジを持つ最小ダイクストラで機能します。通常、 Ford-Bellmanを使用できます。n 個以下の頂点を使用する場合は、動的プログラミング dp[vertex][used_vertex_count] の複雑さ O(|V| * n) の状態とメモリ、および O(|E| * n) 時間をお勧めします。または、グラフの隣接行列を作成し、主対角線にゼロを指定し、エッジがない場合は無限大にして、n 指数を計算します。a_{ij} は、n 個以下の頂点を使用する i から j への最小パスになります。

Answer 2

ここでは、ヒューリスティックを含むアルゴリズムが最も適していると思います。ヒューリスティックは、各ステップで目標にどれだけ「近い」か、どのノードが目標に近づくかという概念です。nそれがなければ、最悪の場合 (ノードだけでは目標に到達できない場合) に指数アルゴリズムを実行する必要があると思いますn。解決できません）。

非ヒューリスティック アルゴリズムを使用する 1 つの例は次のとおりです。ダイクストラを通常の方法で実行し、リスクが最小のノードを選択します。途中で、訪問したノードの数を追跡します。ノードの数がそれを超える場合はn、現在のルートを放棄して前のノードに戻り、次にリスクが低いノードを使用します。n当然のことながら、目標が次のレベルにある場合はそれが選択されているため、1 レベル上のレベルだけをバックトラックすることはできません。したがって、レベルに戻り、続行しますn-2。すべてのパスをチェックせずに存在しないことを判断する実際の方法がないため、これも指数関数的になります。

また、私が何かを見逃している可能性もあります。

Answer 3

Prim のアルゴリズムは、指定されたグラフ内のすべての最小スパニング ツリーを検出するため、使用したいと考えています。次に、必要な制約で mst を選択するのは簡単です。