Python对 BFS(广度优先算法)讲解

hresh 535 0

Python对 BFS(广度优先算法)讲解

概述

BFS 算法像是近视的小明的眼镜掉在了地上,小明肯定是先摸索离手比较近的位置,然后手慢慢向远方延伸,直至摸到眼镜,像是以小明为中心搜索圈不断扩大的过程。

通常用队列(先进先出,FIFO)实现
初始化队列Q;
Q = {起点s};标记s为已访问;
while(Q非空):
    取Q队首元素u;u出队;
    if u == 目标状态 {...}
    所有与u相邻且未被访问的点进入队列;
    标记u为已访问;

如图所示:

在这里插入图片描述

实例讲解

“一马当先”

下过象棋的人都知道,马只能走'日'字形(包括旋转90°的日),现在想象一下,给你一个n行m列网格棋盘, 棋盘的左下角有一匹马,请你计算至少需要几步可以将它移动到棋盘的右上角,若无法走到,则输出-1. 如n=1,m=2,则至少需要1步;若n=1,m=3,则输出-1。

首先我们直接按照上面的程序流程来进行代码实现。

代码一:

from collections import deque

n = 3
m = 5

def steps_count2():
    '''
    BFS算法求解,广度优先搜索算法
    通常用队列(先进先出,FIFO)实现
        初始化队列Q;
        Q = {起点s};标记s为已访问;
        while(Q非空):
            取Q队首元素u;u出队;
            if u == 目标状态 {...}
            所有与u相邻且未被访问的点进入队列;
            标记u为已访问;
    :return:
    '''
    global m,n
    dx = [-1, -2, -2, -1, +1, +2, +2, +1]
    dy = [+2, +1, -1, -2, -2, -1, +1, +2]
    v = {(x, y): False for x in range(0, n + 1) for y in range(0, m + 1)}
    v[(0, 0)] = True
    q = deque([(0, 0, 0)])
    while len(q) > 0:
        p = q.popleft()
        for i in range(8):
            x = p[0] + dx[i]
            y = p[1] + dy[i]
            if x < 0 or x > n or y < 0 or y > m:
                continue
            if v[(x, y)]:
                continue
            v[(x, y)] = True
            q.append((x, y, p[2] + 1))
            if x == n and y == m:
                return p[2] + 1
    return -1

元素定义

  • dx、dy 分别指的是棋子下一步移动的可能性,这里采用枚举的方法给出了所有符合规则的移动策略,根据 i 值获得不同的移动的策略。
  • v 表示 n 行 m 列的坐标图,其中设定 (0,0)为坐标起点(左下角的起点),(n,m)为坐标终点(即右上角的终点)。声明 v
    时,将每个坐标置为 False,即为未走过;将 v[(0,0)]置为起点,状态改为 True。
  • q 表示队列,初始值为(0,0,0),其中前面两位指的是起点坐标,第三位指的是移动的步数。
  • p 表示从 q 左侧取出的第一个值,取出后并删除队列中的记录。

流程分析

  1. 从 q 中取值,得到 p(0,0,0),q 暂时为空。遍历 dx,dy,选择(0,0)的移动的策略,将移动后的结果值(x,y)进行大小比较,若不合适,则更换移动策略。判断(x,y)状态值是否为 True,如果为 True,则跳过(因为避免兜圈,导致步数过大,我们要求的是最小步数)。设置(x,y)状态值为 True,步数(p[2])加 1,放入队列中去。判断(x,y)与(n,m)是否相等,若相同则返回最小步数。
  2. 对(0,0)进行不同的移动后,获得的值都放入到 q 队列,接着对 q 队列进行取值判断。此时 q 队列值为[(2,1,1),(1,2,1)],取出最左侧的值(2,1,1),重复上述操作,最后 q 队列值为[(1,2,1),(3,3,2),(1,3,2),(0,2,2)],依次类推,直到(x,y)与(n,m)值相同,则返回步数。

代码二:

n = 3
m = 5

def steps_count4():
    global m, n
    dx = [+2, +1, -1, -2, -2, -1, +1, +2]
    dy = [-1, -2, -2, -1, +1, +2, +2, +1]
    temp = [set(), set([(0, 0)]), set()]
    t = 1
    f = True
    while f:
        f = False
        for loc in temp[1]:
            for i in range(8):
                x = loc[0] + dx[i]
                y = loc[1] + dy[i]
                if (x,y) == (m, n):
                    return t
                elif x >= 0 and y >= 0 and x <= m and y <= n and not ((x,y) in temp[0] or (x,y) in temp[1] or (x,y) in temp[2]):
                    temp[2].add((x,y))
                    f = True
        t += 1
        del temp[0]
        temp.append(set())
    return -1

元素定义

  • temp:用来存储不同层的坐标,其中 temp[0] 表示上一层,temp[1] 表示当前层,temp[2] 表示下一层。
  • f:逻辑型值,用来记录是否有新的坐标被丢入 temp[2] 中。
  • t:用于记录层数。

流程解析

  1. 创建一个序列 temp=[[],[[0,0]],[]],分别表示上一层、当前层、下一层;
  2. 初始化 t=1,f=True;
  3. 若 f 为 True 进入以下流程,否则输出 -1;
  4. 令 f=False,依次遍历 temp[1] 里的每一个坐标,对每一个坐标采取全部 8 种移动方式,若移动到了 [m,n] 则输出层数 t;
  5. 若移动后仍在棋盘内且不存在 temp 里任何一层中,则将这个坐标加入到 temp[2] 中,且令 f=True;
  6. 遍历完成后,del temp[0] 以控制数据量,这个操作同时使 temp[1] 顶替temp[0],temp[2] 顶替 temp[1],然后使用 append 方法插入一个新的空序列作为 temp[2],t+=1;
  7. 回到第三步并重复。

发表评论 取消回复
表情 图片 链接 代码

分享