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

缺乏、安全感 2023-10-09 20:52 22阅读 0赞

![在这里插入图片描述][158b43a01a0948759d41fff0761dc19a.png]

================================  
专栏文章，自下而上  
[数据结构与算法——二叉搜索树][Link 1]  
[数据结构与算法——深度寻路算法][Link 2]  
[数据结构与算法——二叉树+实现表达式树][Link 3]  
[数据结构与算法——树(三指针描述一棵树）][Link 4]  
[数据结构与算法——栈和队列＜也不过如此＞][Link 5]  
[数据结构与算法——八大经典排序算法详解][Link 6]  
[数据结构与算法——有头无头循环链表详解][Link 7]  
[数据结构与算法——顺序表][Link 8]

================================  
![在这里插入图片描述][1b615417ceb84c3b8e2d984db0807f24.gif_pic_center]

#### 文章目录 ####

*   *   *  1、介绍
         *  2、思想
         *  3、定义及快捷
         *  4、创建四叉树节点
         *  5、判断能不能走
         *  6、准备工作
         *  7、寻路
         *   *  A、标记走过
             *  B、对预测点进行移动处理
             *  C、能走的情况下怎么处理
             *  D、切换层数
         *  8、效果展示
         *  9、综合代码
         *  10、总结

--------------------

#### 1、介绍 ####

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

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

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

#### 2、思想 ####

![在这里插入图片描述][c346eeb45c4849b3b7c1832c837a94ea.png_pic_center]

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

> 可能有的同学会问了，那要怎么实现呐，每次都要派四个小兵，而且有的不是障碍物的要一直寻路下去，这个时候我们就想到了四叉树来实现，把起点放入根节点，一层就代表一步
> 
> **有的同学又会问了，那如果一张地图有很多条路径，那广度寻路怎么会找到最短的那一条路径？**
> 
> 其实思想很简单，就是一找到终点就结束循环，从终点往上遍历，这条路径一定是最短路径——因为这条路径是最先结束循环，即最先找到终点

#### 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、效果展示 ####

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

![在这里插入图片描述][d87d5c11353d4e8e8817c2b9da386c70.png_pic_center]

#### 9、综合代码 ####

**需要源代码的私信我~**

![在这里插入图片描述][d271a4e12e4d425590c0dc75cd3325c6.png]

#### 10、总结 ####

> **总结：**  
> 深度适合大地图 开阔地形  
> 例如 走迷宫 开宝箱  
> 广度适合小地图  
> 回合制游戏 走格子

[158b43a01a0948759d41fff0761dc19a.png]: https://img-blog.csdnimg.cn/158b43a01a0948759d41fff0761dc19a.png
[Link 1]: https://blog.csdn.net/qq_72157449/article/details/130439985
[Link 2]: https://blog.csdn.net/qq_72157449/article/details/129766874
[Link 3]: https://blog.csdn.net/qq_72157449/article/details/129700648
[Link 4]: https://blog.csdn.net/qq_72157449/article/details/129628960
[Link 5]: https://blog.csdn.net/qq_72157449/article/details/129624459
[Link 6]: https://blog.csdn.net/qq_72157449/article/details/129104981
[Link 7]: https://blog.csdn.net/qq_72157449/article/details/128754708
[Link 8]: https://blog.csdn.net/qq_72157449/article/details/128743508
[1b615417ceb84c3b8e2d984db0807f24.gif_pic_center]: https://img-blog.csdnimg.cn/1b615417ceb84c3b8e2d984db0807f24.gif#pic_center
[c346eeb45c4849b3b7c1832c837a94ea.png_pic_center]: https://img-blog.csdnimg.cn/c346eeb45c4849b3b7c1832c837a94ea.png#pic_center
[d87d5c11353d4e8e8817c2b9da386c70.png_pic_center]: https://img-blog.csdnimg.cn/d87d5c11353d4e8e8817c2b9da386c70.png#pic_center
[d271a4e12e4d425590c0dc75cd3325c6.png]: https://img-blog.csdnimg.cn/d271a4e12e4d425590c0dc75cd3325c6.png