(19)中华人民共和国国家知识产权局
(12)发明专利申请
(10)申请公布号 (43)申请公布日 (21)申请号 201710794646.5
(22)申请日 2017.09.06
(71)申请人 电子科技大学
地址 611731 四川省成都市高新区（西区）
西源大道2006号
(72)发明人 李海庆 龚自成 袁容 李伟
唐明哲
(74)专利代理机构 成都宏顺专利代理事务所
(普通合伙) 51227
代理人 周永宏
(51)Int.Cl.
G01C 21/20(2006.01)
(54)发明名称
(57)摘要
本发明公开了一种基于A星算法的最短寻路
人脸抓拍系统
星算法计算从初始状态到目标状态的代价估计，
通过判断起点至目标点各路径对应代价估计值
是否为最小值寻新起点，再通过判断新的起点
是否为目标点完成寻路。本发明具有直观明了，
适用性强，
可以适用各种场景寻路的优点。权利要求书1页 说明书3页 附图2页CN 107687859 A 2018.02.13
ktv点歌台C N 107687859
A
1.一种基于A星算法的最短寻路方法，其特征在于，包括以下步骤：
A、将搜索区域划分为多个网格，确定起点、目标点及障碍点所在网格，将起点放入开启列表中；
B、搜索起点所在网格相邻的网格，计算相邻的网格点与目标点的距离；
C、将网格对应的点作为状态空间中的状态，点之间的距离作为代价，采用A星算法计算从初始状态到目标状态的代价估计；
D、比较起点至目标点各路径对应代价估计值大小，依次判断起点至目标点各路径对应代价估计值是否为最小值；若是，则将起点放入关闭列表，同时将起点所在网格相邻的网格点作为新的起点，将新的起点放入开启列表中；若否，则将起点至目标点的该路径对应的相邻网格点放入关闭列表，重新选择下一条起点至目标点的路径；
E、判断新的起点是否为目标点；若是，则寻路结束；若否，则返回步骤B。
2.如权利要求1所述的基于A星算法的最短寻路方法，其特征在于，所述步骤A中将搜索区域划分为多个网格具体为将搜索区域划分为M*N的方格区域。
3.如权利要求1所述的基于A星算法的最短寻路方法，其特征在于，所述步骤C将网格对应的点作为状
态空间中的状态，点之间的距离作为代价，采用A星算法计算从初始状态到目标状态的代价估计的计算公式为
F＝G+H
其中，F为从初始状态到目标状态的代价估计，G为从初始状态到下一状态的代价，H为下一状态到目标状态的最佳路径的代价。
权 利 要 求 书1/1页CN 107687859 A干粉砂浆
基于A星算法的最短寻路方法
技术领域
[0001]本发明属于寻路算法技术领域，尤其涉及一种基于A星算法的最短寻路方法。
背景技术
[0002]普通教科书上的寻路算法往往只应用在数学意义上的“图”上，即由顶点集合和边集合互相连接组成的结构。因此我们需要将一个栅格化的游戏地图转化为一个“图”：地图上的每一格可以作为一个顶
一次性餐具环保点，而相邻的格子则各有一条边，此例中只考虑二维网格。[0003]大部分在AI和算法领域的寻路算法都是针对作为数学结构的“图”本身，而并非针对这种网格化游戏地图。我们希望寻一种能利用游戏地图自身特征的方法。其实有些在二维网格图中我们认为是常识的事情，一些在普通图上使用的寻路算法本身可能并没有考虑到，例如如果两个物体距离较远，那么可能从一个物体到另一个物体的移动的时间和路径会较长。对于方向来说，如果方向是朝东，那么最优路径的路径也应当是大体往东走，而不是向西去。在网格中还可以从对称中获取信息，即先向北再向西，大部分情况下和先向西再向北等价。这些额外的信息可以让寻路算法更加快速。
[0004]Dijkstra算法简单说来，就是从起始点访问其他临近节点，并将该节点加入待检查节点集合中，使用松弛算法更新待检查节点的路径长度值。只要图不存在负权值的边，Dijkstra算法能够确保到最短路径。
[0005]贪心最好优先搜索算法大体与之类似，不同的是该算法对目标点的距离有一个估计值(启发值)。该算法并不在待检查节点集合中选取距离起始点近的节点进行下一步的计算，而是选择距离目标点近的节点。贪心最好优先搜索算法并不能保证寻到最优路径，然而却能大大提高寻路速度，因为它使用了启发式方法引导了路径的走向。相比于Dijkstra 算法，贪心最好优先算法能够更加快速地寻路。但贪心最好优先算法虽然做了较少的计算，但却并不能到一条较好的路径。
发明内容
[0006]本发明的发明目的是：为了解决现有技术中存在的以上问题，本发明提出了一种基于A星算法的最短寻路方法。假牙清洁剂
[0007]本发明的技术方案是：一种基于A星算法的最短寻路方法，包括以下步骤：[0008]A、将搜索区域划分为多个网格，确定起点、目标点及障碍点所在网格，将起点放入开启列表中；
[0009]B、搜索起点所在网格相邻的网格，计算相邻的网格点与目标点的距离；
[0010]C、将网格对应的点作为状态空间中的状态，点之间的距离作为代价，采用A星算法计算从初始状态到目标状态的代价估计；
[0011]D、比较起点至目标点各路径对应代价估计值大小，依次判断起点至目标点各路径对应代价估计值是否为最小值；若是，则将起点放入关闭列表，同时将起点所在网格相邻的网格点作为新的起点，将新的起点放入开启列表中；若否，则将起点至目标点的该路径对应
的相邻网格点放入关闭列表，重新选择下一条起点至目标点的路径；
[0012]E、判断新的起点是否为目标点；若是，则寻路结束；若否，则返回步骤B。
[0013]进一步地，所述步骤A中将搜索区域划分为多个网格具体为将搜索区域划分为M*N 的方格区域。
[0014]进一步地，所述步骤C将网格对应的点作为状态空间中的状态，点之间的距离作为代价，采用A星算法计算从初始状态到目标状态的代价估计的计算公式为
[0015]F＝G+H
[0016]其中，F为从初始状态到目标状态的代价估计，G为从初始状态到下一状态的代价，H为下一状态到目标状态的最佳路径的代价。
[0017]本发明的有益效果是：本发明采用A星算法，不断更新起点位置，可以直接搜寻最佳路线，在有障碍物的情况下也可以完成最佳路线搜寻；此外，还可以对实际问题进行扩展，在障碍物位置发生变化时也可以完成最佳路线搜寻，具有直观明了，适用性强，可以适用各种场景寻路的优点。
附图说明
[0018]图1是本发明的基于A星算法的最短寻路方法的流程示意图。
[0019]图2是本发明实施例中的区域场景示意图。
具体实施方式
[0020]为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。
[0021]如图1所示，为本发明的基于A星算法的最短寻路方法的流程示意图。一种基于A星算法的最短寻路方法，包括以下步骤：
[0022]A、将搜索区域划分为多个网格，确定起点、目标点及障碍点所在网格，将起点放入开启列表中；
[0023]B、搜索起点所在网格相邻的网格，计算相邻的网格点与目标点的距离；
[0024]C、将网格对应的点作为状态空间中的状态，点之间的距离作为代价，采用A星算法计算从初始状态到目标状态的代价估计；
[0025]D、比较起点至目标点各路径对应代价估计值大小，依次判断起点至目标点各路径对应代价估计值是否为最小值；若是，则将起点放入关闭列表，同时将起点所在网格相邻的网格点作为新的起点，将新的起点放入开启列表中；若否，则将起点至目标点的该路径对应的相邻网格点放入关闭列表，重新选择下一条起点至目标点的路径；
[0026]E、判断新的起点是否为目标点；若是，则寻路结束；若否，则返回步骤B。
[0027]在步骤A中，本发明将搜索区域划分为多个网格，具体为将搜索区域划分为M*N的方格区域；同时，标注出其中起点、目标点及无法通行的障碍点所在的网格；并且将起点放入开启列表中。
[0028]在步骤B中，本发明根据开启列表中的起点，搜索该起点所在网格相邻的网格，这里相邻的网格为起点所在网格上下左右方向的网格，起点通过与其相邻的网格进行上下左
右移动；根据起点的移动路径计算起点相邻的网格点与目标点的距离。
[0029]在步骤C中，本发明采用A星算法，将网格对应的点作为状态空间中的状态，点之间的距离作为代价，计算从初始状态到目标状态的代价估计，计算公式为
[0030]F＝G+H
[0031]其中，F为从初始状态到目标状态的代价估计，即起点与目标点的距离；G为从初始状态到下一状态的代价，即起点与相邻的网格点的距离；H为下一状态到目标状态的最佳路径的代价，即相邻的网格点与目标点的距离。
[0032]在步骤D中，本发明比较起点至目标点各路径对应代价估计值大小，然后依次选取一条起点至目标点的路径，判断该条路径对应代价估计值是否为最小值；若是，则将该条路径的起点放入关闭列表，同时将起点所在网格相邻的网格点作为新的起点，将新的起点放入开启列表中；若否，则将起点
euht终端至目标点的该路径对应的相邻网格点放入关闭列表，重新选择下一条起点至目标点的路径，直到遍历完起点至目标点的所有路径。
[0033]在步骤E中，本发明通过判断新的起点是否为目标点来确定是否完成最短寻路；若是，则说明已完成最短寻路，寻路结束；若否，则说明未完成最短寻路，返回步骤B，搜索新的起点所在网格相邻的网格。
[0034]如图2所示，为本发明实施例中的区域场景示意图。本发明将搜索区域划分为5*3的方格区域，障碍物为1*1的方格区域，起点的位置坐标定为(2,2)，目标点的坐标定为(3, 5)，障碍物的坐标定为(2,4)，搜索起点所在网格相邻的网格点，由于只能进行上下左右移动，因此只判断B、D、E、G四个点的位置。移动一个格子代表的距离为1，因此B点G为1，H为5，F 为6；D点G为1，H为5，F为6；E点G为1，H为3，F为4；G点G为1，H为3，F为4。由于目的点在区域右下角，因此排除B点和D点，将该两点放入关闭列表中，考虑E点和G点作为下一步移动点。由于E点和G点两者F相同，因此选任意一点可以进行移动，将选择的点放入开启列表中进行移动，将初始点放入关闭列表中，并再次进行判断新的移动点。针对于障碍物的点将其放入关闭列表中不予以考虑，通过多次重复迭代最终到目标点，此时可以得到最优寻路路线。[0035]本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。本领域的普通技术人员可以根据本发明公开的这些技术启示做出各种不脱离本发明实质的其它各种具
体变形和组合，这些变形和组合仍然在本发明的保护范围内。
