深度優先算法(DFS 算法)是什么？
尋找起始節點與目標節點之間路徑的算法，常用于搜索逃出迷宮的路徑。主要思想是，從入口開始，依次搜尋周圍可能的節點坐標，但不會重復經過同一個節點，且不能通過障礙節點。如果走到某個節點發現無路可走，那么就會回退到上一個節點，重新選擇其他路徑。直到找到出口，或者退到起點再也無路可走，游戲結束。當然，深度優先算法，只要查找到一條行得通的路徑，就會停止搜索；也就是說只要有路可走，深度優先算法就不會回退到上一步。
如果你依然在編程的世界里迷茫，可以加入我們的Python學習扣qun：784758214，看看前輩們是如何學習的！交流經驗！自己是一名高級python開發工程師，從基礎的python腳本到web開發、爬蟲、django、數據挖掘等，零基礎到項目實戰的資料都有整理。送給每一位python的小伙伴！分享一些學習的方法和需要注意的小細節，點擊加入我們的python學習者聚集地
下圖是使用 DFS 算法搜尋出來的一條路徑：
總結一下：
從起點開始，查詢下一步走得通的節點，將這些可能的節點壓入堆棧中，已經走過的節點不再嘗試。查詢完畢之后，從堆棧中取出一個節點，查詢該節點周圍是否存在走得通的節點。如果不存在可能的節點，就繼續從堆棧中取一個節點。重復以上操作，直到當前節點為終點，或者堆棧中再無節點。
定義數據：
- 起始節點與目標節點
- 存儲節點的堆棧
定義輔助函數
- 獲取下一節點的函數: successor
- 判斷是否為終點的函數: test_goal
首先，我們來定義棧這種數據結構，棧是一種后進先出的數據結構。
因為之后的廣度優先搜索會使用到隊列，A* 算法會用到優先隊列，我們定義了抽象基類，以便后續使用。deque 是雙端隊列，與內置類型 list 操作類似，但頭部與尾部插入和刪除操作的時間復雜度均為 O(1)。
# utils.py
from abc import abstractmethod, ABC
from collections import deque
class Base(ABC):
def __init__(self):
self._container = deque()
@abstractmethod
def push(self, value):
"""push item"""
@abstractmethod
def pop(self):
"""pop item"""
def __len__(self):
return len(self._container)
def __repr__(self):
return f'{type(self).__name__}({list(self._container)})'
class Stack(Base):
def push(self, value):
self._container.append(value)
def pop(self):
return self._container.pop()
下面我們來定義 dfs 函數。其中，initial 為初始節點, s 為棧，marked 用來記錄經過的節點。successor 函數用來搜尋下一個可能的節點，test_goal 函數用來判斷該節點是否為目標節點。children 為可能的節點列表，遍歷這些節點，將沒有走過的節點壓入棧中，并做記錄。
# find_path.py
from utils import Stack
def dfs(initial, _next = successor， _test = test_goal):
s: Stack = Stack()
marked = {initial}
s.push(initial)
while s:
parent: state = s.pop()
if _test(parent):
return parent
children = _next(parent)
for child in children:
if child not in marked:
marked.add(child)
s.push(child)
接下來，我們使用 DFS 算法尋找迷宮路徑，并對搜尋到的迷宮路徑進行可視化演示。
首先使用枚舉，來表示路徑的顏色, EMPTY 為正常節點，BLOCKED 為障礙節點，START 為迷宮入口，END 為迷宮出口，PATH 為搜尋的路徑。
from enum import IntEnum
class Cell(IntEnum):
EMPTY = 255
BLOCKED = 0
START = 100
END = 200
PATH = 150
接下來，我們來定義迷宮。首先，我們采用 Namedtuple 來定義迷宮每個節點的坐標：
class MazeLocation(NamedTuple):
row: int
col: int
首先為了方便確定節點之間的關系，我們在 Maze 類中定義了一個內部類 _Node, 用來記錄節點的狀態，及節點的父節點。
class _Node:
def __init__(self, state, parent):
self.state = state
self.parent = parent
接著初始化，確定入口與出口的坐標，使用
np.random.choice
函數隨機生成迷宮，并標記入口和出口。
def __init__(self, rows: int = 10, cols: int = 10,
sparse: float = 0.2, seed: int = 365,
start: MazeLocation = MazeLocation(0, 0),
end: MazeLocation = MazeLocation(9, 9), *,
grid: Optional[np.array] = None) -> None:
np.random.seed(seed)
self._start: MazeLocation = start
self._end: MazeLocation = end
self._grid: np.array = np.random.choice([Cell.BLOCKED, Cell.EMPTY],
(rows, cols), p=[sparse, 1 - sparse])
self._grid[start] = Cell.START
self._grid[end] = Cell.END
其次是
test_goal
方法，只要該節點坐標與目標節點相即可。
def _test_goal(self, m1: MazeLocation) -> bool:
return m1 == self._end
再就是
successor
方法，只要上下左右方向的節點不是障礙節點且在邊界之內，就納入考慮范圍，加入列表之中。
List[MazeLocation]:
location: List[MazeLocation] = []
row, col = self._grid.shape
if m1.row + 1 < row and self._grid[m1.row + 1, m1.col] != Cell.BLOCKED:
location.append(MazeLocation(m1.row + 1, m1.col))
if m1.row - 1 >= 0 and self._grid[m1.row - 1, m1.col] != Cell.BLOCKED:
location.append(MazeLocation(m1.row - 1, m1.col))
if m1.col + 1 < col and self._grid[m1.row, m1.col + 1] != Cell.BLOCKED:
location.append(MazeLocation(m1.row, m1.col + 1))
if m1.col - 1 >= 0 and self._grid[m1.row, m1.col - 1] != Cell.BLOCKED:
location.append(MazeLocation(m1.row, m1.col - 1))
return location
顯示路徑, pause 為顯示圖像的間隔,plot 為是否繪圖標志。通過目標節點出發，遍歷每一個節點的父節點，直到到達初始節點，并繪制路徑圖。
None:
if pause <= 0:
raise ValueError('pause must be more than 0')
path: Maze._Node = self._search()
if path is None:
print('沒有找到路徑')
return
path = path.parent
while path.parent is not None:
self._grid[path.state] = Cell.PATH
if plot:
self._draw(pause)
path = path.parent
print('Path Done')
為了使用 DFS 算法，我們定義了 DepthFirstSearch 類，繼承迷宮類。
DepthFirstSearch
類重寫了基類的 _search 方法，與我們之前定義的 dfs 函數定義相差無幾。
class DepthFirstSearch(Maze):
def _search(self):
stack: Stack = Stack()
initial: DepthFirstSearch._Node = self._Node(self._start, None)
marked: Set[MazeLocation] = {initial.state}
stack.push(initial)
while stack:
parent: DepthFirstSearch._Node = stack.pop()
state: MazeLocation = parent.state
if self._test_goal(state):
return parent
children: List[MazeLocation] = self._success(state)
for child in children:
if child not in marked:
marked.add(child)
stack.push(self._Node(child, parent))
總結
以上所述是小編給大家介紹的10分鐘教你用python動畫演示深度優先算法搜尋逃出迷宮的路徑,希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對腳本之家網站的支持！
如果你覺得本文對你有幫助，歡迎轉載，煩請注明出處，謝謝！
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
