python - 功能需要很长时间

Question

我目前正在尝试从节点 1 获取唯一路径的数量 .. 加权有向无环图的最大长度 N，我已经计算出获取最大长度，但我一直坚持获取路径的数量给定的最大长度......

数据是这样输入的:

91 120  # Number of nodes, number of edges

1 2 34

1 3 15

2 4 10

....作为节点1->节点2权重为34，

I input my data using a diction so my dict looks like:
_distance = {}
_distance = {1: [(2, 34), (3, 15)], 2: [(4, 10)], 3: [(4, 17)], 4: [(5, 36), (6, 22)], 5: [(7, 8)],...ect

我已经弄清楚如何使用这个实现最长的路径长度:

首先我制作一个顶点列表

class Vertice:
    def __init__(self,name,weight=0,visted=False):
        self._n = name
        self._w = weight
        self._visited = visted
        self.pathTo

for i in range(numberOfNodes): # List of vertices (0-n-1)
  _V = Vertice(i) 
  _nodes.append(_V)

接下来我遍历我的字典，将每个节点设置为它可能的最大权重

        for vert, neighbors in _distance.iteritems():
        _vert = _nodes[vert-1] # Current vertice array starts at 0, so n-1


        for x,y in neighbors:  # neighbores,y = weight of neighbors
            _v = _nodes[x-1]   # Node #1 will be will be array[0]

            if _v._visited == True:
                if _v._w > _vert._w+y:
                    _v._w = _v._w
                else:
                    _v._w = y + _vert._w

            else:

                _v._w = y + _vert._w
                _v._visited = True

完成后，最后一个节点的权重将达到最大值，因此我可以调用

max = _nodes[-1]._w

获得最大重量。这似乎执行得很快，即使在更大的数据集上执行时也能轻松找到最大长度路径，然后我取最大值并将其运行到此函数中:

#  Start from first node in dictionary, distances is our dict{}
#  Target is the last node in the list of nodes, or the total number of nodes.
numLongestPaths(currentLocation=1,target=_numNodes,distances=_distance,maxlength=max)

def numLongestPaths(currentLocation,maxlength, target, sum=0, distances={}):


    _count = 0

    if currentLocation == target:
        if sum == maxlength:
                _count += 1

    else:
        for vert, weight in distances[currentLocation]:
            newSum = sum + weight
            currentLocation = vert
            _count += numLongestPaths(currentLocation,maxlength,target,newSum,distances)

    return _count

一旦我们到达结束节点，我就简单地检查一下我们的当前总和是否为最大值，如果是，则将我们的计数加一，如果不是通过。

这适用于输入，例如 8 个节点，最长路径为 20，找到 3 条路径，以及输入，例如 100 个节点，最长长度为 149，并且只有 1 个该长度的唯一路径，但是当我尝试这样做时一个包含 91 个节点的数据集，例如最长路径 1338，唯一路径数为 32，该函数耗时非常长，可以运行但速度很慢。

有人可以给我一些提示，告诉我我的函数有什么问题导致它需要这么长时间才能从 1..N 找到路径长度 X 的数量吗？我假设它的运行时间呈指数增长，但我不确定如何修复它

感谢您的帮助!

编辑:好吧，我想太多了，以错误的方式解决了这个问题，我重组了我的方法，我的代码现在如下:

# BEGIN SEARCH.
    for vert, neighbors in _distance.iteritems():
        _vert = _nodes[vert-1] # Current vertice array starts at 0, so n-1


        for x,y in neighbors:  # neighbores

            _v = _nodes[x-1]   # Node #1 will be will be array[0]

            if _v._visited == True:
                if _v._w > _vert._w+y:
                    _v._w = _v._w
                elif _v._w == _vert._w+y:
                        _v.pathsTo += _vert.pathsTo
                else:
                    _v.pathsTo = _vert.pathsTo
                    _v._w = y + _vert._w

            else:

                _v._w = y + _vert._w
                _v.pathsTo = max(_vert.pathsTo, _v.pathsTo + 1)
                _v._visited = True

我在我的 Vertice 类中添加了一个 pathsTo 变量，它将保存最大长度的唯一路径的数量

Answer 1

您的 numLongestPaths 很慢，因为您递归地尝试每条可能的路径，而且其中的路径可能呈指数级增长。找到一种方法来避免为任何节点多次计算 numLongestPaths。

此外，您原来的 _w 计算被破坏了，因为当它计算一个节点的 _w 值时，它没有做任何事情来确保其他 _w它所依赖的值本身已经被计算出来。您需要避免使用未初始化的值；一个topological sort可能很有用，尽管听起来顶点标签可能已经按拓扑排序顺序分配。