在python中實現遞歸深度優先算法的錯誤

-1

我在udacity上做了一些實踐問題，必須編寫一些遞歸代碼來查找節點中朋友的路徑。我想出了這個。然而，遞歸定義缺少停止條件，我認爲沒有找到連接。我如何解決它？網絡的在python中實現遞歸深度優先算法的錯誤

def path_to_friend(network, user_A, user_B,traversed = None): 
    if traversed is None: 
     traversed = [] 

    if (user_B in network and user_A in network): 
     if user_B in get_connections(network,user_A): 
      return [user_A] + [user_B] 
     else: 
      for conn in get_connections(network,user_A) : 
       if conn in traversed: 
        continue 
       else: 
        traversed.append(conn) 
        return [user_A] + path_to_friend(network,conn,user_B) 
    else: 
     return None

數據結構：{ '鮑勃'：[[ '卡羅爾']，[]]， '愛麗絲'：[[ '鮑勃']，[]]， '卡羅爾'：[[」鮑勃 ']，[]]}

爲了找到：path_to_friend（網絡，' 鮑勃」， '愛麗絲'）

結果：無限遞歸。我如何解決它？

來源

2015-10-18 Kartik Kapoor

你失蹤，至少，因爲當''LEN（網絡）的條件== 0''。我認爲它應該返回''None''或者什麼 –

爲什麼你的值是列表的列表，什麼是get_connections？ –

這行代碼在這裏可能會導致此問題：

return [user_A] + path_to_friend(network,conn,user_B)

基本上這個代碼，只要任何連接發現尚未訪問運行。因此，代碼將在第一個未訪問路徑中搜索連接，否則將不再路徑。

  c ---- e 
     /
a ---- b 
     \ 
     d

如果你開始在和目標節點是E，你的代碼將只能達到E，如果c在get_connections(network , b) d前出現，否則代碼將在d結束。這種行爲甚至沒有定義/執行路徑不會以return -statement結尾。

最簡單的解決辦法是簡單地返回None，如果路徑沒有找到節點結束：

for conn in get_connections(network,user_A) : 
    if conn in traversed: 
     continue 
    else: 
     traversed.append(conn) 
     tmp = path_to_friend(network , conn , user_B) 
     if (tmp is not None): 
      return [user_A] + tmp//a matching path was found 

//no matching path was found -> return none 
return None

下一頁問題代碼：你不是從一個調用保持走過列表接下來，每次調用該函數時，traversed is None都成立。使用每個呼叫的遍歷列表作爲參數，爲後續的呼叫：

path_to_friend(network,conn,user_B, traversed)

來源

2015-10-18 09:33:22 Paul

我已經更新了代碼。但仍然陷入無限循環。似乎遍歷列表正在每個函數調用中創建。我該如何解決。 –

@KartikKapoor我已經更新了答案，應該修復這個問題。 – Paul

def path_to_friend(network, user_A, user_B,traversed = None): 
if traversed is None: 
    traversed = [] 

if (user_B in network and user_A in network): 
    if user_B in network[user_A][0] : 
     return [user_A] + [user_B] 
    else: 
     for conn in network[user_A][0] : 
      if conn in traversed: 
       continue 
      else: 
       traversed.append(conn) 
       temp = path_to_friend(network,conn,user_B,traversed) 
       if (temp is not None): 
        return [user_A] + temp 
     return None 
else: 
    return None 


network = {'Bob': [['Carol'], []], 'Alice': [['Bob'], []], 'Carol': [['Bob'], []]} 
path_to_friend(network,'Bob','Alice')

來源

2015-10-18 11:20:05

在python中實現遞歸深度優先算法的錯誤

回答

相關問題