避免Python堆栈

我正在尝试一些广义AI问题的搜索算法，其中之一是深度优先搜索。我将广度优先搜索，贪婪搜索和A *搜索从它们的自然递归形式转换为迭代搜索，但是在深度优先搜索中执行它有点麻烦cleanly（虽然它不超出我的能力，但我我不确定最好的方法，因此问题）。避免Python堆栈

即使是一些中型问题，我也遇到了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 []

来源

2012-10-02 efritz

我不知道有一个最Python的方式，但我很好奇，如果任何人有比这更好的答案。而应该存储多少信息的答案是“不超过您对算法工作的要求”。 – Omnifarious

只是一个小改进 - 如果您使用[deque]（http://docs.python.org/library/collections.html#collections.deque）而不是列表，则可能会获得_slightly_更快的堆栈。 –

@Omnifarious当我优化存储大量冗余路径（因为每个当前层节点都有相同的父路径）时，BF也是如此。我很好奇看到处理这个问题的最好方法。 – efritz

下面是保持发电机解决各地保持期望懒惰属性：

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

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

来源

2012-10-02 16:20:43 nneonneo

您使用了未定义的'path'。你的意思是使用'stack'代替吗？ – efritz

是的，我的意思是'堆'，谢谢。 – nneonneo

这是我将如何创建一个迭代深度优先搜索。它使用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

来源

2012-10-02 15:49:27 Kevin

我在编写BFS解决方案时使用了相同的字典技术。 – efritz

我假设你知道如何反复使用栈来实现DFS（其基本相同BFS，只是后进先出法，而不是FIFO），所以我会后只是一些普通的窍门。

当反复实施DFS，你应该使用collections.deque堆栈，这是为快速追加和弹出要素优化。
您应该使用closed_set而不是列表的集合。（或者如果你想查找最短路径，则需要map {state：depth}）。
为了跟踪路径，你可以创建一个包装类，封装你当前的状态和引用前一个（基本上是链接状态列表），或者使用先前状态的映射。

不知道如何使用发电机在这种情况下，虽然如此，你的筹码将容纳深x分支因素元素...也许你可以把发电机在栈上，而不是实际的元素？只是一个想法...

来源

2012-10-02 15:50:55

只有FIFO才需要'deque'。对于LIFO来说，普通的旧名单是有效的; 'append（）'或'pop（）'不需要移动元素。 – kindall

避免Python堆栈

回答

相关问题