私は麻薬の売人で、それぞれ一定額の価値がある配達ルートの地図を持っています。しかし、私はエリア全体をカバーすることはできません、私は私の少しの芝と戦う必要があります。しかし、私は自分が戦うことができる芝のビットを選択することができます。
このグラフの頂点は街角であり、すべての街路は同じ長さで1方向です。いくつかの通りは他より多くの価値があります。通過しなければならない街角の数が最小になるように、歩く最大のビートを見つけたいと思います。すべてのパスは、42nd Street Subwayで始まり、RooseveltIslandTramで終わります。
ネットをざっと見てみましたが、どこかで見た覚えのないもののようです。
最大重量/流量/コストパスの計算は、動的計画法を使用したDAGで簡単に行えます。
しかし、可能な限り短いパスを見つける必要がある場合はどうでしょうか。さて、ある球場の値の近くで、長さkのすべての最大パスをkに対して繰り返すことができます。しかし、長さkの最大パスを取得するにはどうすればよいですか？
これへのポインタを見つけるためのアイデアはありますか？
編集1
わかりました。フロイド・ウォーシャルは特定の長さで最大パスを実行できると感じています。これで十分かもしれません。可能なすべての長さで実行できます。しかし...もっと良いアイデアはありますか？
編集2
DAGのみを参照するように修正されました。
編集3
Floyd-Warshallは、特定の長さの最大パスを実行できます。k：つまり、DAG最大パスとFloyd Warshallを使用して、任意の頂点と最終ストップの間の最短（エッジ数）のパスを取得します。したがって、最大パスアルゴリズムの任意の頂点で、（現在の最大パスの）現在のエッジ数の合計+（Floyd-Warshallが決定した）その頂点と最終停止は、特定の長さkを超えます。
編集4
答えがあると思います。
このグラフの長さkの最大パスを見つけるために、グラフ内の任意のノードについて、そのノードとエンドポイントの間のエッジの最小数がわかっていると仮定します。
したがって、このように最大パスアルゴリズムを実行し、特定のブランチで可能なエッジの最小数が除外範囲を下回っていることを確認します。
このコードでは、グラフは開始頂点によってインデックス付けされたエッジのディクショナリであり、各エッジはタプル（destination_edge、weight）です。このアルゴリズムは重みを最大化しますが、返されるパスがパラメーターkより長くないことを保証します。
def maxpathoflength(k,start_vertex,graph_out_edges,memory,frame_size):
# first of all we leverage dynamic programming to save any results we have checked before
if start_vertex in memory:
return memory[start_vertex]
# otherwise we calculate it
# first we set the current maximum gold at this vertex
maxgold = 0
# corresponding to the following maximum path
maxpath = [start_vertex]
#then we check to see if we have broken our k-length path constraint
if k < 0:
# we failed, yet somehow we should never make it to here anyway
return { 'gold' : maxgold, 'path' : maxpath }
# if on the other hand k were equal to zero and this was the end point
# we would have succeeded
# we save this size since we can use it to calculate the lower bound
# on the number of edges required to get to the finish from this vertex
graph_size = len(graph_out_edges)
# we get the edges adjacent to start_vertex
# they are all out_edges, the graph has the DAG property
# the graph also has this property : there are no out edges from the last vertex :
if start_vertex > graph_size - 1:
return { 'gold' : maxgold, 'path' : maxpath }
out_edges = graph_out_edges[start_vertex]
print 'Out edges: ' + str(out_edges)
for edge in out_edges:
# each edge is stored as a 2-tuple (to_vertex,edge_weight)
arrival_vertex = edge[0]
edge_weight = edge[1]
# the following property holds for this graph, hence we can know the lower bound on edges of any path from this vertex
min_edges_from_arrival_vertex_to_end = ceil((1.0*graph_size - int(arrival_vertex))/frame_size)
# and so we can determine if we want should search it or not
if min_edges_from_arrival_vertex_to_end > k-1:
print 'Skipping this edge'
continue
# or if this branch is ok
# we search down this branch and take 1 off the edges
# remaining
# we search it and find the result of searching it is...
result = maxpathoflength(k-1,arrival_vertex,graph_out_edges,memory,frame_size)
gold = edge_weight + result.get('gold')
path = result.get('path')
# if that result is greater than our current best
if gold > maxgold:
# we make that result our new personal best
maxgold = gold
maxpath = [start_vertex] + path
# our return value is what we found the maximum to be from this vertex
returnvalue = { 'gold' : maxgold, 'path' : maxpath }
# we save this so we never ever have to do this again
memory[start_vertex] = returnvalue
# and send it back to up to the calling function
return returnvalue