10分鐘教你用python動(dòng)畫演示深度優(yōu)先算法搜尋逃出迷宮的路徑
深度優(yōu)先算法(DFS 算法)是什么?
尋找起始節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間路徑的算法,常用于搜索逃出迷宮的路徑。主要思想是,從入口開始,依次搜尋周圍可能的節(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開發(fā)工程師,從基礎(chǔ)的python腳本到web開發(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)開始,查詢下一步走得通的節(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)注明出處,謝謝!
- PHP 雙鏈表(SplDoublyLinkedList)簡(jiǎn)介和使用實(shí)例
- tween.js緩動(dòng)補(bǔ)間動(dòng)畫算法示例
- 利用JavaScript在網(wǎng)頁(yè)實(shí)現(xiàn)八數(shù)碼啟發(fā)式A*算法動(dòng)畫效果
- JavaScript排序算法動(dòng)畫演示效果的實(shí)現(xiàn)方法
- javascript動(dòng)畫算法實(shí)例分析
- 用隊(duì)列模擬jquery的動(dòng)畫算法實(shí)例
- 看動(dòng)畫學(xué)算法之Java實(shí)現(xiàn)doublyLinkedList
相關(guān)文章
PyTorch中g(shù)rid_sample的使用及說(shuō)明
這篇文章主要介紹了PyTorch中g(shù)rid_sample的使用及說(shuō)明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-02-02Python自動(dòng)安裝第三方庫(kù)的小技巧(pip使用詳解)
很多朋友私信小編Python安裝第三方庫(kù)安裝技巧,在這就不一一回復(fù)大家了,今天小編給大家分享一篇教程關(guān)于Python自動(dòng)安裝第三方庫(kù)的小技巧,本文以安裝plotly為例給大家詳細(xì)講解,感興趣的朋友跟隨小編一起看看吧2021-05-05Pycharm中出現(xiàn)ImportError:DLL load failed:找不到指定模塊的解決方法
這篇文章主要介紹了Pycharm中出現(xiàn)ImportError:DLL load failed:找不到指定模塊的解決方法,需要的朋友可以參考下2019-09-09python?AutoViz庫(kù)一行代碼實(shí)現(xiàn)可視化數(shù)據(jù)集
這篇文章主要介紹了python?AutoViz庫(kù)一行代碼實(shí)現(xiàn)可視化數(shù)據(jù)集實(shí)例探索,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2024-01-01Python實(shí)現(xiàn)bilibili時(shí)間長(zhǎng)度查詢的示例代碼
這篇文章主要介紹了Python實(shí)現(xiàn)bilibili時(shí)間長(zhǎng)度查詢的示例代碼,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-01-01