0

再帰関数の 1 つでメモリ エラーが発生しました。

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

1 つの入力例は問題ありませんが、別の行列でメモリ エラーが発生します。

>>>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リストのサイズが の係数で増加しlen(adjMat)ます。

関数の最初の呼び出しでは、要素を持つフラグ リストを使用し、len(adjMat)それを再帰呼び出しに渡します。そこで、リストに が乗算され、要素len(adjMat)が得られます。len(adjMat) * len(adjMat)再帰呼び出しを数回行うと、これはすぐに手に負えなくなり、この非常に大きなflagリストを格納するためのメモリが不足する可能性があります。

于 2013-07-10T20:59:09.113 に答える