10分钟教你用python动画演示深度优先算法搜寻逃出迷宫的路径Pythonpython函数基础教程-

@本文来源于公众号：csdn2299，喜欢可以关注公众号 程序员学府
深度优先算法(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)) 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)) 

非常感谢你的阅读
大学的时候选择了自学python，工作了发现吃了计算机基础不好的亏，学历不行这是
没办法的事，只能后天弥补，于是在编码之外开启了自己的逆袭之路，不断的学习python核心知识，深入的研习计算机基础知识，整理好了，如果你也不甘平庸，那就与我一起在编码之外，不断成长吧！
其实这里不仅有技术，更有那些技术之外的东西，比如，如何做一个精致的程序员，而不是“屌丝”，程序员本身就是高贵的一种存在啊，难道不是吗？[点击加入]想做你自己想成为高尚人，加油！