在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 

现在，如果你知道深度优先搜索，这似乎是一个伟大的发电机在解决这个难题时使用。或者是？ （我想是的，也许你可以帮助提出更Pythonic的方式？）

那么，我的递归拼图解算器功能，将使用发电机不工作，也许你可以帮我吗？

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

由于您可以跳过空洞，因此您必须跟踪您已经访问过的任何节点。否则，你将会有一个无限循环。

您还需要不带有短路for循环，除非你已经找到了目标

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 funtion会

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:] 

这由宁愿举动，除去调谐深度第一微小一个挂钩

Answer 2

我还没有解析你的succ（）函数，但假设它可以工作，那么程序的其余部分确实会进行深度优先搜索。我认为代码不会终止？如果succ可以返回先前遇到的状态，那么您可能拥有无限的决策树，并且深度优先搜索可能会卡住沿着无限分支并错过另一个分支上的正确解决方案。在这种情况下，您需要使用广度优先搜索。