在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可以返回先前遇到的狀態，那麼您可能擁有無限的決策樹，並且深度優先搜索可能會卡住沿着無限分支並錯過另一個分支上的正確解決方案。在這種情況下，您需要使用廣度優先搜索。