推荐蜂巢迷宫最短路径计算方法及蜂巢迷宫实训系统与流程

将乐信息网 http://www.jianglexinxi.cn 2020-10-18 13:05 出处:网络
这里写的推荐蜂巢迷宫最短路径计算方法及蜂巢迷宫实训系统与流程,小编为您一一讲解!

这里写的推荐蜂巢迷宫最短路径计算方法及蜂巢迷宫实训系统与流程,小编为您一一讲解!


本发明涉及教育实训技术领域,特别涉及一种蜂巢迷宫最短路径计算方法及蜂巢迷宫实训系统。



背景技术:

编程教育是通过编程游戏启蒙、可视化图形编程等课程,培养学生的计算思维和创新解难能力的课程。最短路径计算是让学生在已有地图上寻找两点间的最短路径,是一种启发学生逻辑思维能力的经典课程。最短路径算法不仅在解决路径搜索相关的应用中十分普遍,包括网络路由算法、机器人探路、人工智能、游戏设计等,而且在交通路线导航、路径分析领域应用更加广泛。常用的最短路径搜索算法有dijkstra(迪杰斯特拉算法),a-star算法,但是目前主流的单片机的ram都在64k以下,想要运行以上这些最短路径算法均有一定难度。



技术实现要素:

本发明要解决的技术问题是如何提供一种可应用在低硬件配置环境下的蜂巢迷宫最短路径计算方法及蜂巢迷宫实训系统。

为了解决上述技术问题,本发明的技术方案为:

一方面,本发明提出了一种蜂巢迷宫最短路径计算方法,包括步骤:

将蜂巢形迷宫的每个节点作为一个单元结构体,单元结构体的属性包括单元坐标、邻结点的指针、单位结点权值、邻结点的数量;将每个节点相邻的所有节点进行编号,将相邻节点的指针存入该节点的单元结构体中;

读取节点和边的数据并以邻接矩阵形式存储,并统计出节点个数和边的条数;邻接矩阵中的元素为n和max两种,n表示直接有边相连的权值,max表示无边直接相连;

在邻接矩阵的运算过程中,每个结点遍历完邻结点后其余连接点均设为max;

获取起始节点、终点节点及各中间节点的节点信息,通过迪杰斯特拉算法计算经过各中间节点的起始点至终点的最短距离。

优选地,还包括步骤:从网络图中删去目标路径不经过的节点。

优选地,从网络图中删去目标路径不经过的节点的步骤为:从起点出发,深度遍历网络图,将没有遍历到的节点从原网络图中删除,生成新的网络图用以替换原网络图。

优选地,在将每个邻节点的指针存入单元数据组中之前,还包括:

当一节点的单元坐标位置处在网络图的区域范围外,则删除该节点。

另一方面,本发明还提出一种蜂巢迷宫实训系统,包括:

多个正六边形的蜂巢单元,所述蜂巢单元设有一用于设置起点和终点的按钮,以及六条分别与六条边连通的用于感应相邻结点是否连接的电桥,六条电桥之间相互连通;

主控设备,所述主控设备与各所述蜂巢单元通信连接,所述主控设备可执行如上所述的蜂巢迷宫最短路径计算方法。

优选地,每个所述蜂巢单元上都设有受所述主控设备控制的信号灯。

优选地,所述主控设备包括stm32系列的控制芯片。

采用上述技术方案,通过多个蜂巢单元排布成所需的地图,并通过主控设备对各个蜂巢单元实现控制。并在主控设备进行地图构建、优化邻接矩阵、最短距离计算等步骤。采用本算法能够在低配置,特别是低ram的设备及单片机上有效的执行通过指定节点的最短路径算法。采用本实训系统,可以随意构建地形,减少故障率,通过让学生在游戏中探索和发现激发学生对科学技术的兴趣。

附图说明

图1为本发明蜂巢迷宫最短路径计算方法一实施例的步骤流程图;

图2为本发明一节点的邻节点编号示意图;

图3为本发明中一邻接矩阵示意图;

图4为本发明蜂巢迷宫实训系统的蜂巢单元结构示意图;

图5为本发明蜂巢迷宫实训系统的迷宫结构示意图。

具体实施方式

下面结合附图对本发明的具体实施方式作进一步说明。在此需要说明的是,对于这些实施方式的说明用于帮助理解本发明,但并不构成对本发明的限定。此外,下面所描述的本发明各个实施方式中所涉及的技术特征只要彼此之间未构成冲突就可以相互组合。

第一方面,参照图1,本发明提出了一种蜂巢迷宫最短路径计算方法,包括步骤:

s10:将蜂巢形迷宫的每个节点作为一个单元结构体,单元结构体的属性包括单元坐标、邻结点的指针、单位结点权值、邻结点数量;将每个节点相邻的所有节点进行编号,将相邻节点的指针存入该节点的单元结构体中;

s20:读取节点和边的数据并以邻接矩阵形式存储,并统计出节点个数和边的条数;邻接矩阵中的元素为n和max两种,n表示直接有边相连的权值,max表示无边直接相连,其中max为一个事先定义的足够大的数字;

s30:在邻接矩阵运算过程中,每个结点遍历完邻结点后其余连接点均设为max;

s40:获取起始节点、终点节点及各中间节点的节点信息;通过迪杰斯特拉算法计算经过这些中间节点的起始点至终点的最短距离。

具体地,还包括步骤:从网络图中删去目标路径不经过的节点。此外,还需从网络图中删去目标路径已经经过的节点,避免重复计算。

具体地,从网络图中删去目标路径不经过的节点的步骤为:从起点出发,深度遍历网络图,将没有遍历到的节点从原网络图中删除,生成新的网络图用以替换原网络图。

具体地,在将每个邻节点的指针存入单元数据组中之前,还包括:当一节点的单元坐标位置处在网络图的区域范围外,则删除该节点。

第二方面,本发明还提出了一种蜂巢迷宫实训系统,包括:

多个正六边形的蜂巢单元,蜂巢单元设有一用于配置起点和终点的按钮,以及六条分别与六条边连通的用于感应相邻结点是否连接的电桥,六条电桥之间相互连通;使用时,通过按压按钮,将蜂巢单元设定为起点或者终点。

主控设备,主控设备与各蜂巢单元通信连接,主控设备可执行上述的蜂巢迷宫最短路径计算方法。

具体地,每个蜂巢单元上都设有受主控设备控制的信号灯。通过信号灯从视觉上来提示用户起点和终点的所在,便于实训教学中使用。

具体地,主控设备包括stm32系列的控制芯片。需要说明的是,本发明中,还可以使用其他满足性能要求的控制芯片来实现主控设备的功能。

采用上述技术方案,由通过多个蜂巢单元排布成所需的地图,并通过主控设备对各个蜂巢单元实现控制。通过在主控设备进行地图构建、优化邻接矩阵、最短距离计算等步骤。采用本算法能够在低配置,特别是低ram的设备及单片机上有效的执行通过指定节点的最短路径算法。采用本实训系统,可以随意构建地形,减少故障率,通过让学生在游戏中探索和发现激发学生对科学技术的兴趣。

参照图5,为解决以上技术问题,本发明另一实施例中提出以下技术方案:

地图的构建。初始化迷宫结构,蜂巢形迷宫的特点主要在于每个结点有六个邻结点,因此路径的密度大于以四边形为单位的迷宫,不仅要考虑路径的计算,也要考虑移动算法,因此需要构建一个全面的结点类以方便地图布局和后面的计算。首先构建一个类cell用于初始化迷宫单位结点。cell的主要属性有:

对象position{x,y}用于存储单位结点的坐标,该对象用于地图的布局。

数组neighbor[]存放指向邻结点的指针。

变量quanzhi_用来存储单位结点的权值。

以及变量neighborsnum_用来存储单位结点的邻结点的数量。为了便于计算邻结点,在本算法中采用长度为n×m的一维数组celllist[n×m]存放迷宫结点。

构造邻结点,如图2所示,将每一个结点的邻结点进行编号。如图5所示,在构建地图过程中,左边界结点会缺失2号邻结点,右边界会缺失3号邻结点。当前结点的位置为cell的position{x,y},偶数行时0号邻结点position{x,y-1},1号邻结点position{x+1,y-1},2号邻结点position{x+1,y},3号邻结点position{x+1,y+1},4号邻结点position{x,y+1},5号邻结点position{x-1,y},当奇数行时0号邻结点position{x-1,y-1},1号邻结点position{x,y-1},2号邻结点position{x+1,y},3号邻结点position{x,y+1},4号邻结点position{x-1,y+1},5号邻结点position{x-1,y}。当position满足if(!(x<0||y<0||x>cols-1||y>rows-1))时则将相应位置的结点指针放入neighbor中。

点和边的数据提取,从文件中读取节点和边的数据并以邻接矩阵形式存储,同时统计出节点个数和边的条数。如图3所示,邻接矩阵中的元素只有n和max两种,n表示直接有边相连的权值,max表示无边直接相连。max为一个事先定义的足够大的数字。

从原网络图中删去目标路径肯定不会经过的节点,进行剪枝。具体方法为,从起点出发,深度优先遍历该图,那些没有遍历到的节点肯定不会出现在目标路径上,就可以将它们从原网络图中“剪”掉。从而生成新的网络图,替换原来的网络图。剪枝的目的是在不影响求目标路径的情况下,通过减少网络中节点个数,来大幅提高算法的时空效率。

优化邻接矩阵,由于每个cell最多有6个邻结点,当地图增大时邻接矩阵会存在大量的max值占用空间大。因此在邻接矩阵运算过程中每个结点遍历完自己的邻结点后其余连接点均为max。

本发明实施例中使用的最短路径算法为:

(1)假设需要经过的指定中间节点个数为n,先判断这n个节点之间的连通情况,若有任意俩节点不连通,则满足条件的路径不存在;反之,进入下一步。判断是否连通的方法:在这n个节点中,任选一个为根节点,深度优先遍历该图,若其他的n-1个所有节点都遍历到了,则是连通的;反之,则为未连通的。

(2)对这n个中间节点做全排列,生成一个中间节点序列。全排列的起点记为v1,终点记为vn。计算v1和vn之间的最短距离和路径。具体方法,见“求中间节点之间的距离和路径的方法”。

(3)求目标源点到v1的局部最短路径,即为单源点最短路径,直接使用迪杰斯特拉算法即可。若目标源点和v1之间的路径经过了自由节点,则将经过的自由节点按序保存到该局部路径中。

(4)求v1到vn的经过所有中间节点的局部最短路径,(2)中已求出。

(5)求vn到目标终点的局部最短路径,即为单源点最短路径,直接使用迪杰斯特拉算法即可。若vn和目标终点之间的路径经过了自由节点,则将经过的自由节点按序保存到该局部路径中。

(6)将以上3条路径依序连接起来即得经过smid中所有节点的(待选)全程最短路径。将以上3条路径的距离相加即得该条待选全程最短路径的距离。

(7)搜索(6)中求出的路径,其中距离最小的即为待求的全程最短距离,对应的路径就是待求的最短路径。

本发明实施例中的蜂巢迷宫实训系统包括蜂巢单元及主控设备。蜂巢单元用来构建蜂巢迷宫结构,通过电信号将场地信息传输给主控设备,主控设备调用设备上预装的算法求解最短路径及途径结点并将结果返回到各个蜂巢单元,若为最短路径上的结点则亮起。

蜂巢单元,实际实训系统应用的是如图4所示的单元,其中中间的按钮用来配置起点和终点,其内部6条电轨用来感应相邻结点是否连接。这样做的优势是所有单元格可以随意配置和移动,已满足不同地形设计。

主控设备,本实施例中使用了st的stm32f4系列高性能微控制器,其采用了90纳米的nvm工艺和art(自适应实时存储器加速器,adaptivereal-timememoryaccelerator)。stm32f4系列可达到210dmips@168mhz。自适应实时加速器能够完全释放cortex-m4内核的性能;当cpu工作于所有允许的频率(≤168mhz)时,在闪存中运行的程序,可以达到相当于零等待周期的性能。stm32f4系列微控制器集成了单周期dsp指令和fpu(floatingpointunit,浮点单元),提升了计算能力,可以进行一些复杂的计算和控制。

本发明目的是解决在低配置单片机中无法实现蜂巢迷宫最短路径算法的问题,在低成本的硬件环境下采用高效的算法。该方法可用于各种教育实训产品中,可显著降低产品成本。

以上结合附图对本发明的实施方式作了详细说明,但本发明不限于所描述的实施方式。对于本领域的技术人员而言,在不脱离本发明原理和精神的情况下,对这些实施方式进行多种变化、修改、替换和变型,仍落入本发明的保护范围内。


技术特征:

1.一种蜂巢迷宫最短路径计算方法,其特征在于,包括步骤:

将蜂巢形迷宫的每个节点作为一个单元结构体,单元结构体的属性包括单元坐标、邻结点的指针、单位结点权值、邻结点数量;将每个节点相邻的所有节点进行编号,将相邻节点的指针存入该节点的单元结构体中;

读取节点和边的数据并以邻接矩阵形式存储,并统计出节点个数和边的条数;邻接矩阵中的元素为n和max两种,n表示直接有边相连的权值,max表示无边直接相连;

在邻接矩阵的运算过程中,每个结点遍历完邻结点后其余连接点均设为max;

获取起始节点、终点节点及各中间节点的节点信息,通过迪杰斯特拉算法计算经过各中间节点的起始点至终点的最短距离。

2.根据权利要求1所述的蜂巢迷宫最短路径计算方法,其特征在于,还包括步骤:从网络图中删去目标路径不经过的节点。

3.根据权利要求2所述的蜂巢迷宫最短路径计算方法,其特征在于,从网络图中删去目标路径不经过的节点的步骤为:从起点出发,深度遍历网络图,将没有遍历到的节点从原网络图中删除,生成新的网络图用以替换原网络图。

4.根据权利要求1所述的蜂巢迷宫最短路径计算方法,其特征在于,在将每个邻节点的指针存入单元数据组中之前,还包括:

当一节点的单元坐标位置处在网络图的区域范围外,则删除该节点。

5.一种蜂巢迷宫实训系统,其特征在于,包括:

多个正六边形的蜂巢单元,所述蜂巢单元设有一用于设置起点和终点的按钮,以及六条分别与六条边连通的用于感应相邻结点是否连接的电桥,六条电桥之间相互连通;

主控设备,所述主控设备与各所述蜂巢单元通信连接,所述主控设备可执行如权利要求1至4任一项所述的蜂巢迷宫最短路径计算方法。

6.根据权利要求5所述的蜂巢迷宫实训系统,其特征在于:每个所述蜂巢单元上都设有受所述主控设备控制的信号灯。

7.根据权利要求5所述的蜂巢迷宫实训系统,其特征在于:所述主控设备包括stm32系列的控制芯片。

技术总结
本发明公开了一种蜂巢迷宫最短路径计算方法及蜂巢迷宫实训系统,将蜂巢形迷宫的每个节点作为一个单元结构体,将每个节点相邻的所有节点进行编号,将相邻节点的指针存入该节点的单元结构体中;读取节点和边的数据并以邻接矩阵形式存储,并统计出节点个数和边的条数;在邻接矩阵运算过程中,每个结点遍历完邻结点后其余连接点均设为极大值;获取起始节点、终点节点及各中间节点的节点信息;通过迪杰斯特拉算法计算经过这些中间节点的起始点至终点的最短距离。本发明解决了在低配置单片机中无法实现蜂巢迷宫最短路径算法的问题,在低成本的硬件环境下采用高效的算法,可用于各种教育实训产品中,显著降低了产品成本。

技术研发人员:余泽凡;何学智;刘小扬;刘子炜
受保护的技术使用者:新大陆数字技术股份有限公司
技术研发日:2020.02.21
技术公布日:2020.06.26

推荐蜂巢迷宫最短路径计算方法及蜂巢迷宫实训系统与流程的相关内容如下:

本文标题:推荐蜂巢迷宫最短路径计算方法及蜂巢迷宫实训系统与流程
http://www.jianglexinxi.cn/yanergaozhi/522668.html

0

精彩评论

暂无评论...
验证码 换一张
取 消