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）需要某种形式的栈（可以是系统自带的调用栈，或者你自己创建的栈）。那这个栈在哪里呢？

Answer 2

首先，深度优先搜索是基于树形结构的。这在这里是合理的，因为在大多数情况下，你有多个可能的移动选择。深度优先搜索会尝试第一个可能的移动，然后在新的情况中尝试第一个可能的移动，再在那个新的情况中继续尝试第一个可能的移动，直到找到成功的结果或者没有更多的移动选项为止。如果没有更多的选择，它会退回到上一步，寻找一个还没有尝试过的移动，然后再继续往下走。

实现这一过程的“正确”方式是使用递归。从我看到的，你的系统里没有使用递归。

像这样的方式可以工作（用简单的伪代码表达）：

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 3

在一个每一步都是从“棋盘位置”移动到下一个可能位置的情况下，通常实现深度优先搜索（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 这两个部分（如果你坚持把位置保持为列表，你需要把它转换成元组，这样才能检查是否在集合中并添加到集合中，不过这算是小事;-）。