python中的深度优先搜索算法

Question

（这个问题在这里有更详细的讨论：python-search-algorithm-from-implied-graphs）

假设我有一个函数，它接受一个输入（$x iui$），然后经过一个循环并生成一系列输出（$x{I，j}$）。然后，每个输出可以再次作为同一函数的输入，从而产生更多的输出（$x{i，j，k}$）。我试图通过这个函数找到一组步骤，来达到一个特定的结束状态。在

这是一个普遍的问题，我的问题是python中什么样的代码结构可以处理这个问题。在

以下是一些元代码作为示例（尽管在实践中可能更复杂）：

def f(x):
  for i in range(n):
    if some_condition:
      yield g(x,i) 
  yield false

然后对于一些$x\u 0$和一些$y$，我们要寻找一个序列$x\u 0，x_1，\ldots，x_k$，这样$x_k=y$，而$x{j+1}=g（x_j，i_j）$，对于{0，\ldots，k-1}$。在

要使用深度优先搜索来实现这一点，首先要计算$f（f（\ldots f（x）\ldots））$，直到它生成目标结果或为false。然后后退一步，从$f$得到第二个结果，然后重复（这是一个粗略的描述，但是你得到的想法是：基本上是深度优先搜索）。在

在我看来，yield关键字处理这个问题的效率很低。您还必须处理$（x，f（x），f（f（x）），\ldots）$的堆栈（我认为这是正确的术语），以便您在遇到死胡同时能够后退。在

这个一般性的问题是我经常遇到的，我在某种程度上解决了它即席，但我想知道是否有一个很好的通用结构来解决这个问题，它自然而有效地处理堆栈并探索python中可能的解决方案树。在

我希望这个问题足够清楚。我欢迎任何想法、评论、澄清或回答。在

Answer 1

我认为对当前路径和递归使用显式堆栈比较简单：

def search(start_state, neighbors, goal):
    path = [start_state]

    class PathFound(RuntimeError):
        pass

    def rsearch(x):
        if goal(x):
            raise PathFound
        for y in neighbors(x):
            path.append(y)
            rsearch(y)
            path.pop()

    try:
        rsearch(start_state)
    except PathFound:
        return path

    return None # No path exists

Python具有较低的递归限制，但对于深度优先搜索，这通常不是问题（而且它可以通过sys.setrecursionlimit进行扩展）。在

Answer 2

class Tree:
def __init__(self, value, children = None):
    self.value = value
    self.children = []
    if children:
        self.children = list(children)

def get_children(self):
    return list(self.children)

def get_value(self):
    return self.value

def has_children(self):
    if self.children:
        return True

node9 = Tree(9)
node5 = Tree(5, [node9])
node6 = Tree(6)
node3 = Tree(3, [node5, node6])
node7 = Tree(7)
node8 = Tree(8)
node4 = Tree(4, [node7, node8])
node2 = Tree(2)
node1 = Tree(1, [node2, node4, node3])

def iterate_child(child):
    global level
    print ' ' * level * 2, child.get_value()
    if child.has_children():
        level += 1
        for s_child in child.get_children():
            iterate_child(s_child)
        level -= 1

level = 1
print node1.get_value()
for child in node1.get_children():
    iterate_child(child)

如上图所示，我迭代了node1的子节点，并递归地迭代了子节点的子节点，然后处理了父节点的第二个子节点。在