我正在为一个通用的 AI 问题尝试多种搜索算法,其中之一是深度优先搜索。我已经将广度优先搜索、贪婪搜索和 A* 搜索从它们的自然递归形式转换为迭代形式,但使用深度优先搜索干净
时遇到了一些麻烦(尽管这不超出我的能力范围,我不确定这样做是最pythonic的方式,因此问题)。
我遇到了 CPython 的 1000 次递归调用限制,即使是一些中等规模的问题。后继状态是延迟生成的(_generate_states
是生成器,而不是列表),并且需要从初始状态开始的路径。
从使用调用堆栈转移到显式堆栈的最 pythonic 方法是什么?堆栈中应该存储多少信息?回溯时(当没有状态返回非空列表时),从栈顶弹出死信息的最佳方法是什么?
def dfs(initial, closed_set, goal, capacity):
if initial == goal:
return [initial]
for state in _generate_states(initial, capacity):
if state not in closed_set:
result = dfs(state, [initial] + closed_set, goal, capacity)
if result:
return [state] + result
return []
最佳答案
这里有一个解决方案,可以让生成器保持在周围以保持所需的惰性属性:
def dfs(initial, goal, capacity):
# These three variables form the "stack".
closed_set = {initial}
stack = [initial]
gens = [_generate_states(initial, capacity)]
while stack:
cur = stack[-1]
gen = gens[-1]
try:
state = next(gen)
except StopIteration:
# This node is done
closed_set.discard(cur)
gens.pop()
stack.pop()
continue
if state == goal:
return stack
if state not in closed_set:
closed_set.add(state)
stack.append(state)
gens.append(_generate_states(state, capacity))
return None
注意路径是目标所在的栈,因为栈是为了到达当前节点所访问的节点的记录。
关于python - 避免 Python 的栈,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12693278/