深度優(yōu)先算法(DFS 算法)是什么塔鳍？
尋找起始節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間路徑的算法，常用于搜索逃出迷宮的路徑拜隧。主要思想是宿百，從入口開始，依次搜尋周圍可能的節(jié)點(diǎn)坐標(biāo)洪添，但不會(huì)重復(fù)經(jīng)過同一個(gè)節(jié)點(diǎn)垦页，且不能通過障礙節(jié)點(diǎn)。如果走到某個(gè)節(jié)點(diǎn)發(fā)現(xiàn)無路可走干奢，那么就會(huì)回退到上一個(gè)節(jié)點(diǎn)痊焊，重新選擇其他路徑。直到找到出口忿峻，或者退到起點(diǎn)再也無路可走薄啥，游戲結(jié)束。當(dāng)然逛尚，深度優(yōu)先算法垄惧，只要查找到一條行得通的路徑，就會(huì)停止搜索绰寞；也就是說只要有路可走到逊，深度優(yōu)先算法就不會(huì)回退到上一步。
下圖是使用 DFS 算法搜尋出來的一條路徑：
總結(jié)一下：
從起點(diǎn)開始滤钱，查詢下一步走得通的節(jié)點(diǎn)觉壶，將這些可能的節(jié)點(diǎn)壓入堆棧中，已經(jīng)走過的節(jié)點(diǎn)不再嘗試件缸。查詢完畢之后掰曾，從堆棧中取出一個(gè)節(jié)點(diǎn)，查詢該節(jié)點(diǎn)周圍是否存在走得通的節(jié)點(diǎn)停团。如果不存在可能的節(jié)點(diǎn)，就繼續(xù)從堆棧中取一個(gè)節(jié)點(diǎn)掏熬。重復(fù)以上操作佑稠，直到當(dāng)前節(jié)點(diǎn)為終點(diǎn)，或者堆棧中再無節(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
首先舌胶，我們來定義棧這種數(shù)據(jù)結(jié)構(gòu)，棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)疮丛，之前公眾號寫過一篇介紹性文章：
https://mp.weixin.qq.com/s/adC4Y3YWCuvLmjSuj90Mrw
因?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()
下面我們來定義 dfs 函數(shù)飒筑。其中，initial 為初始節(jié)點(diǎn), s 為棧绽昏，marked 用來記錄經(jīng)過的節(jié)點(diǎn)协屡。successor 函數(shù)用來搜尋下一個(gè)可能的節(jié)點(diǎn)，test_goal 函數(shù)用來判斷該節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)全谤。children 為可能的節(jié)點(diǎn)列表肤晓，遍歷這些節(jié)點(diǎn)，將沒有走過的節(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 = 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 算法尋找迷宮路徑余蟹，并對搜尋到的迷宮路徑進(jìn)行可視化演示。
首先使用枚舉子刮，來表示路徑的顏色, 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
接下來橱赠，我們來定義迷宮尤仍。首先，我們采用 Namedtuple 來定義迷宮每個(gè)節(jié)點(diǎn)的坐標(biāo)：
class MazeLocation(NamedTuple):
row: int
col: int
首先為了方便確定節(jié)點(diǎn)之間的關(guān)系狭姨，我們在 Maze 類中定義了一個(gè)內(nèi)部類 _Node, 用來記錄節(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)辆布，就納入考慮范圍瞬矩，加入列表之中。
def _success(self, m1: MazeLocation) -> 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)志锋玲。通過目標(biāo)節(jié)點(diǎn)出發(fā)景用，遍歷每一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，直到到達(dá)初始節(jié)點(diǎn)嫩絮，并繪制路徑圖丛肢。
def show_path(self, pause: float = 0.5, *, plot: bool = True) -> 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 函數(shù)定義相差無幾置尔。
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))
最后再放一張效果圖：
