避免Python的堆栈

Question

我正在尝试一些搜索算法来解决一个通用的AI问题，其中之一是深度优先搜索。我已经将广度优先搜索、贪婪搜索和A*搜索从自然的递归形式转换为迭代形式，但在使用深度优先搜索时遇到了更多的麻烦(尽管这不超出我的能力范围，但我不确定最典型的方法是什么，因此出现了这个问题)。(虽然这不超出我的能力范围，但我不确定最典型的方法是cleanly，因此出现了这个问题)。

我遇到了CPython的1000个递归调用限制，即使是一些中等规模的问题。后续状态是延迟生成的(_generate_states是一个生成器，而不是一个列表)，并且需要从初始状态开始的路径。

从使用调用堆栈转移到显式堆栈的最典型的方式是什么？堆栈中应该存储多少信息？在回溯时(当没有状态返回非空列表时)，从堆栈的前面弹出死信息的最佳方法是什么？

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

请注意，路径是定位目标时的堆栈，因为堆栈是为到达当前节点而访问的节点的记录。

Answer 2

我假设您知道如何使用堆栈迭代地实现DFS (它基本上与BFS相同，只是后进先出而不是FIFO)，所以我将只发布一些一般技巧。

• 当你迭代地实现DFS时，你应该为堆栈使用collections.deque，它为快速追加和弹出元素进行了优化。
• 你绝对应该为closed_set使用集合而不是列表。(如果您要查找最短路径，则可以使用映射{ state : depth}。)
• 为了跟踪路径，您可以创建一个包装类，封装当前状态和对前一个状态的引用(基本上是一个链接的状态列表)，或者使用前置状态的映射。

但是，不确定在这种情况下如何使用生成器，所以堆栈最多可以容纳x个分支因子元素……或者您可以将生成器放在堆栈上，而不是实际的元素？只是一个想法..。

Answer 3

下面是我如何创建迭代深度优先搜索的方法。它使用candidate_states作为下一步应该探索的状态堆栈。您可以使用parents字典重建从任何被访问节点到初始节点的路径。

def reconstruct_path(state, parents):
    path = []
    while state != None:
        path.append(state)
        state = parents[state]
    path.reverse()
    return path

def dfs(initial, goal):
    visited_states = set()
    candidate_states = [initial]
    parents = {initial: None}
    while len(candidate_states) > 0:
        cur_state = candidate_states.pop()
        if cur_state in visited_states: continue
        if cur_state == goal:
            return reconstruct_path(cur_state, parents)
        for state in _generate_states(cur_state):
            parents[state] = cur_state
            candidate_states.append(state)
    return None