0

BFS はO(b^d)メモリを必要としますが、IDDFS はO(bd)メモリのみで実行されることが知られています。しかし、これら 2 つの実装をプロファイリングすると、まったく同じ量の RAM を使用していることが判明しました。

Treeテストを実行するために、分岐係数または 10のクラスを使用しています。

class Tree(object):
    def __init__(self, value):
        self.key = value
        self.children = [ ]

    def insert(self, value):
        if len(self.children) == 0:
            self.children = [ Tree(value) for x in range(10) ]
        else:
            for ch in self.children:
                ch.insert(value)

私の実装iddfs：

def iddfs(t):
    for i in range(0,8):
        printGivenLevel(t, i)

def printGivenLevel(t, level):
    if not t:
        return
    if level == 1:
        pass
    elif level > 1:
        for ch in t.children:
            printGivenLevel(ch, level - 1)

BFSは

def bfs(t):
    currLevel = [t]
    nextLevel = []
    while currLevel:
        for node in currLevel:
            if node:
                nextLevel.extend([ x for x in node.children ])
        currLevel = nextLevel
        nextLevel = []

コードは実際には何もしていません。ツリー全体をループしているだけです。コードのプロファイリングにhttps://github.com/fabianp/memory_profilerを使用しています。

4

1 に答える 1

4

IDDFS のメモリ上の利点は、ノードが到達するとすぐに生成され、すぐに破棄される暗黙的なツリーにのみ適用されます。ツリーが完全にメモリ内に表現されている場合、ツリー自体がすでにO(b^d)メモリを使用しており、IDDFS または BFS に必要なメモリは比較的少ないものです。

于 2015-07-05T00:00:55.257 に答える