我在尝试为一个通用的AI问题使用多种搜索算法，其中包括深度优先搜索。我已经将广度优先搜索、贪婪搜索和A*搜索从它们原本的递归形式转换成了迭代形式，但在尝试以cleanly的方式将深度优先搜索也转换成迭代形式时遇到了更多的困难（虽然这并不超出我的能力范围，但我并不确定最符合Python风格的做法，因此提出这个问题）。

即使是一些中等规模的问题，我也遇到了CPython的1000次递归调用限制的问题。继任状态是惰性生成的（_generate_states是一个生成器，而非列表），并且需要从初始状态开始的路径。

从使用调用堆栈转向使用显式堆栈的最符合Python风格的方法是什么？堆栈中应该存储多少信息？在回溯时（当没有状态返回非空列表时），从堆栈前端弹出无用信息的最佳方法是什么？

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):    # 这三个变量构成了“堆栈”。    closed_set = {initial}    stack = [initial]    gens = [_generate_states(initial, capacity)]    while stack:        cur = stack[-1]        gen = gens[-1]        try:            state = next(gen)        except StopIteration:            # 这个节点已完成            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

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