写给妹妹的编程札记 5 - 搜索: 迷宫问题 - 广度优先搜索

2024-05-24 04:58

本文主要是介绍写给妹妹的编程札记 5 - 搜索: 迷宫问题 - 广度优先搜索,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

        让我们也使用广度优先搜索来解决一下迷宫问题,可以对比一下《写给妹妹的编程札记 4 - 搜索: 迷宫问题 - 深度优先搜索》。

        如在《写给妹妹的编程札记 3 - 穷举: 深度优先搜索/广度优先搜索》中描述的广度优先搜索, 对一个简单的例子,我们手动进行一遍迷宫遍历。每次找到队首的搜索状态,把从这个状态开始的全部状态加入队列。



        广度优先搜索, 我们需要一个队列来维护访问过的搜索状态。 对于每个搜索状态,我们记录该状态对应迷宫中的位置currX/currY, 从上一个状态怎么过来的: prevDir, 上一个状态在队列中的位置prevState。 后面两个信息prevDir/prevState主要是为了反向找到路径。

typedef struct tagMazeState {int currX;int currY;int prevDir;int prevState;
} MazeState;


        除了新创建的队列,跟深度优先搜索一样, 我们需要记录一个位置是否访问过 - isVisited数组。

void Search(char** maze, int row, int col)
{    bool** isVisited;isVisited = new bool*[row];for(int i = 0; i < row; i++) {isVisited[i] = new bool[col];memset(isVisited[i], 0, sizeof(bool) * col);}MazeState* queue = new MazeState[row * col];int queueHead = 0;int queueTail = 0;MazeState origin;origin.currX     = 0;origin.currY     = 0;origin.prevDir   = -1;origin.prevState = -1;// 判断起点是否为空位if (maze[0][0] != '.') {printf("Invalid maze. Origin maze[0][0] is blocked!\n");return;}// 判断是否已经到达终点if (origin.currX == row - 1 && origin.currY == col - 1) {printf("Already arrive target position!\n");return;}queue[queueTail++] = origin;isVisited[0][0] = 1;BFS(maze, row, col, isVisited, queue, queueHead, queueTail);for(int i = 0; i < row; i++) delete[] isVisited[i];delete[] isVisited;delete[] queue;
}


        有了搜索状态队列的支持, 广度优先搜索的代码就很简单了:

void BFS(char** maze, int row, int col, bool** isVisited, MazeState* queue, int queueHead, int queueTail)
{// 判断队列是否为空while (queueHead < queueTail) {// 取出队首的搜索状态int currX = queue[queueHead].currX;int currY = queue[queueHead].currY;printf("queueHead: (%d, %d)\n", currX, currY);// 检查从这个状态开始的所有能够到达的状态 (广度优先搜索)for (int k = 0; k < 4; k++) {int nextX = currX + direction[k][0];int nextY = currY + direction[k][1];// 检查保证新位置在迷宫内,没有离开迷宫, 且是空位(不能走到墙里面)if ((nextX >= 0) && (nextX < row) && (nextY >= 0) && (nextY < col) && (maze[nextX][nextY] == '.')) {// 找到可以走的方向后, 需要判断这个新的位置是否已经走过,如果已经走过,我们继续会走就出现环路if (!isVisited[nextX][nextY]) {// 标记搜索访问过isVisited[nextX][nextY] = 1;// 没有走过的新位置,加入队列 (广度优先搜索)MazeState nextState;nextState.currX     = nextX;nextState.currY     = nextY;nextState.prevDir   = k;nextState.prevState = queueHead;queue[queueTail++]  = nextState;// 一旦发现目标状态到达的话, 说明已经找到最短路径,输出if (nextX == row - 1 && nextY == col - 1) {// 输出最短路径DisplayPath(queue, queueTail - 1);// 终止搜索return;}}}}// 队首的搜索状态已经完成,从队列中删除 (没有实际删除,还在queue数组中,只是不在逻辑队列中[queueHead, queueTail) )queueHead++;}
}


        跟深度优先搜索不同的是,我们采取广度优先,多条路径同时进行,不能只使用一个path数组保存当前的路径。 对应于搜索状态队列中的每一个状态, 其实都对应着一条从起点开始到该状态的一条路径。为了反向找到这条路径,搜索状态队列中的每个状态都已经记录了从哪个状态过来的,怎么过来的。 我们需要反向找到这条路径:


// 输出从起点开始到(queue[targetPositionIndex].currX, queue[targetPositionIndex].currY)的路径
void DisplayPath(MazeState* queue, int targetPositionIndex)
{// 终止条件。 起点的前一个状态index为:-1if (targetPositionIndex < 0) {return;}// 前一个状态int previousPositionIndex = queue[targetPositionIndex].prevState;// 从前一个状态怎么过来的int previousDirection     = queue[targetPositionIndex].prevDir;// 先输出从起点到前一个状态的路径DisplayPath(queue, previousPositionIndex);// 再输出从前一个状态到当前状态的路径switch(previousDirection) {case 0: printf("N"); break;case 1: printf("S"); break;case 2: printf("W"); break;case 3: printf("E"); break;}
}




这篇关于写给妹妹的编程札记 5 - 搜索: 迷宫问题 - 广度优先搜索的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/997439

相关文章

Flask解决指定端口无法生效问题

《Flask解决指定端口无法生效问题》文章讲述了在使用PyCharm开发Flask应用时,启动地址与手动指定的IP端口不一致的问题,通过修改PyCharm的运行配置,将Flask项目的运行模式从Fla... 目录android问题重现解决方案问题重现手动指定的IP端口是app.run(host='0.0.

Seata之分布式事务问题及解决方案

《Seata之分布式事务问题及解决方案》:本文主要介绍Seata之分布式事务问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Seata–分布式事务解决方案简介同类产品对比环境搭建1.微服务2.SQL3.seata-server4.微服务配置事务模式1

mysql关联查询速度慢的问题及解决

《mysql关联查询速度慢的问题及解决》:本文主要介绍mysql关联查询速度慢的问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql关联查询速度慢1. 记录原因1.1 在一次线上的服务中1.2 最终发现2. 解决方案3. 具体操作总结mysql

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

Spring MVC跨域问题及解决

《SpringMVC跨域问题及解决》:本文主要介绍SpringMVC跨域问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录跨域问题不同的域同源策略解决方法1.CORS2.jsONP3.局部解决方案4.全局解决方法总结跨域问题不同的域协议、域名、端口

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

SpringBoot自定义注解如何解决公共字段填充问题

《SpringBoot自定义注解如何解决公共字段填充问题》本文介绍了在系统开发中,如何使用AOP切面编程实现公共字段自动填充的功能,从而简化代码,通过自定义注解和切面类,可以统一处理创建时间和修改时间... 目录1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3

基于.NET编写工具类解决JSON乱码问题

《基于.NET编写工具类解决JSON乱码问题》在开发过程中,我们经常会遇到JSON数据处理的问题,尤其是在数据传输和解析过程中,很容易出现编码错误导致的乱码问题,下面我们就来编写一个.NET工具类来解... 目录问题背景核心原理工具类实现使用示例总结在开发过程中,我们经常会遇到jsON数据处理的问题,尤其是

springboot3.4和mybatis plus的版本问题的解决

《springboot3.4和mybatisplus的版本问题的解决》本文主要介绍了springboot3.4和mybatisplus的版本问题的解决,主要由于SpringBoot3.4与MyBat... 报错1:spring-boot-starter/3.4.0/spring-boot-starter-

在 Spring Boot 中使用异步线程时的 HttpServletRequest 复用问题记录

《在SpringBoot中使用异步线程时的HttpServletRequest复用问题记录》文章讨论了在SpringBoot中使用异步线程时,由于HttpServletRequest复用导致... 目录一、问题描述:异步线程操作导致请求复用时 Cookie 解析失败1. 场景背景2. 问题根源二、问题详细分