“ 探索迷局:解密广度寻路算法 “

这篇具有很好参考价值的文章主要介绍了“ 探索迷局:解密广度寻路算法 “。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

“ 探索迷局:解密广度寻路算法 “

================================
专栏文章,自下而上
数据结构与算法——二叉搜索树
数据结构与算法——深度寻路算法
数据结构与算法——二叉树+实现表达式树
数据结构与算法——树(三指针描述一棵树)
数据结构与算法——栈和队列<也不过如此>
数据结构与算法——八大经典排序算法详解
数据结构与算法——有头无头循环链表详解
数据结构与算法——顺序表

================================
“ 探索迷局:解密广度寻路算法 “


1、介绍

广度寻路算法是一种基于图的搜索算法,用于寻找两个节点之间的最短路径。它从起点开始展开搜索,并逐步向外扩展,直到找到目标节点或所有节点都被访问过。广度寻路算法使用队列作为辅助数据结构来实现搜索。当一个节点被访问时,将其所有的邻居节点加入队列中,并标记为已访问。从队列中取出的节点继续进行扩展搜索,直到队列为空或目标节点被找到为止。广度寻路算法的时间复杂度为O(V+E),其中V为节点数,E为边数。由于它逐层扩展搜索,因此能够找到最短路径,但会占用较多的空间。需要源代码的私信我~

深度寻路算法:1.循环试探,遇到死胡同回退 2.循环 简单 3.不一定能找到最佳路径 4.空旷地形 深度寻路

广度寻路算法:
1. 不需要回退
2. 一定能找到最短路径

2、思想

“ 探索迷局:解密广度寻路算法 “

深度寻路就好比猴哥的毫毛一样,直接派四个小兵分别去上下左右四个方位寻找,到达下一个位置时,再派四个小兵出去寻找(当然如果有的方向是障碍物,那就不用派人去了),就这样一直下去,最后会找到终点的,而且是最短路径(后面会解释为什么)

可能有的同学会问了,那要怎么实现呐,每次都要派四个小兵,而且有的不是障碍物的要一直寻路下去,这个时候我们就想到了四叉树来实现,把起点放入根节点,一层就代表一步

有的同学又会问了,那如果一张地图有很多条路径,那广度寻路怎么会找到最短的那一条路径?

其实思想很简单,就是一找到终点就结束循环,从终点往上遍历,这条路径一定是最短路径——因为这条路径是最先结束循环,即最先找到终点

3、定义及快捷

在开始写之前我们先把准备工作写好,比如行和列的定义,最大孩子的数量,因为是试探4个方向,所以最大孩子的数量为4,且这里定义的是四叉树,存储当前层和下一层节点地址的数组大小,地图中路和障碍物的枚举,上下左右方向的枚举,还要定义一个点类型,以及四叉树类型,四叉树中需要定义结构体数组,因为有四个孩子,还有一个重要的是定义当前孩子的数量,因为不仅父亲要指向孩子,孩子也还要指向父亲,因为最后确定最佳路径,还要从终点往上遍历

//行列
#define ROWS 10
#define COLS 10
//最大孩子数量
#define CHILD_NUM 4
//临时数组的最大容量
#define BUFF_SIZE 100
//地图枚举
enum Mymap{road,wall};
//方向枚举
enum Mydirect{p_up,p_left,p_down,p_right};
//点
typedef struct Mypoint 
{
	int row, col;
}Mypoint;
//四叉树节点类型
typedef struct myThree 
{
	Mypoint			pos;
	struct myThree* partent;
	struct myThree* Child[CHILD_NUM];
	int				Curchild_Num;  
}myThree;
#define SIZE sizeof(myThree)

4、创建四叉树节点

这里先是直接用快捷的方式,把四叉树中都初始化为0,然后再赋值点的坐标

myThree* createThreeNode(Mypoint* pos)
{
	myThree* pNew = malloc(SIZE);
	assert(pNew);
	memset(pNew, 0, SIZE);
	pNew->pos.row = pos->row;
	pNew->pos.col = pos->col;
	return pNew;
}

5、判断能不能走

当前点越界,以及辅助地图上标记过的点,是墙都不能走

bool can_Walk(Mypoint* pos, bool map[ROWS][COLS], bool pathMap[ROWS][COLS])
{
	//越界
	if (pos->row < 0 || pos->row >= ROWS || pos->col < 0 || pos->col >= COLS) 		return false;
	//走过
	if (pathMap[pos->row][pos->col]) return false;
	//是墙
	if (map[pos->row][pos->col]) return false;
	return true;
}

6、准备工作

1、简单用数组实现一个二维地图,用于寻路

2、定义起点和终点

3、定义辅助地图,用于标记有没有走过

4、定义两个辅助数组,用来在当前层和下一层之间切换,这两个数组分别是用来存储当前层和下一层节点的地址

5、创建一棵树,起点成为树根,并且根节点还有独占一层

6、准备一个预测点

7、定义isFindend,用来判断是否找到终点,因为寻找的过程是多层循环,一个break结束不了循环,所以定义了一个标记

	//1 地图  1表示障碍  0表示路
	bool map[ROWS][COLS] = 
	{
		{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
		{ 1, 0, 1, 1, 0, 0, 0, 1, 1, 1 },
		{ 1, 0, 1, 1, 0, 1, 0, 1, 1, 1 },
		{ 1, 0, 1, 1, 0, 1, 0, 0, 0, 1 },
		{ 1, 0, 1, 1, 0, 1, 1, 0, 1, 1 },
		{ 1, 0, 0, 0, 0, 0, 0, 0, 1, 1 },
		{ 1, 0, 1, 1, 1, 1, 1, 0, 1, 1 },
		{ 1, 0, 1, 1, 0, 0, 0, 0, 0, 1 },
		{ 1, 0, 1, 0, 0, 1, 1, 1, 0, 1 },
		{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
	};

	//点--起点和终点
	Mypoint begPos = { 1,1 };
	Mypoint endPos = { 8,8 };

	//辅助地图
	bool pathMap[ROWS][COLS] = { 0 };

	//创建一颗树
	myThree* pRoot = NULL;
	//起点成为树根
	pRoot = createThreeNode(&begPos);

	//辅助数组
	//记录当前层节点的地址
	myThree* currentLayer[BUFF_SIZE] = { 0 };
	// 当前层节点的数量
	int currentLayerSize = 0;
	//记录下一层节点的地址
	myThree* nextLayer[BUFF_SIZE] = { 0 };
	//下一层节点的数量
	int nextLayerSize = 0;

	//树的根节点独占一层
	currentLayer[currentLayerSize++] = pRoot;
	
	//预测点
	Mypoint search;
	
	//标记是否走到终点
	bool isFindend = false;
	
	//准备一个临时变量
	myThree* temp_Node = NULL;

7、寻路

寻路的思想前面已经讲过了,我们一层一层的遍历(即一步一步的遍历),然后对每一步的四个方向进行处理

A、标记走过

处理之前,我们还要标记当前点已经走过并且要把当前的孩子数量清空

//标记走过
pathMap[currentLayer[i]->pos.row][currentLayer[i]->pos.col] = true;
//孩子数量清空
currentLayer[i]->Curchild_Num = 0;
B、对预测点进行移动处理

预测点就是当前的点,然后用switch进行处理

//预测点就是当前点
search.row = currentLayer[i]->pos.row;
search.col = currentLayer[i]->pos.col;
switch(j)
{
	case p_up:  search.row--;  break;
	case p_down:  search.row++;  break;
	case p_left:  search.col--;  break;
	case p_right:  search.col++;  break;
}
C、能走的情况下怎么处理

能走的情况下当前点就要成为预测点的父节点,预测点还要成为当前点的孩子,除此之外还要把预测点放入下一层数组中,因为它的身份是预测点,即为当前点的孩子,最后还要判断是否到达终点

//能走
if (can_Walk(&search,map,pathMap))
{
	//创建树节点
	temp_Node = createThreeNode(&search);
	//预测点成为当前点的孩子
	currentLayer[i]->Child[currentLayer[i]->Curchild_Num++] = temp_Node;
	//当前点成为预测点的父亲
	temp_Node->partent = currentLayer[i];
	//放入下一层数组中
	nextLayer[nextLayerSize++] = temp_Node;
	//判断是否到达终点
	if (temp_Node->pos.row==endPos.row&& temp_Node->pos.col == endPos.col)
	{
		isFindend = true;
		break;
	}
}
D、切换层数

如果下一层的数组为空,这时候已经遍历到最后一层了,直接退出,否则切换到下一层

//下一层为空
if (nextLayerSize == 0) break;
//切换到下一层中
for (int i = 0; i < nextLayerSize; i++)
{
	currentLayer[i] = nextLayer[i];
}
currentLayerSize = nextLayerSize;

8、效果展示

明显看出,这是一条最短路径

“ 探索迷局:解密广度寻路算法 “

9、综合代码

需要源代码的私信我~

“ 探索迷局:解密广度寻路算法 “

10、总结

总结:
深度适合大地图 开阔地形
例如 走迷宫 开宝箱
广度适合小地图
回合制游戏 走格子文章来源地址https://www.toymoban.com/news/detail-443534.html

到了这里,关于“ 探索迷局:解密广度寻路算法 “的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 保护数据隐私:深入探索Golang中的SM4加密解密算法

    最近做的项目对安全性要求比较高,特别强调: 系统不能涉及MD5、SHA1、RSA1024、DES高风险算法。 那用什么嘞?甲方: 建议用国产密码算法SM4。 擅长敏捷开发(CV大法)的我,先去GitHub找了开源项目、又去网络上找了一些教程,但是或多或少都有些问题: 比如 golang.org/x/cryp

    2024年02月10日
    浏览(94)
  • 掌握Go语言:Go语言递归函数,解密编程之谜,探索算法的奥秘!(27)

    递归函数是指在函数内部调用自身的函数。在Go语言中,递归函数使用起来非常方便,但需要注意递归的终止条件,以避免无限循环。 Go语言递归函数的使用方法 在Go语言中,编写递归函数的基本步骤如下: 上述三点内容详细解释如下: 定义一个函数,函数内部调用自身 :

    2024年04月15日
    浏览(50)
  • Redis 专栏、JVM 专栏、RocketMQ 专栏、ZooKeeper 专栏文章导读

    欢迎关注公众号(通过文章导读关注:【11来了】),及时收到 AI 前沿项目工具及新技术 的推送 发送 资料 可领取 深入理解 Redis 系列文章结合电商场景讲解 Redis 使用场景 、 中间件系列笔记 和 编程高频电子书 ! 文章导读地址:点击查看文章导读! 感谢你的关注! 下边这

    2024年02月02日
    浏览(37)
  • wireshark专栏——解密加密报文

    示例抓包文件解密参数: snmpUser=“ABC” authenType=“SHA” authenPass=“ABC123” priType=“AES” priPass=“ABC123” 备注:这些参数是SNMPv3读取mib节点时设置的参数 我们看到加密报文把报文中携带的数据信息给加密了:encryptedPDU:privKey Unkown 根据设备中设置的加密参数输入对应的位置 报

    2024年01月19日
    浏览(37)
  • 专栏文章列表

    1.1 语言基础 C++中的static和extern 异常处理 将成员函数作为函数形参 自增和自减运算符的重载 C++中sort对类对象进行排序 c++的lambda表达式 1.2 进阶 智能指针 默认构造函数和拷贝构造函数的构造操作 list中的sort()函数 1.3 其他 lua如何调用C/C++ 教你三步搞定VsCode调试C++ 2.1

    2024年02月07日
    浏览(42)
  • 【网络安全 -> 防御与保护】专栏文章索引

    为了方便 快速定位 和 便于文章间的相互引用等 作为一个快速准确的导航工具 网络安全——防御与保护 (一).信息安全概述 (二).防火墙组网

    2024年01月23日
    浏览(39)
  • Python案例——采集专栏文章保存成pdf

    前言 嗨喽,大家好呀~这里是爱看美女的茜茜呐 环境使用: python 3.8 运行代码 pycharm 2022.3 辅助敲代码 wkhtmltopdf 软件 找助理邀课老师获取 模块使用: 内置模块 re 正则表达式 第三方模块 需要安装 requests pip install requests 数据请求 parsel pip install parsel 数据解析 pdfkit pip install pdfki

    2024年02月10日
    浏览(40)
  • 【Stable Diffusion】专栏介绍和文章索引(持续更新中)

    最近开始学习AIGC,对Stable Diffusion比较感兴趣,所以新建了这个专栏,来记录自己在使用和学习Stable Diffusion的一些方法、资料以及实验过程,也和大家一起分享这些经验和心得体会,一起学习进步。 专栏地址:Stable Diffusion 本专栏会分以下几部分介绍。 入门:主要是介绍SD的

    2024年04月11日
    浏览(40)
  • 算法修养--A*寻路算法

    广度优先算法搜索以广度做为优先级进行搜索。 从起点开始,首先遍历起点周围邻近的点,然后再遍历已经遍历过的点邻近的点,逐步的向外扩散,直到找到终点。 这种算法就像洪水(Flood fill)一样向外扩张。直至洪水将整张地图都漫延。在访问节点时候,每个点需要记录

    2024年02月08日
    浏览(26)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包