欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

10分鐘教你用python動畫演示深度優(yōu)先算法搜尋逃出迷宮的路徑

 更新時間:2019年08月12日 15:44:44   作者:學好Python爬蟲  
這篇文章主要介紹了10分鐘教你用python動畫演示深度優(yōu)先算法搜尋逃出迷宮的路徑,非常不錯,具有一定的參考借鑒價值,需要的朋友可以參考下

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

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

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

下圖是使用 DFS 算法搜尋出來的一條路徑:

總結(jié)一下:

從起點開始,查詢下一步走得通的節(jié)點,將這些可能的節(jié)點壓入堆棧中,已經(jīng)走過的節(jié)點不再嘗試。查詢完畢之后,從堆棧中取出一個節(jié)點,查詢該節(jié)點周圍是否存在走得通的節(jié)點。如果不存在可能的節(jié)點,就繼續(xù)從堆棧中取一個節(jié)點。重復以上操作,直到當前節(jié)點為終點,或者堆棧中再無節(jié)點。

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

  • 起始節(jié)點與目標節(jié)點
  • 存儲節(jié)點的堆棧

定義輔助函數(shù)

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

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

因為之后的廣度優(yōu)先搜索會使用到隊列,A* 算法會用到優(yōu)先隊列,我們定義了抽象基類,以便后續(xù)使用。deque 是雙端隊列,與內(nèi)置類型 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 函數(shù)。其中,initial 為初始節(jié)點, s 為棧,marked 用來記錄經(jīng)過的節(jié)點。successor 函數(shù)用來搜尋下一個可能的節(jié)點,test_goal 函數(shù)用來判斷該節(jié)點是否為目標節(jié)點。children 為可能的節(jié)點列表,遍歷這些節(jié)點,將沒有走過的節(jié)點壓入棧中,并做記錄。

# 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 為正常節(jié)點,BLOCKED 為障礙節(jié)點,START 為迷宮入口,END 為迷宮出口,PATH 為搜尋的路徑。

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

接下來,我們來定義迷宮。首先,我們采用 Namedtuple 來定義迷宮每個節(jié)點的坐標:

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

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

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

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

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é)點坐標與目標節(jié)點相即可。

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

再就是 successor 方法,只要上下左右方向的節(jié)點不是障礙節(jié)點且在邊界之內(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 為是否繪圖標志。通過目標節(jié)點出發(fā),遍歷每一個節(jié)點的父節(jié)點,直到到達初始節(jié)點,并繪制路徑圖。

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

總結(jié)

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

相關(guān)文章

  • Python模塊、包和發(fā)布模塊示例代碼

    Python模塊、包和發(fā)布模塊示例代碼

    模塊是python程序架構(gòu)的一個核心概念,模塊名同樣也是一個標識符,需要符合標識符的命名規(guī)則,接下來通過本文給大家講解Python模塊、包和發(fā)布模塊,需要的朋友可以參考下
    2023-01-01
  • python中base64加密解密方法實例分析

    python中base64加密解密方法實例分析

    這篇文章主要介紹了python中base64加密解密方法,實例分析了base64加密解密的原理、用途與相關(guān)使用技巧,需要的朋友可以參考下
    2015-05-05
  • PyTorch中g(shù)rid_sample的使用及說明

    PyTorch中g(shù)rid_sample的使用及說明

    這篇文章主要介紹了PyTorch中g(shù)rid_sample的使用及說明,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-02-02
  • opencv python 傅里葉變換的使用

    opencv python 傅里葉變換的使用

    這篇文章主要介紹了opencv python 傅里葉變換的使用,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2018-07-07
  • Python自動安裝第三方庫的小技巧(pip使用詳解)

    Python自動安裝第三方庫的小技巧(pip使用詳解)

    很多朋友私信小編Python安裝第三方庫安裝技巧,在這就不一一回復大家了,今天小編給大家分享一篇教程關(guān)于Python自動安裝第三方庫的小技巧,本文以安裝plotly為例給大家詳細講解,感興趣的朋友跟隨小編一起看看吧
    2021-05-05
  • TensorFlow 模型載入方法匯總(小結(jié))

    TensorFlow 模型載入方法匯總(小結(jié))

    這篇文章主要介紹了TensorFlow 模型載入方法匯總(小結(jié)),小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2018-06-06
  • python實現(xiàn)俄羅斯方塊游戲

    python實現(xiàn)俄羅斯方塊游戲

    這篇文章主要為大家介紹了python實現(xiàn)俄羅斯方塊游戲的詳細代碼,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-06-06
  • Pycharm中出現(xiàn)ImportError:DLL load failed:找不到指定模塊的解決方法

    Pycharm中出現(xiàn)ImportError:DLL load failed:找不到指定模塊的解決方法

    這篇文章主要介紹了Pycharm中出現(xiàn)ImportError:DLL load failed:找不到指定模塊的解決方法,需要的朋友可以參考下
    2019-09-09
  • python?AutoViz庫一行代碼實現(xiàn)可視化數(shù)據(jù)集

    python?AutoViz庫一行代碼實現(xiàn)可視化數(shù)據(jù)集

    這篇文章主要介紹了python?AutoViz庫一行代碼實現(xiàn)可視化數(shù)據(jù)集實例探索,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2024-01-01
  • Python實現(xiàn)bilibili時間長度查詢的示例代碼

    Python實現(xiàn)bilibili時間長度查詢的示例代碼

    這篇文章主要介紹了Python實現(xiàn)bilibili時間長度查詢的示例代碼,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-01-01

最新評論