Leggiamo su Wikipedia > Ricerca approfondita approfondita per prima profondità che
The space complexity of IDDFS is O(bd), where b is the branching factor and d is the depth of shallowest goal.
Wikipedia fornisce anche qualche pseudocodice decente per IDDFS; L'ho pit pitificato:
def IDDFS(root, goal):
depth = 0
solution = None
while not solution:
solution = DLS(root, goal, depth)
depth = depth + 1
return solution
def DLS(node, goal, depth):
print("DLS: node=%d, goal=%d, depth=%d" % (node, goal, depth))
if depth >= 0:
if node == goal:
return node
for child in expand(node):
s = DLS(child, goal, depth-1)
if s:
return s
return None
Quindi la mia domanda è: in che modo la complessità dello spazio include il fattore di ramificazione? Questo presuppone che expand(node) occupa O(b) spazio? Cosa succede se expand utilizza un generatore che richiede solo uno spazio costante? In tal caso, la complessità dello spazio sarebbe ancora una funzione del fattore di ramificazione? Ci sono situazioni in cui è anche possibile che expand sia un generatore di spazio costante?