搜索算法的实现04《搜索算法的实现》课件

搜索算法的实现学 科：信息技术（浙教版）年 级：高三学 校：浙江大学附属中学深搜

广搜深搜结果：1

2

5

9

3

6

10

7

4

8广搜结果：1

2

3

4

5

6

7

8

9

10广度优先搜索算法的实现01算法原理逻辑实现广度优先搜索

遍历图广度优先搜索 简称BFS从图中一个未访问的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。假如我们有一个图，里面有A、B、C、D、E、F、G、H共8个顶点，点和点之间的连接如右图所示：如何对这个图进行广度优先的遍历呢？广度优先遍历需要借用的数据结构是队列（Queue）队列特点是先进先出（FIFO）广度优先搜索

遍历图headtail队列结果：如何利用

广度优先搜索

遍历迷宫

？02算法原理代码实现上机调试、验证1.

抽象与建模如何从 到 ？如下图，红色区域

表示

不能通行，绿色区域

表示

能通行，在迷宫中可以往上下左右四个绿色方向通行。xy探路规则上左下右逆时针2.

设计数据结构和算法思考：如何存储10*10的迷宫图案？（1）选择合适的数据结构迷宫图案中的通行区域用数字表示：1是可以通行的点，0是不能通行的点。这样，迷宫图案就转化成一0和1组成的二维表，可以存储成二维数组。0：不能通行1：可以通行2：已被访问遍历中需借助数据结构：队列2.

设计数据结构和算法（2）算法描述：创建一个空队列，将起点坐标A加入队列，并标记已访问；初始化flag为False。：队列非空，重复如下步骤：① 取出队首元素坐标（x,y）② 计算得到四个方向上的坐标（nx,ny）③ 判断（nx,ny）是否越界或已被访问，若符合条件将（nx,ny）入队，并标记已访问；同时判断是否达到终点B，达到终点flag标记为True；：通过flag判断迷宫是否为“通关迷宫”。3.

编写程序n=10#迷宫的规模que=[["",""]foriin

range(100)]head=tail=0que[tail]=[1,1];tail+=1

#起点入队，可以用变量maze[1][1]=2

#值为2，表示该点已被访问flag=False #初始化迷宫不通while

head!=tail:x,y=que[head];head+=1#队首元素出队创建一个空队列，起点坐标入队；标记起点坐标已被访问；标记flag为False。队非空，一直循环下列步骤：取出队首元素坐标（x,y）计算得到四个方向上的坐标（nx,ny）dirs=[[-1,0],[0,-1],[1,0],[0,1]]#往上、左、下、右四个方向搜索fordin

range(len(dirs)):#四个方向上遍历nx,ny=x+dirs[d][0],y+dirs[d][1]if(0<=nx<nand0<=ny<n

andmaze[nx][ny]==1):#（nx,xy）未越界，未标记，入队que[tail]=[nx,ny];tail+=1maze[nx][ny]=2#做标记，防止折回#（nx,xy）已到终点，标记flag为True判断（nx,ny）是否越界和已被访问，若符合条件，将（nx,ny）入队，并标记已访问；同时判断是否达到终点B，if

[nx,ny]==[8,8]:flag=True；print("success!")达到终点将flag标记为True；通过flag判断迷宫是否为“通关迷宫”。队非空4.

结果呈现5.

问题讨论，思考分析调试运行任务1，思考如下问题：（1）代码中利用二维数组maze存储迷宫图案，则len(maze)和len(maze[0])分别表示什么？总的行数总的列数行列坐标二维数组maze是用横纵坐标还是行列坐标来描述元素位置的？maze[x][y]表示什么？当其取值为0、1、2时分别有何含义？0：不能通行1：可以通行2：已被访问(x,y)的状态6.

拓展应用1如下图，红色区域

表示

不能通行，绿色区域

表示

能通行，在迷宫中可以往上下左右四个绿色方向通行。任务1：完成从到 是否通？任务2：能否通过改进程序段，分析得到到 最短路径？解决策略：起点位置坐标入队时，将当前步数

0也入队。每次到达某个点，除了坐标入队，将到当前位置所用步数也入队。起点A初始状态：（1，1，0）到迷宫中的任意位置最少17步最短14步达到终点6.

拓展应用1steps=0#新增变量，存储步数que[tail]=start+[steps]x,y,steps=que[head]que[tail]=[nx,ny]+[steps]print("到终点的最短步数：",steps)程序运行结果：steps+=1插入到哪里？que=[["","",""]foriin

range(100)]7.

拓展应用2如下图，红色区域

表示

不能通行，绿色区域

表示

能通行，在迷宫中可以往上下左右四个绿色方向通行。到到是否通？最短路径。任务1：任务2：任务3：输出这条最短路径。解决策略：遍历到的每个节点，记录坐标、步数、前驱节点起点A的入队状态：（1，1，0，-1）输出路径时，反向回溯遍历链表7.

拓展应用2如下图，红色区域

表示

不能通行，绿色区域

表示

能通行，在迷宫中可以往上下左右四个绿色方向通行。任务3：

输出这条最短路径。请在任务2的基础上，稍改进代码，输出右图的最短路径，调试结果如下图。7.

拓展应用2que[p][0]==start[0]and

que[p][1]==start[1]等价代码(3)(4)(5)(6)输出最短路径代码(7)(1)

que=[["","","",""]foriinrange(100)](2)任务4：体验利用Turtle库绘制迷宫地图，并进行深搜和广搜遍历。8.

本课小结1.

对比学习了深度优先搜索和广度优先搜索的算法策略。2.利用广度优先搜索算法走迷宫。① 任务1：判断A到B是否通畅。② 任务2：计算A到B的最短路径。③ 任务3：输出A到B的最短路径。④ 任务4：体验可视化绘制迷宫地图，并输出路径。⑤ 任务5：分析迷宫中任意两点的某著名企业情况。⑥ 任务6：分析迷宫中任意两点的最短路径（最优值）。链表搜索算法 再思考利用广度优先搜索解决问题，能找到最短路径，效率较高。广度优先搜的常见应