0

我在我的一个递归函数中遇到了内存错误。

def allPaths(self, adjMat, start, stop, flag=[0], walks=[]):
    walks = walks + [start]
    if start == stop:
        return [walks]
    loc = 0
    flag=flag*len(adjMat)
    output = []
    for value in adjMat[start]:
        if value > 0.0:
            if flag[loc] < 3:
                flag[loc]+=1
                paths = self.allPaths(adjMat, loc, stop, flag, walks)
                for k in paths:
                    output.append(k)
        loc += 1
    return output

一个示例输入很好，但我得到不同矩阵的内存错误。

>>>print test.allPaths([[0.0, 0.9, 0.0, 0.0, 0.0, 0.0, 0.1, 0.0],
          [0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0],
          [0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0],
          [0.0, 0.0, 0.0, 0.8, .15, .05, 0.0, 0.0],
          [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0],
          [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0],
          [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0],
          [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]],0,7)
[[0, 1, 2, 3, 3, 3, 4, 7], [0, 1, 2, 3, 3, 3, 5, 7], [0, 1, 2, 3, 3, 4, 7], [0, 1, 2, 3, 3, 5, 7], [0, 1, 2, 3, 4, 7], [0, 1, 2, 3, 5, 7], [0, 6, 7]]

>>>print test.allPaths([[0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
          [0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0],
          [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0],
          [0.8, 0.0, 0.0, 0.0, .05, .15, 0.0, 0.0],
          [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0],
          [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0],
          [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
          [0.9, 0.0, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0]],0,7)

错误似乎发生在“flag=flag*len(adjMat)”行。有什么建议么？

4

1 回答 1

1

每个递归调用都会将flag列表的大小增加 1 倍len(adjMat)。

对函数的第一次调用使用带有len(adjMat)元素的标志列表并将其传递给递归调用。列表将乘以len(adjMat)，得到len(adjMat) * len(adjMat)元素。通过一些递归调用，这很快就会失控，并且您可能会耗尽内存来存储这个过大的flag列表。

于 2013-07-10T20:59:09.113 回答