python - 如何更有效地递归搜索最长节点？

Question

我试图在有向无环图中找到最长的路径。目前，我的代码似乎是 O(n³) 的运行时间复杂度。

图是输入{0: [1,2], 1: [2,3], 3: [4,5]

#Input: dictionary: graph, int: start, list: path
#Output: List: the longest path in the graph (Recurrance)
# This is a modification of a depth first search
def find_longest_path(graph, start, path=[]):
    path = path + [start]
    paths = path
    for node in graph[start]:
        if node not in path:
            newpaths = find_longest_path(graph, node, path)
            #Only take the new path if its length is greater than the current path
            if(len(newpaths) > len(paths)):
                paths = newpaths

    return paths

它返回一个节点列表，例如[0,1,3,5]

如何使它比 O(n³) 更有效？递归是解决这个问题的正确方法还是我应该使用不同的循环？

Answer 1

您可以在 O(n+e) 中解决此问题(即与节点数 + 边数呈线性关系)。

想法是您首先创建一个拓扑排序(我是 Tarjan's algorithm 的粉丝)和反向边集。如果您可以分解问题以利用现有解决方案，这总是有帮助的。

然后，您向后遍历拓扑排序，将其子节点的距离 + 1 推到每个父节点(在有多条路径的情况下保持最大值)。跟踪到目前为止看到的距离最大的节点。

当你用距离完成对所有节点的注释后，你可以从距离最大的节点开始，这将是你最长的路径根，然后沿着你的图走下去，选择比当前节点(因为它们位于关键路径上)。

一般来说，在尝试寻找最佳复杂度算法时，不要害怕一个接一个地运行多个阶段。五个 O(n) 算法顺序运行仍然是 O(n) 并且仍然优于 O(n²) 从复杂性的角度来看(尽管实际运行时间可能更糟，具体取决于恒定的成本/因素和 n 的大小)。

预计到达时间:我刚刚注意到您有一个起始节点。这使得它只是一个进行深度优先搜索并保留迄今为止看到的最长解决方案的简单情况，无论如何它只是 O(n+e)。递归很好，或者您可以保留一个已访问节点的列表/堆栈(每次回溯时查找下一个子节点时都必须小心)。

当您从深度优先搜索回溯时，您需要存储从该节点到叶子的最长路径，这样您就不会重新处理任何子树。这也将用作 visited 标志(即除了执行 node not in path 测试之外，还有一个 node not in subpath_cache 测试之前递归)。您可以存储长度，而不是存储子路径，然后在完成后根据上面讨论的顺序值(关键路径)重建路径。

ETA2:这是一个解决方案。

def find_longest_path_rec(graph, parent, cache):
    maxlen = 0
    for node in graph[parent]:
        if node in cache:
            pass
        elif node not in graph:
            cache[node] = 1
        else:
            cache[node] = find_longest_path_rec(graph, node, cache)

        maxlen = max(maxlen, cache[node])

    return maxlen + 1

def find_longest_path(graph, start):
    cache = {}
    maxlen = find_longest_path_rec(graph, start, cache)
    path = [start]
    for i in range(maxlen-1, 0, -1):
        for node in graph[path[-1]]:
            if cache[node] == i:
                path.append(node)
                break
        else:
            assert(0)
    return path

请注意，我已经删除了 node not in path 测试，因为我假设您实际上提供了所声明的 DAG。如果你想要检查你真的应该提出错误而不是忽略它。另请注意，我已将断言添加到 for 的 else 子句中，以记录我们必须始终在路径中找到有效的下一个(顺序)节点。

ETA3:最后的 for 循环有点困惑。我们正在做的是考虑在关键路径中所有节点距离必须是连续的。考虑节点 0 的距离为 4，节点 1 的距离为 3，节点 2 的距离为 1。如果我们的路径从 [0, 2, ...] 开始，我们就有了矛盾，因为节点 0 不是进一步的 1来自一片叶子而不是两片叶子。