python中的深度优先搜索算法

Question

（此问题在此处更详细地跟进：）

假设我有一个函数接受一个输入（$x_i$），然后经过一个循环并产生一系列输出（$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_0$ 和一些 $y$，我们正在寻找一个序列 $x_0,x_1,\ldots,x_k$ , 这样 $x_k=y$, 和 $x_{j+1}=g(x_j,i_j)$ 对于 $j\in{0,\ldots, k-1}$.

要通过深度优先搜索来执行此操作，您将首先计算 $f(f(\ldots f(x) \ldots))$ 直到它产生目标结果或错误。然后返回一个步骤并从 $f$ 中产生第二个结果并重复（一个粗略的描述，但你明白了：基本上是深度优先搜索）。

在我看来，yield 关键字处理这个问题的效率很低。您还必须以一种允许您回溯的方式处理 $(x, f(x), f(f(x)),\ldots)$ 的堆栈（我认为这是正确的术语）你走进了死胡同。

这个一般性问题是我偶尔遇到的，我有点解决它临时，但我想知道是否有一个很好的通用结构来解决这个问题，它自然而有效地处理堆栈并探索 python 中可能的解决方案树。

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

Answer 1

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的子节点，然后递归遍历了子节点的子节点，然后处理了父节点的第二个子节点。

Answer 2

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

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 进行扩展）。

python中的深度优先搜索算法

Depth first search algorithm in python

python

depth-first-search

python-2.7

python-3.x