python - 避免 Python 的栈

Question

我正在为一个通用的 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 []

Answer 1

这里有一个解决方案，可以让生成器保持在周围以保持所需的惰性属性:

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

注意路径是目标所在的栈，因为栈是为了到达当前节点所访问的节点的记录。