Python中的深度优先搜索算法 [英] Depth first search algorithm in python

问题描述

（此问题在此处得到详细介绍： python-search-algorithm- from-implied-graphs ）

(This question is followed up in more detail here: python-search-algorithm-from-implied-graphs)

假设我有一个函数接受输入（$ x_i $），然后经过一个循环并产生一系列输出（$ x_ {i，j} $）。然后，每个输出可以再次成为同一函数的输入，从而产生更多的输出（$ x_ {i，j，k} $）。我正在尝试通过此功能找到特定的最终状态的一组步骤。

Suppose I have a function that takes an input ($x_i$) and then goes through a loop and yields a series of outputs ($x_{i, j}$). Then each output can be an input again to the same function yielding further outputs ($x_{i, j, k}$). And I'm trying to find a set of steps via this function to a particular end state.

这是一个普遍的问题，我的问题是python中如何处理此问题的良好代码结构。

This is a general problem, and my question is what is a good code structure within python to handle this.

这里有一些元代码作为示例（尽管在实践中可能会更复杂）：

Here's some meta code as an example (though it might be more complicated in practice):

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} $。

Then for some $x_0$ and some $y$, we're looking for a sequence $x_0,x_1,\ldots,x_k$, such that $x_k=y$, and $x_{j+1}=g(x_j,i_j)$ for $j\in{0,\ldots,k-1}$.

要进行深度优先搜索，您首先要计算$ f（f（\ldots f（x）\ldots））$，直到得出目标结果或错误。然后备份一个步骤，并从$ f $产生第二个结果并重复（粗略的描述，但您会想到：基本上是深度优先搜索）。

To do this with a depth first search where you would calculate $f(f(\ldots f(x) \ldots))$ first until it yields the targeted result or a false. Then back up one step and yield the second result from $f$ and repeat (a rough description, but you get the idea: a depth first search, basically).

在我看来，yield关键字将无法有效地解决这一问题。您还必须以允许您回溯的方式处理$（x，f（x），f（f（x）），\ldots）$的堆栈（我认为这是正确的术语）当你死胡同时。

It seems to me that the yield keyword is going to be inefficient to handle this. You've also got to handle the stack (I think this is the right terminology) of $(x, f(x), f(f(x)),\ldots)$ in a way that allows you to back track when you hit a dead end.

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

This general problem is something I come across now and then, and I kind of solve it ad hoc, but I wondered if there was a good general structure for solving this, which naturally and efficiently handles the stack and exploring the tree of possible solutions in python.

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

I hope this question is sufficiently clear. I welcome any thoughts, comments, clarifications or answers.

推荐答案

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

I think that just using an explicit stack for the current path and recursion is simpler:

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 has a low recursion limit but for a depth-first search this is normally not an issue (and it can be extended anyway by sys.setrecursionlimit).

这篇关于Python中的深度优先搜索算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！