1

各ノードと各エッジに値が付加された標準グラフがあるとします。最短時間でグラフ上の 1 つのノードから別のノードに移動したいと考えています。このグラフをトラバースするのにこれまでにかかった時間は T と呼ばれます。エッジの値が V の場合、そのエッジをトラバースすると V が費やされた時間に追加されます (T += V)。ノードの値が N の場合、そのノードをトラバースすると、費やした時間が N (T += (N - T % N) % N) で割り切れるまで待機する必要があります。

これは、通りや信号機のようなものと考えることができます。通りを運転すると、反対側に到達するまでに一定の時間がかかります。信号を通過すると、青になるまでの待ち時間が長くなります。

たとえば、次のグラフがあるとします。

S--6--[1]--2--[7]
       |       |
       3       2
       |       |
      [9]--3--[6]--1--E

一見すると、エッジが短く、遅延が短いトップ パスの方が高速に見えます。ただし、下のルートの方が速いことがわかります。最初に底を計算しましょう：

Start: 0 + 6 -> 6
       6 % 1 == 0 # We can pass
       6 + 3 -> 9
       9 % 9 == 0 # We can pass
       9 + 3 -> 12
       12 % 6 == 0 # We can pass
       12 + 1 -> 13
End:   13

そしてトップ：

Start: 0 + 6 -> 6
       6 % 1 == 0 # We can pass
       6 + 2 -> 8
       8 % 7 != 0 # Have to wait
       8 + 6 -> 14
       14 % 7 == 0 # We can pass
       14 + 2 -> 16
       16 % 6 != 0 # Have to wait
       16 + 2 -> 18
       18 % 6 == 0 # We can pass
       18 + 1 -> 19
End:   19

ご覧のとおり、下の方が短くなっています。このような小さなサイズでは計算が簡単ですが、都市のサイズでは、ある種のトラバーサル アルゴリズムを使用する必要があります。ブルートフォース以外に何らかの解決策があるかどうか知っている人はいますか?

4

1 に答える 1

2

これは最短経路探索問題として知られており、ダイクストラのアルゴリズムによって多項式時間で解くことができます。パスの長さが計算されるとき、目的の頂点での待機に費やされた時間も追加する必要があります (目的の頂点を除く)。したがって、これはやはり最短経路探索問題ですが、重み関数は単純なエッジの重みの合計とは少し異なります。

于 2014-10-13T21:01:13.830 に答える