2

我是一名毒贩，有一张运送路线图，每条路线都价值一定。但我不能覆盖整个区域，我只需要争夺我的一小块地盘。但是，我可以选择我可以争吵的地盘。

该图的顶点是街道拐角，所有街道的长度和 1 way相同。有些街道比其他街道更有价值。我想找到最大的步行节拍，这样我必须经过的街角数量最少。所有路径都从第 42 街地铁开始，到罗斯福岛电车结束。

我快速浏览了一下网，但似乎不像我记得在任何地方看到过的东西。

使用动态规划在 DAG 上计算最大重量/流量/成本路径很容易。

但是，如果我们还需要找到尽可能短的最大路径怎么办？好吧，我们可以迭代所有长度为 k 的最大路径，以使 k 接近某个近似值。但是，如何获得长度为 k 的最大路径？

任何想法在哪里可以找到指向这个的指针？

编辑 1

好的..我有一种感觉 Floyd-Warshall 可以在特定长度下完成最大路径。这可能已经足够好了，我可以在所有可能的长度上运行它。但是……有更好的主意吗？

编辑 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
4

0 回答 0