3

有向非巡回グラフがあり、リソース制約のある最短経路を見つける必要があります。私の制約は、選択されたパスは、消費されるセット リソースの最小数を持たなければならないということです。

現在、Yen の K 最短パス アルゴリズムを使用して K 最短パスを計算し、制約を満たすパスのみを受け入れています。ここで問題となるのは、K を推測することです。誤って選択された場合、実行可能なパスが見つからない可能性があります。

このトピックに関するかなり多くの文献を見つけました。これは良い概要を提供すると思います。しかし、私はそれを理解し、実装できる簡潔なアルゴリズムを見つけるのに苦労しています (私は Python を使用していますが、明確なアルゴリズムのアイデアは素晴らしいでしょう)。

この問題は NP-Complete であることを理解しています。そのため、適切な近似アルゴリズムと正確なアプローチに興味があります。

誰にも良い推奨事項はありますか？

4

2 に答える 2

2

できることは、グラフ(V,E)を(V',E')どこに変換するかです

  • P(v)元のノードの価格ですv
  • Rリソースの最大使用量です。
  • V' = {(v,k) | v in V and k in [0..R]}
  • E'((v,k),(w,l)) = E(v,w) and k+P(w)=l

次に、からダイクストラ検索を行います(v0,P(v0))。へのパスを見つけることができた場合v1、制限が与えられた場合、そこへの最短距離は、(v1,k)頂点間で最短になります。

明らかに、実際の展開されたグラフを作成しません。変更されたダイクストラで何が起こっているかというと、これまでの距離に加えて、リソースの使用もこれまでのところ維持するということです。制限を超えていない場合にのみ、パスをたどります。dist[v]そして、aを保持する代わりに、リソースdist[v,k]を正確に使用して、これまでの v への最短パスを表し続けます。k

リソースバウンドが非常に大きい場合、これは潜在的に大きくなる可能性があります。したがって、NP完全性。ただし、リソース バウンドが小さい場合、または最も近い 10、100、または 1000 に丸めることを気にしない場合、高速な多項式時間で実行されます。特に、 useable に達したら停止する最適化を実装する場合(v1,k)。

于 2012-01-19T16:10:43.080 に答える