深度优先在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. omg帮帮我？

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(如果你坚持保持一个位置作为一个列表你必须把它变成一个元组来检查集合中的成员资格并添加到集合,但是,这是非常小的;-).