Python中的深度优先搜索

Question

好的，简单来说，我正在为一个迷你跳棋游戏做深度优先搜索。对于不熟悉这个游戏的人来说，它其实很简单。

这个游戏有一个有10个洞和9个棋子的棋盘，棋子用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

我这里有一个生成器函数，可以找到某个“节点”或者说棋盘的所有合法移动：

def succ(self, node):
    size = len(node)

    # find all legal moves going forward
    for pos in range(0, size-1):
        new_node = list(node)
        if ((node[pos] == 1) and (pos < (size - 2)) and (node[pos+2] == 0)):
            new_node[pos] = 0  # we're moving now
            new_node[pos+2] = 1 # this is where we're moving the peg to
            new_node[pos+1] = 0  # take out the peg here if there was one
            yield new_node

    # find all legal moves going backwards
    for pos in range(0, size-1):
        new_node = list(node)
        if ((node[pos] == 1) and (pos > 1) and (node[pos-2] == 0)):
            new_node[pos] = 0  # we're moving now
            new_node[pos-2] = 1 # this is where we're moving the peg
            new_node[pos-1] = 0  # take out the peg here if there was one
            yield new_node

如果你知道深度优先搜索，这看起来是个很好的生成器，可以用来解决这个难题。或者说，是吗？（我觉得是的，也许你能帮我想出更符合Python风格的方法？）

不过，我的递归解题函数用这个生成器时没有正常工作，也许你能帮我一下？

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 solve_board(dfs_obj, node):
    if goal(node):  # only 1 peg!
        print node
        return node

    for new_node in succ(node):
        print new_node
        return solve_board(new_node)

if __name__ == "__main__":
    solve_board([1, 1, 1, 1, 1, 0, 1, 1, 1, 1])

基本上我觉得我的succ()函数做的没错（也许不是？），但我的solve_board()递归可能有问题，因为棋盘没有解决。

Answer 1

我还没搞懂你的 succ() 函数，不过假设它是有效的，那么程序的其他部分确实是在进行深度优先搜索。我猜这个代码没有结束对吧？如果 succ 能返回之前遇到过的状态，那可能会出现一个无限的决策树，深度优先搜索可能会一直往下走这个无限的分支，结果错过了其他分支上的正确解。在这种情况下，你需要使用广度优先搜索。

Answer 2

因为你可以跳过空洞，所以你需要记住自己已经访问过哪些节点。否则，你可能会陷入无限循环。

在找到目标之前，你也不要提前结束这个循环。

tested_nodes=set()
def solve_board(dfs_obj, node):
    if goal(node):  # only 1 peg!
        print node
        return node

    for new_node in succ(node):
        if tuple(new_node) not in tested_nodes:
            tested_nodes.add(tuple(new_node))
            print new_node
            result = solve_board(new_node)
            if result:  # True if it's a goal, None otherwise
                return result

你的succ函数中的范围设置错了，计算范围时不应该从大小减去1。你也可以这样重写它，这样就能减少一个if条件。

def succ(self, node):
    size = len(node)

    # find all legal moves going forward
    for pos in range(size-2):
        new_node = list(node)
        if ((node[pos] == 1) and (node[pos+2] == 0)):
            new_node[pos] = 0  # we're moving now
            new_node[pos+2] = 1 # this is where we're moving the peg to
            new_node[pos+1] = 0  # take out the peg here if there was one
            yield new_node

    # find all legal moves going backwards
    for pos in range(1,size):
        new_node = list(node)
        if ((node[pos] == 1) and (node[pos-2] == 0)):
            new_node[pos] = 0  # we're moving now
            new_node[pos-2] = 1 # this is where we're moving the peg
            new_node[pos-1] = 0  # take out the peg here if there was one
            yield new_node

另一种写succ函数的方法是

def succ(self, node):
    for i in range(len(node)-2):
        j=i+3
        if node[i:j]==[1,1,0]:
            yield node[:i]+[0,0,1]+node[j:]
        if node[i:j]==[0,1,1]:
            yield node[:i]+[1,0,0]+node[j:]
        if node[i:j]==[1,0,0]:
            yield node[:i]+[0,0,1]+node[j:]
        if node[i:j]==[0,0,1]:
            yield node[:i]+[1,0,0]+node[j:]

这样稍微调整了深度优先搜索的方式，更倾向于选择移除一个钉子的移动。