4

指定されたコストを超えない最速パスを見つけるのに問題があります。

指定された最大コストと 4 つのレコードがあるとしましょう。

// specified cost
    10 
// end point
    5
//(start point) (finish point) (time) (cost)
    2 5 50 5
    3 5 20 9
    1 2 30 5
    1 3 30 7

ポイント (1) から (5) に到達できるかどうかを判断する必要があります (取得したコスト以下のパスがない場合、または 1 から 5 の間に接続がない場合は不可能です)。そこに入る最速の方法です。

このようなデータの出力は次のようになります。

80 // fastest time
3 1 // number of points that (1 -> 2)  -> (2 -> 5)

1->2移動できるという記録がある場合は、覚えておいてください。

1 2 30 5

2<-1移動することはできません。

4

2 に答える 2

2

次のような動的計画法を使用します。

Route(node, length, target, accumulated)

if length <= 0 return -1
if node == target return accumulated

For each adjacent node:
  current length = accumulated + Route(adjacent node, length - connecting edge weight, target, accumulated + connecting edge weight)
  min length = min(current length, min length)

return min length
于 2012-11-15T18:47:03.823 に答える
0

Web 検索でhttp://www.cs.elte.hu/~alpar/publications/jour/AKCE_October_25.pdfが見つかり、これはかなり最新の研究問題であることを示唆しています。論文を読まずに、私のアプローチは動的計画法を使用することです。ここで、ノードごとに、合理的な K ごとにコスト <= K で最短パスの記録を保持します。使用可能な最短パスが変化する場合に K 値のみを保持する必要があります。 K が変化するとき。コストまたは時間のいずれかが確実に小さい整数である場合、これは実現可能かもしれません。そうでない場合は、管理できない数の部分解を計算して保持する必要がある問題例を作成できます。

于 2012-11-15T20:39:56.703 に答える