python - python中的深度优先搜索算法

Question

(此问题在此处更详细地跟进:python-search-algorithm-from-implied-graphs)

假设我有一个函数接受一个输入($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

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

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