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. 看上去好像没跟着干，有什么

帮我吗？

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代码(如果您坚持将一个位置作为列表保存，则必须将其转换为元组，以检查set中的成员资格并添加到set中，但这很小；-)。

Answer 2

看起来，您并不是在创建新的节点，而是重复使用现有的节点。DFS需要某种类型的堆栈(调用堆栈或您自己的堆栈)。那是哪里？

Answer 3

首先，深度优先搜索假设是一棵树。现在，这在这里是有意义的，因为在大多数情况下，您有几个可能的移动。深度搜索首先尝试第一个可能的移动，然后在新的情况下尝试第一个可能的移动，然后在新的情况下进行第一个可能的移动，直到成功或不再有可能的移动为止，在这种情况下，它会向后退，直到找到一个它还没有尝试过的移动，然后再次下降。

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

像这样的东西会起作用的(pythonic psuedo可待因英语)：

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