深度優(yōu)先算法(DFS 算法)是什么？

尋找起始節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間路徑的算法，常用于搜索逃出迷宮的路徑。主要思想是，從入口開(kāi)始，依次搜尋周圍可能的節(jié)點(diǎn)坐標(biāo)，但不會(huì)重復(fù)經(jīng)過(guò)同一個(gè)節(jié)點(diǎn)，且不能通過(guò)障礙節(jié)點(diǎn)。如果走到某個(gè)節(jié)點(diǎn)發(fā)現(xiàn)無(wú)路可走，那么就會(huì)回退到上一個(gè)節(jié)點(diǎn)，重新選擇其他路徑。直到找到出口，或者退到起點(diǎn)再也無(wú)路可走，游戲結(jié)束。當(dāng)然，深度優(yōu)先算法，只要查找到一條行得通的路徑，就會(huì)停止搜索；也就是說(shuō)只要有路可走，深度優(yōu)先算法就不會(huì)回退到上一步。

如果你依然在編程的世界里迷茫，可以加入我們的Python學(xué)習(xí)扣qun：784758214，看看前輩們是如何學(xué)習(xí)的！交流經(jīng)驗(yàn)！自己是一名高級(jí)python開(kāi)發(fā)工程師，從基礎(chǔ)的python腳本到web開(kāi)發(fā)、爬蟲、django、數(shù)據(jù)挖掘等，零基礎(chǔ)到項(xiàng)目實(shí)戰(zhàn)的資料都有整理。送給每一位python的小伙伴！分享一些學(xué)習(xí)的方法和需要注意的小細(xì)節(jié)，點(diǎn)擊加入我們的python學(xué)習(xí)者聚集地

下圖是使用 DFS 算法搜尋出來(lái)的一條路徑：

總結(jié)一下：

從起點(diǎn)開(kāi)始，查詢下一步走得通的節(jié)點(diǎn)，將這些可能的節(jié)點(diǎn)壓入堆棧中，已經(jīng)走過(guò)的節(jié)點(diǎn)不再嘗試。查詢完畢之后，從堆棧中取出一個(gè)節(jié)點(diǎn)，查詢?cè)摴?jié)點(diǎn)周圍是否存在走得通的節(jié)點(diǎn)。如果不存在可能的節(jié)點(diǎn)，就繼續(xù)從堆棧中取一個(gè)節(jié)點(diǎn)。重復(fù)以上操作，直到當(dāng)前節(jié)點(diǎn)為終點(diǎn)，或者堆棧中再無(wú)節(jié)點(diǎn)。

定義數(shù)據(jù)：

• 起始節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)
• 存儲(chǔ)節(jié)點(diǎn)的堆棧

定義輔助函數(shù)

• 獲取下一節(jié)點(diǎn)的函數(shù): successor
• 判斷是否為終點(diǎn)的函數(shù): test_goal

首先，我們來(lái)定義棧這種數(shù)據(jù)結(jié)構(gòu)，棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。

因?yàn)橹蟮膹V度優(yōu)先搜索會(huì)使用到隊(duì)列，A* 算法會(huì)用到優(yōu)先隊(duì)列，我們定義了抽象基類，以便后續(xù)使用。deque 是雙端隊(duì)列，與內(nèi)置類型 list 操作類似，但頭部與尾部插入和刪除操作的時(shí)間復(fù)雜度均為 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()
          

下面我們來(lái)定義 dfs 函數(shù)。其中，initial 為初始節(jié)點(diǎn), s 為棧，marked 用來(lái)記錄經(jīng)過(guò)的節(jié)點(diǎn)。successor 函數(shù)用來(lái)搜尋下一個(gè)可能的節(jié)點(diǎn)，test_goal 函數(shù)用來(lái)判斷該節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)。children 為可能的節(jié)點(diǎn)列表，遍歷這些節(jié)點(diǎn)，將沒(méi)有走過(guò)的節(jié)點(diǎn)壓入棧中，并做記錄。

            
# 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)
          

接下來(lái)，我們使用 DFS 算法尋找迷宮路徑，并對(duì)搜尋到的迷宮路徑進(jìn)行可視化演示。

首先使用枚舉，來(lái)表示路徑的顏色, EMPTY 為正常節(jié)點(diǎn)，BLOCKED 為障礙節(jié)點(diǎn)，START 為迷宮入口，END 為迷宮出口，PATH 為搜尋的路徑。

            
from enum import IntEnum
class Cell(IntEnum):
  EMPTY = 255
  BLOCKED = 0
  START = 100
  END = 200
  PATH = 150
          

接下來(lái)，我們來(lái)定義迷宮。首先，我們采用 Namedtuple 來(lái)定義迷宮每個(gè)節(jié)點(diǎn)的坐標(biāo)：

            
class MazeLocation(NamedTuple):
  row: int
  col: int
          

首先為了方便確定節(jié)點(diǎn)之間的關(guān)系，我們?cè)?Maze 類中定義了一個(gè)內(nèi)部類 _Node, 用來(lái)記錄節(jié)點(diǎn)的狀態(tài)，及節(jié)點(diǎn)的父節(jié)點(diǎn)。

            
class _Node:
  def __init__(self, state, parent):
    self.state = state
    self.parent = parent
          

接著初始化，確定入口與出口的坐標(biāo)，使用 np.random.choice 函數(shù)隨機(jī)生成迷宮，并標(biāo)記入口和出口。

            
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 方法，只要該節(jié)點(diǎn)坐標(biāo)與目標(biāo)節(jié)點(diǎn)相即可。

            
def _test_goal(self, m1: MazeLocation) -> bool:
  return m1 == self._end
          

再就是 successor 方法，只要上下左右方向的節(jié)點(diǎn)不是障礙節(jié)點(diǎn)且在邊界之內(nèi)，就納入考慮范圍，加入列表之中。

            
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 為是否繪圖標(biāo)志。通過(guò)目標(biāo)節(jié)點(diǎn)出發(fā)，遍歷每一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，直到到達(dá)初始節(jié)點(diǎn)，并繪制路徑圖。

            
None:
  if pause <= 0:
    raise ValueError('pause must be more than 0')
  path: Maze._Node = self._search()
  if path is None:
    print('沒(méi)有找到路徑')
    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 函數(shù)定義相差無(wú)幾。

            
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))
          

總結(jié)

以上所述是小編給大家介紹的10分鐘教你用python動(dòng)畫演示深度優(yōu)先算法搜尋逃出迷宮的路徑,希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
如果你覺(jué)得本文對(duì)你有幫助，歡迎轉(zhuǎn)載，煩請(qǐng)注明出處，謝謝！