algorithm - 指定されたコスト以下のコストで最速のパスを見つける

Question

これが私の問題の視覚化です。

私はその上でdjikstraを使おうと試みてきましたが、うまくいきませんでした。

Answer 1

私が見ているように、複雑なのは、ダイクストラのアルゴリズムが、保持する必要がある情報を破棄することです: A から E に移動しようとすると、

   B
 /   \
A     D - E
 \   /
   C

そして、ABD は ACD よりも短く、Dijkstra は ACD が可能だったことを忘れるでしょう (ACD を A から D への標準的なルートとして使用します)。しかし、ABD が ACD よりもコストが高く、ABDE がクォータを上回っているのに対し、ACDE がクォータを下回っている場合、現在削除されている ACD は正しいものでした。問題は、ダイクストラのアルゴリズムが、ある経路が少なくとも別の経路と同じ長さである場合、その経路が弱く支配されていると想定していることです。それを優先する理由はありません。そして、比較の 1 つの次元では、パスは弱く順序付けられています。2 つのパスが与えられた場合、一方が他方を弱く支配します。

しかし、ここでは比較の次元が 2 つあるため、順序付けは成立しません。一方の経路は短くなり、他方は安くなる可能性があります。支配されたパスしか破棄できないため、まだ予算を超えておらず、支配されていないすべてのパスを保持する必要があります。このアプローチを実装するために少し作業を行いました。実行可能に見えますが、指数関数的な複雑さを下回る最悪のケースの境界の引数を見つけることができません (正常なグラフではほとんどのパスが支配されているため、通常のパフォーマンスははるかに優れているはずです)。

また、Billiska が指摘するように、k 番目の最短ルート アルゴリズムを使用して、予算を下回るルートが見つかるまで結果を進めることもできます。それは時間 O(m+ K*n*log(m/n)); を使用します。しかし、K がバジェット (存在する場合) を下回るパスを含むことが保証されるような K の上限を誰かが見ない限り、K をパスの総数に設定する必要があり、ここでも指数関数的な複雑さが生じます (ただし、少なくとも長さとコストが合理的に相関している場合、K を段階的に増加させると、妥当な平均ランタイムが得られる可能性があります)。

編集：

私が提案した変更の実装を複雑に (おそらく致命的に) しているのは、ダイクストラのアルゴリズムがノードのアクセシビリティの順序付けに依存していることです。そのため、最短経路を持つ未調査のノードを使用すると、より良い方法は決して見つからないことがわかっています。 (他のすべてのルートは既に長いことがわかっているため)。その最短ルートも費用がかかる場合は、それを維持する必要はありません。ノードを探索した後でも、ノードへのより長いが安価なルートに基づいて、ノードからのパスを更新する準備ができている必要があります。これにより、最悪の場合、多項式時間に到達できなくなると思います。

Answer 2

Dijkstraでできると思いますが、各ステップで暫定距離の計算方法を変更する必要があります。距離だけでなく、コストも考慮してください。新しい距離は2次元の数値(dist, cost)である必要があります。最小の距離を選択する場合は、最小のdistANDを使用する距離を選択しますcost <= 6。それだけです。

これが正しいことを願っています。

Answer 3

基本的に、最初の最短パスを見つけて、それが機能するかどうかを確認し、次に 2 番目の最短パスを見つけて、機能するかどうかを確認する必要があります...

ダイクストラのアルゴリズムは、そのようなタスクで動作するようには設計されていません。そして、この問題の新しい定義に関する Google 検索だけで、kth-shortest-paths の検索に関する Stack Overflow の質問にたどり着きました。 私はまだそれを読んでいないので、私に聞かないでください。これが役立つことを願っています。