python - Python 中的深度优先搜索

Question

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

基本上我们有一个 peg-solitaire 棋盘:

[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()

您可能还希望保留反向链接，以便能够在最后发出导致找到的解决方案(如果有)的一系列移动，但这是一个附属问题。

我在您的代码中看不到这种一般结构(或其合理变体)的踪迹。为什么不尝试以这种方式记录呢？您只需要编写 possiblessuccessors 和 isending 代码(如果您坚持将位置保留为列表，则必须将其转换为元组以检查集合中的成员资格并添加设置，但是，这是非常小的；-)。