瞭解此深度第一個搜索算法

我已經給出了一個DFS算法，它返回到目標節點的最短路徑。它將一個圖形（所有節點及其路徑），一個起始節點，一個目標節點以及已訪問的節點列表（初始化爲空）作爲參數。這裏是代碼：瞭解此深度第一個搜索算法

def shortestPath(graph, start, end, visited = []): 
    path = str(start) 
    if start == end: 
     return path 
    shortest = None 
    for node in graph.childrenOf(start): 
     if str(node) not in visited: 
      visited = visited + [str(node)] 
      newPath = shortestPath(graph, start, end, visited) 
      if newPath = None: 
       continue 
      if shortest == None or len(newPath) < shortest: 
       shortest = newPath 
    if shortest != None: 
     path = path + shortest 
    else: 
     path = None 
    return path

我明白深度優先搜索的概念，但這種遞歸令人浮想聯翩。讓我知道我的思路是否完全符合軌道，哪裏出軌。

所以基本上，當newPath被分配一個值，這當然是對shortestPath的調用時發生遞歸。此時，遞歸會一直沿着圖形進行，直到它到達沒有子節點或目標節點的節點。如果它到達沒有孩子的節點不是目標，則忽略基本情況，並忽略整個for循環，返回值爲none。那麼None就是簡單地通過遞歸鏈。如果它到達目標節點，那麼遞歸的底層實際上會返回一個值（路徑），該值會回到遞歸的頂部。

此時我感到困惑，因爲「最短」的情況正在發生。所以每次爲newPath返回一個實際值時，最短的都會被賦值，但是它會被添加到路徑中。但是，讓我們說我有多條路徑到達目標節點。我成功找到第一條路徑，路徑等於所有newPath/shortests的總和。但是，對於下一個成功實現目標的遞歸，不要只是繼續添加更多的newPaths？那麼最終的結果是不是我可以訪問的每條路徑的長列表，而不是最短路徑的目標節點？

來源

2012-10-10 user1427661

提示：用紙和筆運行代碼以查看遞歸調用如何執行它們的操作（最好使用小圖形作爲輸入：p）。 – keyser

請注意，建議的算法 - 雖然正確，但效率不高。它會生成所有到達目標的路徑，並檢查哪些路徑是最好的。（有那些指數）。找到最短路徑的更有效的算法是[BFS]（http://en.wikipedia.org/wiki/Breadth-first_search） – amit

path變量是本地函數。每個遞歸調用都有自己的堆棧框架 - 它獨立於其他調用）。這意味着下一次通話開始時，一切都是全新的。

來源

2012-10-10 15:26:03

如果路徑對函數的每次調用都是局部的，路徑的最終值如何得到如何計算？如果我一直到遞歸的底部，並且每次調用都會計算path = path + shortest，但是每次調用都會重置路徑，那麼Python如何返回一個包含基本情況中的每個節點的值到開始？ – user1427661

查看'path = path + shortest'，'shortest'實際上包含下一個遞歸調用的路徑變量的值。 –

瞭解此深度第一個搜索算法

回答

相關問題