深度優先搜索（圖形方法）

我一直在研究這個問題很長一段時間，幾乎都有。基本上，我正在執行深度優先搜索，跟蹤節點，以便找到目標節點並能夠跟蹤從開始節點到目標節點的路徑。我可以找到目標節點並可以跟蹤路徑，但是我遇到的問題是這樣的：深度優先搜索（圖形方法）

當我試圖重新創建我的路線時，我卡在無限循環中，例如節點x1點到節點x2，節點x2指向節點x1。這裏是相關的代碼（在python中）：

# Starting position 
stack = util.Stack() 
currentState = problem.getStartState() 
goalState = [] 
directions = {} 
visited = [] 


if problem.isGoalState(currentState): return [] 
else: 
    stack.push(currentState) 

while stack.isEmpty() == False: 
    currentState = stack.pop() 
    if currentState in visited: 
     continue 
    if problem.isGoalState(currentState): 
     goalState = currentState 
     break 
    visited.append(currentState) 
    for state in problem.getSuccessors(currentState): 
     stack.push(state[0]) 
     directions[state[0]] = (currentState, state[1]) 

print goalState 
goalState = directions[goalState][0] 
print goalState 
goalState = directions[goalState][0] 
print goalState 
goalState = directions[goalState][0] 
print goalState 
goalState = directions[goalState][0] 
print goalState 
goalState = directions[goalState][0] 
print goalState 
goalState = directions[goalState][0] 
print goalState 
goalState = directions[goalState][0]

每個狀態是（（座標節點），「方向行進」，成本）的元組。我明白我需要一個while循環來正確追溯啓動狀態，代碼的端部只是說明你們這樣的輸出：

 
(1, 1) 
(2, 1) 
(2, 2) 
(2, 1) 
(2, 2) 
(2, 1) 
(2, 2)

任何幫助，將不勝感激！這是我第一次在這裏發佈，所以我希望我做的一切都正確。

來源

2014-09-27 devii

在DFS算法中，您應該將每個節點標記爲「已訪問」並在繼續之前檢查節點是否「已訪問」，以避免此類無限循環。看起來你已經試圖做到這一點。你需要運行一個調試器來確定它爲什麼沒有按你期望的方式工作。 – 2014-09-27 21:38:02

您需要保存訪問節點時的方向，而不是將節點添加到堆棧時。

在當前代碼中，您將繼續覆蓋方向字典。

（。爲了解決這個問題，例如，你可以節省新的節點和堆棧上的父節點，然後只寫了方向字典，當你訪問節點）

順便說一句：

測試，如果你，如果你想你可能要考慮使用一個優先級隊列中的最小成本路徑使用一套不是列表
如果節點在訪問更有效（如Python的heapq模塊提供）代替堆棧

來源

2014-09-27 21:53:54

非常感謝！我在這個問題上絞盡腦汁想了很長時間，卻無法弄清楚我的錯誤。 – devii 2014-09-27 22:36:57

深度優先搜索（圖形方法）

回答

相關問題