欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

python 实现深度优先搜索(DFS)

程序员文章站 2022-06-11 12:25:37
...

深度优先算法(DFS 算法)是什么?

寻找起始节点与目标节点之间路径的算法,常用于搜索逃出迷宫的路径。主要思想是,从入口开始,依次搜寻周围可能的节点坐标,但不会重复经过同一个节点,且不能通过障碍节点。如果走到某个节点发现无路可走,那么就会回退到上一个节点,重新选择其他路径。直到找到出口,或者退到起点再也无路可走,游戏结束。当然,深度优先算法,只要查找到一条行得通的路径,就会停止搜索;也就是说只要有路可走,深度优先算法就不会回退到上一步。

下图是使用 DFS 算法搜寻出来的一条路径:

python 实现深度优先搜索(DFS)

总结一下:

从起点开始,查询下一步走得通的节点,将这些可能的节点压入堆栈中,已经走过的节点不再尝试。查询完毕之后,从堆栈中取出一个节点,查询该节点周围是否存在走得通的节点。如果不存在可能的节点,就继续从堆栈中取一个节点。重复以上操作,直到当前节点为终点,或者堆栈中再无节点。

定义数据:

  • 起始节点与目标节点
  • 存储节点的堆栈

定义辅助函数

  • 获取下一节点的函数: successor
  • 判断是否为终点的函数: test_goal

首先,我们来定义栈这种数据结构,栈是一种后进先出的数据结构,之前公众号写过一篇介绍性文章:

https://mp.weixin.qq.com/s/adC4Y3YWCuvLmjSuj90Mrw

因为之后的广度优先搜索会使用到队列,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 = 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 方法,只要上下左右方向的节点不是障碍节点且在边界之内,就纳入考虑范围,加入列表之中。

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 为是否绘图标志。通过目标节点出发,遍历每一个节点的父节点,直到到达初始节点,并绘制路径图。

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 函数定义相差无几。

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 实现深度优先搜索(DFS)