Python 中的深度优先搜索

Question

我正在尝试在 Python 中进行深度优先搜索，但它不起作用。

基本上我们有一个钉子接龙板：

[1,1,1,1,1,0,1,1,1,1]

1 代表一个钉子，0 代表一个空位。您必须一次将一个钉子向后或向前移动两个槽，仅移动到空位置。如果您在此过程中跳过另一个钉子，它就会变成一个空槽。这样做直到剩下一根钉子。基本上，游戏是这样的：

[1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 0, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 1, 0, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 1, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 1, 0, 1] #etc until only 1 peg left

这就是我所拥有的：

class MiniPeg():
    def start(self):
        ''' returns the starting board '''
        board = [1,1,1,1,1,0,1,1,1,1]
        return board

    def goal(self, node):
        pegs = 0

        for pos in node:
            if pos == 1:
                pegs += 1

        return (pegs == 1) # returns True if there is only 1 peg

    def succ(self, node):
        pos = 0
        for peg in node:
            if peg == 1:                
                if pos < (len(node) - 2):  # try to go forward
                    if node[pos+2] == 0 and node[pos+1] == 1:
                        return create_new_node(node, pos, pos+2)

                if pos > 2: # try to go backwards 
                    if node[pos-2] == 0 and node[pos-1] == 1:
                        return create_new_node(node, pos, pos-2)
        pos += 1

def create_new_node(node, fr, to):
    node[fr] = 0
    node[to] = 1
    if fr > to:
        node[fr-1] = 0
    else:
        node[fr+1] = 0
    return node

if __name__ == "__main__":
    s = MiniPeg()
    b = s.start()

    while not s.goal(b):
        print b
        b = s.succ(b)

那么，现在我的问题是：

1. 这是对此进行深度优先搜索的正确方法吗？
2. 我的算法不行！！！它被卡住了。在来这里提问之前，我已经为此苦苦挣扎了好几天，所以请帮忙。
3. 看来我没有遵循 DRY，有什么建议吗？
4. 天啊帮帮我吗？

Answer 1

在每一步都是从“棋盘位置”“移动”到某个可能的下一个位置直到达到目标的情况下，实现 DFS 的正常方法如下（伪代码）

seenpositions = set()
currentpositions = set([startingposition])
while currentpositions:
  nextpositions = set()
  for p in currentpositions:
    seenpositions.add(p)
    succ = possiblesuccessors(p)
    for np in succ:
      if np in seenpositions: continue
      if isending(np): raise FoundSolution(np)
      nextpositions.add(np)
  currentpositions = nextpositions
raise NoSolutionExists()

您可能还想保留向后链接最后能够发出一系列导致找到解决方案（如果有的话）的动作，但这是一个附带问题。

我在您的代码中没有识别出这种一般结构（或其合理变体）的痕迹。为什么不尝试用这种方式记录下来呢？您只需要编写possiblesuccessors和isending（如果您坚持将位置保留为列表，则必须将其转换为元组以检查集合中的成员资格并添加设置，但是，这是相当小的；-)。

Answer 2

您似乎并未创建新节点，而只是重用现有节点。 DFS 需要某种类型的堆栈（调用堆栈或您自己的堆栈）。哪里是？

Answer 3

好吧，首先深度优先搜索假设有一棵树。现在，这在这里是有意义的，因为在大多数情况下你有几种可能的动作。深度优先搜索将简单地尝试第一个可能的移动，然后是新情况下的第一个可能的移动，以及该新情况下的第一个可能的移动，直到成功或不再有可能的移动，在这种情况下，它将备份直到它找到了一个没有尝试过的动作，然后再次下降。

这样做的“正确”方法是使用递归。据我所知，你的系统中没有递归。

像这样的东西会起作用（pythonic psuedo codeish english）：

def try_next_move(self, board):
    for each of the pegs in the board:
        if the peg can be moved:
            new_board = board with the peg moved
            if new_board is solved:
                return True
            if self.try_next_move(new_board):
                return True
            # That move didn't lead to a solution. Try the next.
    # No move  worked.
    return False

Answer 4

基本的算法问题是，succ 函数始终只为给定的棋盘状态生成一种可能的走法。即使有多个可能的移动，succ 函数也只会返回它能找到的第一个移动。深度优先搜索需要处理每个状态下所有可能的移动。

进一步的问题可能来自这样一个事实：create_new_node 尽管它的名称如此，但实际上并没有创建新节点，而是修改了现有节点。对于想要保留前一个节点的深度优先搜索，如果此函数实际上创建了它作为参数获取的列表的副本，那就更好了。

另外，在检查 succ 中向后移动的可能性时，只有在 pos > 时才尝试这样做。 2.。这太严格了， pos > 1 也可以。