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

2024-05-24 04:58

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

        写给妹妹的编程札记 3 - 穷举: 深度优先搜索/广度优先搜索中, 我们了解到基本的深度优先搜索和广度优先搜索。 来点实战吧, 使用搜索技术来解决一些实际的问题。 


        首先来看看怎么使用深度优先搜索解决迷宫问题?

        假设,输入的迷宫如下列数据表示: 

                第一行包含两个整数,分别表示行数 - r 和列数 - c

                从第二行开始,包括r行, 每行c个字符。 “#”表示墙壁,不能通过; “.”表示空位,可以通过

        我们需要解决的问题是,寻找从[0][0]这个位置,走到[r-1][c-1]这个位置的最短路径。


3 4
...#
.#.#
....
6 8
.#######
.......#
.##.##.#
....#.##
#.######
#.......


        《写给妹妹的编程札记 3 - 穷举: 深度优先搜索/广度优先搜索》中讨论的是树的遍历,怎么跟迷宫关联到一起呢?

        假设使用“@”表示人所在的位置,人在迷宫中不同位置的时候,属于不同的状态。 初始状态为: 人在[0][0]这个位置。 而目标状态为: 人在[r-1][c-1]这个状态。如果两个状态能够通过走一步到达,我们说两个状态是相连的。 比如[0][0] - [1][0]是相连的,因为人可以从[0][0]走一步到达[1][0]。我们就是需要找一条最短的路,从初始状态走到目标状态。状态之间的关联,不是一棵树,因为两个状态之间可能有多条路。但,我们还是可以类似地得到一棵搜索树:


        由于实际状态之间关系是图, 所以搜索树上有很多相同的节点。 我们搜索的时候要避免重复处理这些重复的节点(状态),因为从这些重复的状态开始的搜索树都是一样的,只会导致重复计算。在使用深度优先搜索的时候, 因为题目要求找出路径最短的方案,我们需要把所有的方案找出来,从中再挑一个路径最短的。 需要说明的是, 虽然说我们要把”所有“的方案找出来,如《写给妹妹的编程札记 2 - 穷举: 初识剪枝》提及, 如果找到一条路径比当前最好的要差,当然可以剪枝,不需要考虑,因为即使找到也不可能比当前解要好。


        首先,把输入迷宫数据存储起来, 使用一个二维数据char** maze存储迷宫里面的空位和墙, 整数row表示迷宫的行数, col表示迷宫的列数:

int main()
{char** maze;int row, col;FILE* fin = fopen("in.txt", "r");while(2 == fscanf(fin, "%d%d", &row, &col)) {printf("\nrow=%d, col=%d\n", row, col);// Init maze and read input maze datamaze = new char*[row];for(int i = 0; i < row; i++) {maze[i] = new char[col + 1];fscanf(fin, "%s", maze[i]);printf("%s\n", maze[i]);}// SearchSearch(maze, row, col);// free maze datafor(int i = 0; i < row; i++) delete[] maze[i];delete[] maze;}fclose(fin);
}


        核心搜索逻辑,在函数Search(maze, row, col)中实现。 在搜索过程中,如上述描述, 我们需要记录某个状态是否已经达到过。每个状态都可以使用在迷宫中的位置表示, 所以,使用isVisited[x][y]表示当前路径是否经过位置(x, y)。 同时,申请一段空间int path[]来存储我们的迷宫游走路径。 每个位置,我们都可以往东西南北四个方向走动,所以,游走的路径只需要记录一个东西南北走动的序列即可。

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);}int* path = new int[row * col];isVisited[0][0] = 1;DFS(maze, row, col, isVisited, path, 0, 0, 0);for(int i = 0; i < row; i++) delete[] isVisited[i];delete[] isVisited;delete[] path;
}


        深度优先搜索,使用DFS(char** maze, int row, int col, bool** isVisited, int* path, int currX, int currY, int currStep)函数实现。其中 maze/row/col 为固定不变的迷宫信息, isVisited记录到目前位置经过的位置, path记录了到目前位置的游走路径,currX/currY记录当前的位置,currStep记录到目前位置走了多少步

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// N (-1,  0)
// S ( 1,  0)
// W ( 0, -1)
// E ( 0,  1)
int direction[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}
};void DFS(char** maze, int row, int col, bool** isVisited, int* path, int currX, int currY, int currStep)
{// 判断是否到达目标位置(row - 1, col - 1), 找到一个方案,输出该方案if (currX == (row - 1) && currY == (col - 1)) {for(int k = 0; k < currStep; k++) {switch(path[k]) {case 0: printf("N"); break;case 1: printf("S"); break;case 2: printf("W"); break;case 3: printf("E"); break;}}printf("\n");return;}// 如果没有到达目的地, 继续搜索: 尝试从当前位置 (currX, currY) 出发, 沿着四个方向走for (int k = 0; k < 4; k++) {// 计算沿着该方向走下去的新位置 (nextX, nextY)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]) {// 没有走过的新位置,做标记,准备优先走下去 (深度优先)// 1. 标记isVisited[nextX][nextY] = 1;path[currStep] = k;// 2. 继续搜索DFS(maze, row, col, isVisited, path, nextX, nextY, currStep + 1);// 3. 回溯,搜索完(nextX, nextY)开始的情况后,又回到节点(currX, currY), 继续下一个方向 (需要恢复,清除之前的标记)isVisited[nextX][nextY] = 0;}}}
}


        到此, 我们完成了使用深度优先搜索寻找迷宫答案:

row=3, col=4
...#
.#.#
....
SSEEE
EESSErow=6, col=8
.#######
.......#
.##.##.#
....#.##
#.######
#.......
SSSESSEEEEEE
SEEESSWWSSEEEEEE



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



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

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)