存儲python的深度優先搜索路徑

我想寫一個矩形網格的DFS，我從某個（x，y）座標開始，必須達到目標座標（xg，yg）。我需要我的函數返回這實際上是我採取的路線清單的路徑，像存儲python的深度優先搜索路徑

到目前爲止我的代碼是這樣的

def depthFirstSearch(): 
    visited=[]    # stores the vertices that I have visited 
    action=[]     # this is what I have to return 
    stack=Stack()    # the general stack used in DFS 
    forward=Stack()   # stores the forward direction 
    reverse=Stack()   # stores the backward direction, in case we need to backtrack 
    stack.push(getStartState()) 

    while not stack.isEmpty(): 
     tmp=stack.pop() 
     if(GoalState(tmp)): 
      return action 
     if not tmp in visited: 
      visited.append(tmp) 
      if not forward.isEmpty(): 
       dirn=forward.pop() 
       action.append(dirn) 
       reverse.append(opposite(dirn)) 

     child1=getSuccessors(tmp) # returns all the possible childs and direction as a list 
     child2=[] 

     for st in child1: 
      if not st in visited: 
       child2.append(st) 

     if child2: 
      for state in child2: 
       stack.push(state[0]) 
       forward.push(state[1]) 
       reverse.push(oppposite(state[1]) 
     elif not child2: 
      action.append(reverse.pop())

我是python的新手，如果有人能幫忙，我會很感激我在這裏。我在縮進時遇到問題。此外，我不太清楚我的DFS存儲路徑的邏輯。請幫忙！！

來源

2012-10-14 OneMoreError

請正確縮進您的代碼，以便我們可以按照您的想法。應該將所有代碼段放在'depthFirstSearch'內嗎？ – jsbueno

希望這會說清楚。早點對不起！ – OneMoreError

你的問題不是很清楚。您的意思是說，當搜索到達死衚衕時，路徑需要包括回溯？ – Gene

這是一篇文章，解釋有關Depth First Search。你做的是以下，你有start節點，在你的情況(x,y)，然後你檢查你訪問的步驟是否已經達到goal這是(xg,yg)深度優先搜索的方式是，它維護一個堆棧並推動每個訪問節點進入堆棧並彈出它們並檢查它是否是目標。在您的程序中，您必須將該檢查步驟寫入列表中。我希望教程鏈接可以幫助你開始。

來源

2012-10-14 04:03:29

這裏的問題是，假設我在節點（x，y）上有兩個孩子（x1，y1）和（x2，y2），這兩個孩子都不是目標狀態。現在，當我去（x1，y1）時，從那裏我不能直接去（x2，y2）。我首先需要回到（x，y），然後再回到（x2，y2）。 – OneMoreError

嘗試將x1，y1作爲單個節點，在元組或兩個元素列表中進行處理。 –

這將如何幫助？ – OneMoreError

存儲python的深度優先搜索路徑

回答

相關問題