Maze試驗臺的設計與實作（寬度優先搜索和深度優先搜索的理解）
一、 寬度優先搜索
BFS，屬于一種盲目搜尋法，目的是系統地展開并檢查圖中的所有節點，以找尋結果，換句話說，它并不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止，在一棵樹上的搜索特點就是由根節點向深層逐層搜索，搜索完一層后再搜索下一層；在圖中搜索方式類似于“波浪“，由根節點一層一層的向外搜索，
用佇列實作寬度優先演算法：
1、把根節點放到佇列中，
2、每次從佇列的頭部取出一個元素v，判斷節點v是否被訪問：一、當節點v沒有被訪問時，執行步驟3、4、，二、v節點被訪問時，則不需要對節點v進行任何操作，重復步驟2，
3、對于沒有被訪問的節點v要進行以下幾個操作：一、判斷當前節點v是否是目標goal，若是則回傳目標，搜索結束，二、節點v不是目標節點，則將節點v標記為已訪問，并將v的所有孩子節點集合w放在佇列的末尾（對于一個圖來說，則是與之相鄰的上下四個節點），注：對于v的孩子節點入佇列前，加一個判斷，將那些已訪問或者是障礙物的孩子節點剔除），
4、如果遍歷整個樹還沒有找到，結束程式
def BFS(maze,v,goal,came_from):
frontier=Queue()#宣告一個佇列
frontier.enqueue(v)#將根節點v入佇列尾
came_from[v]=None#根節點的父節點為空
while not frontier.is_empty():
v=frontier.dequeue()#從佇列頭彈出一個節點
if maze[v[0],v[1]]==Maze.EMPTY:#在v節點是已被訪問或者是障礙物的時候，都無意義可直接跳過
if v==goal:
return v
else:
maze[v[0],v[1]]==Maze.OCCUPIED#當該節點不是目標節點時，將其標記為已訪問，并將其子節點入佇列尾
for w in Maze.getAllMoves(v[0],v[1]):#Maze.getAllMoves()方法是獲得與v節點相鄰的所有節點
if w==Maze.EMPTY:#有選擇的入佇列，排除無意義的節點（必要性：***一定要剔除已被訪問的節點，否則v擴展w入佇列，然后w出佇列，同時又同樣的擴展v，從而進入死回圈v,w不停地出入佇列，***
frontier.enqueue(w)
came_from[w]=v
return None
二、深度優先搜索
顧名思義，深度優先，則是以深度為準則，先一條路走到底，直到達到目標，也就是遞回下去，否則既沒有達到目標又無路可走了，那么則退回到上一步的狀態，走其他路，這便是回溯上來，
遞回實作
def DFS(maze,v,goal,came_from):
if came_from=={}:
came_from[v]=None
if v==goal:
return v
maze[v[0],v[1]]==Maze.OCCUPIED
for w in maze.getAllMOves(v[0],v[1]):
if maze[w[0],w[1]]==Maze.EMPTY:
came_from[w]=v
result=DFS(maze,w,goal,came_from)
if result==goal:
return result
return None
用堆疊實作
與寬度優先搜索很類似，但又有些差異，寬度是越深層的節點越后訪問，所以先來的節點先訪問，用佇列儲存；而深度優先搜索則相反，先來的節點后訪問，所以用堆疊來儲存，
def DFS(maze,v,goal,came_from):
stack=Stack()
stack.push(v)
came_from[v]=None#根節點的父節點為空
while not stack.is_empty():
v=stack.pop()
if maze[v[0],v[1]]==Maze.EMPTY:#在v節點是已被訪問或者是障礙物的時候，都無意義可直接跳過
if v==goal:
return v
else:
maze[v[0],v[1]]=Maze.OCCUPIED#當該節點不是目標節點時，將其標記為已訪問，并將其子節點入堆疊尾
for w in maze.getAllMoves(v[0],v[1]):
if maze[w[0],w[1]]==Maze.EMPTY:#v的子節點有可能已被訪問或者是障礙物，需判斷，洗掉后程式卡死，為什么？
stack.push(w) #關鍵在于有已被訪問的節點入堆疊由v擴展出w，v出堆疊；然后訪問w的時候，再由w擴展出v，因為v和w是相鄰關系， v再入堆疊，這樣就會形成死回圈
came_from[w]=v
return None
總結：深度優先搜索與寬度優先搜索之間的不同在分別用堆疊與佇列實作的時候非常明顯，歸結為一點就是給節點賦予的優先級不同，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/41827.html
標籤：其他