AStar算法

什么是AStar:
是一种静态路网中求解最短路最有效的直接搜索方法,估价值跟实例值非常接近;

启发式搜索 :
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,在从这个位置进行搜索直到目标.这样可以省略大量无谓的搜索路径,提高了效率;

在启发式搜索中,对位置的估价是十分重要的.采用了不同的估价,可以有不同的效果;
(估价函数就一种规则,制定的规则不同,最后的效果也就不同)<比如寻路的格子不同,最后的效果也是不同的>


估价函数 :
从当前节点移动到 目标节点的预估费用<费用简单的说就是从起点到终点的距离>(如果放到地图上就是距离,走的路越多估价越高);这个估价就是启发式的.在寻路问题和迷宫问题中,我们通常用曼哈顿(manhattan)估价函数预估费用.

A*算法特点:
在理论上是时间最优的;
但也有缺点:它的空间增长是指数级别的;(格子越多计算的量也就越大)<优化可以使用 二叉堆 >

中心思想:
通过从起始点开始,检查相邻方格的方式,向外扩展,直到找到目标;

运用:
把一个平面分成一个个的小方格,方格分的越细,寻路就越精准;

为了更好的描述,和理解A*算法提出的两个概念(不存在于真实的场景中)


开启列表:
待检查方格的集合列表,寻找周围可以达到的点,加入到此列表中,
并保存中心点为父节点

关闭列表:列表中保存不需要再次检查的方格

路径评分:
G-当前点与起始点的距离
H-当前点与目标点的距离

F的值是G和F的和
F,G和H的评分被写在每个方格里.
如图:F被打印在中间,G在左上角.H在右上角.
<如上图>
从一个格子到相邻格子的斜线距离(以为到斜线格子的距离为跟2,所以用1.4为单位)
从一个格子到相格子的直线距离(因为格子为1,所以就以1为单位);
为了方便计算查看,都乘以10作为单位;

选择路径过程中,经过哪个方格关键是:F=G+H;

<如上图>以红色格子为例
方块的中心位置42就是估价,也就是起始点到目标的距离
左上角用G表示,也就是该格子到目标点的距离为14
右上角用H表示,也就是该格子到起始点的距离为28
红色格子右上角是62,是因为已经确定了当前红色的格子,路径是从当前红色格子到右上角的格子,所以值为62;
如果选择的不是当前红色的格子,那么就会去改变其他格子的值,也就是说每个格子的值随着你的选择进行改变
(改变成符合当前格子路径上的值).

例如:从A到B的一个解析过程

开始搜索:
1.把起始格添加到开启列表。
从A点开始查找
2.寻找起点周围所有可到达或者可通过的方格，把他们加入开启列表。
遍历A所能到达的所有方格,把他们加入开启列表中
3.从开启列表中删除点A，把它加入到一个“关闭列表”，列表中保存所有不需要再次检查的方格。
因为A已经走过,所以把A加入关闭列表中,下次在进行遍历时把A除外

继续搜索:
4把当前格子从开启列表中删除，然后添加到关闭列表中。
因为已经到达了当前格子,所以把当前格子放到关闭列表中(已经到达了,没有必要去进行遍历)
5检查所有相邻格子。跳过那些已经在关闭列表中的或者不可通过的，把他们添加进开启列表，把选中的方格作为新的方格的父节点。
当前中的格子周围有两个已经添加到开启列表中,上面三个为不可通过,也就是障碍物,所以只是新添加了左侧的两个格子;

6如果某个相邻格已经在开启列表里了，检查现在的这条路径G值是否会更低一些。

如果新的G值更低，那就把相邻方格的父节点改为目前选中的方格，重新计算F和G的值。
一旦重新选择了一个点那么就需要重新计算一下当前的费用,上面写着只计算G和F的 值,为什么呢!
原因:
每个点到目标点的距离是固定的,所以H点(又上角的点)是不需要改变的,会变化的G值仅仅是因为路经改变的原因跟起始点的距离会发生改变,
所以只需要计算G的值和F的值,其他的点也会相应的更新;
<图一>
因为选择的42,但是出现了3个相同的估价,那么我们该怎么选择呢?
<图二>
这里还有另外一个原则:那就是选择一个距离目标点最近的一个值,也就是H值最低的一个.
也就是左侧的48这个方块 ,那么就把48这个点从开启列表中删除,送进关闭列表中.
因为选择了48,新增了左侧两个点,那么跟新一下在开启列表中的当前48下面的两个点(在这里下面那两个点是没有变化的,因为42下面的也是48,所以路径的值是没有改变的);
那么继续走
当我们继续走的时候,发现遍历48所能达到的值,发现这条路径不是最优的.
为什么不是最优的呢:(因为在它的开启列表中还有一个48)
那么在他的开启列表中还有一个48的值,那么就把当前的这个48从开起列表中删除，送进关闭列表中。
我们就回到上一步,选择42下方的48;
同理，这个48也不是最优的，因为他的开启列表中还有一个48，那么我们继续选择42，右侧的这个48；
结束

起始格下方格子的父节点已 经和前面不同的。 之前它的G值是，并且指向 右上方的格子。现在它的G 值是，指向它上方的格子。 这在寻路过程中的某处发生， 当应用新路径时，G值经过 检查变得低了－于是父节点 被重新指定，G和F值被重
新计算。

根据上述的原理得到如上图所示的路径，也就是最佳路径；

总结

1把起始格添加到开启列表。
2重复如下的工作：
寻找开启列表中F值最低的格子。我们称它为当前格。
把它切换到关闭列表。
/1/对相邻的格中的每一个–> 如果它不可通过或者已经在关闭列表中，略过它。反之如下。如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
/2/如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的 G和F值。
停止，当你 把目标格添加进了关闭列表，这时候路径被找到–>没有找到目标格，开启列表已经空了。这时候，路径不存在。
3.保存路径。从目标格开始，沿着每一格的父节点移动直到回到起始格。

算法：步骤架构
<1>开启集合
<2>关闭集合
<3>添加起始点到开始集合中
<4>循环如下步骤： 当前点=开启集合中最小F_Cost的点 将当前点移出开启集合中 将当前点添加到关闭集合中
<5>如果当前点是目标点，结束查询
<6>遍历当前点的每个相邻点 如果相邻点不能访问或者相邻点在关闭集合中，跳过此相邻点 如果新路径到相邻点的距离更短，或者相邻点不在开启集合中 重新设置F_Cost 重新设置其父节点为当前点
<7>如果相邻点不在开启集合中
<8>添加相邻点到开启集合什么是AStar: 是一种静态路网中求解最短路最有效的直接搜索方法,估价值跟实例值非常接近;
启发式搜索 : 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,在从这个位置进行搜索直到目标.这样可以省略大量无谓的搜索路径,提高了效率;

在启发式搜索中,对位置的估价是十分重要的.采用了不同的估价,可以有不同的效果;
(估价函数就一种规则,制定的规则不同,最后的效果也就不同)<比如寻路的格子不同,最后的效果也是不同的>

估价函数 :从当前节点移动到 目标节点的预估费用<费用简单的说就是从起点到终点的距离>(如果放到地图上就是距离,走的路越多估价越高);这个估价就是启发式的.在寻路问题和迷宫问题中,我们通常用曼哈顿(manhattan)估价函数预估费用.

A*算法特点:在理论上是时间最优的;
但也有缺点:它的空间增长是指数级别的;(格子越多计算的量也就越大)<优化可以使用 二叉堆 >

中心思想:通过从起始点开始,检查相邻方格的方式,向外扩展,直到找到目标;

.运用
把一个平面分成一个个的小方格,方格分的越细,寻路就越精准;

为了更好的描述,和理解A*算法提出的两个概念(不存在于真实的场景中)
开启列表: 待检查方格的集合列表,寻找周围可以达到的点,加入到此列表中,
并保存中心点为父节点

关闭列表:列表中保存不需要再次检查的方格

路径评分:
G-当前点与起始点的距离
H-当前点与目标点的距离

F的值是G和F的和
F,G和H的评分被写在每个方格里.
如图:F被打印在中间,G在左上角.H在右上角.
<如上图>
从一个格子到相邻格子的斜线距离(以为到斜线格子的距离为跟2,所以用1.4为单位)
从一个格子到相格子的直线距离(因为格子为1,所以就以1为单位);
为了方便计算查看,都乘以10作为单位;

选择路径过程中,经过哪个方格关键是:F=G+H;

<如上图>以红色格子为例
方块的中心位置42就是估价,也就是起始点到目标的距离
左上角用G表示,也就是该格子到目标点的距离为14
右上角用H表示,也就是该格子到起始点的距离为28
红色格子右上角是62,是因为已经确定了当前红色的格子,路径是从当前红色格子到右上角的格子,所以值为62;
如果选择的不是当前红色的格子,那么就会去改变其他格子的值,也就是说每个格子的值随着你的选择进行改变
(改变成符合当前格子路径上的值).

例如:从A到B的一个解析过程

开始搜索:
1.把起始格添加到开启列表。
从A点开始查找
2.寻找起点周围所有可到达或者可通过的方格，把他们加入开启列表。
遍历A所能到达的所有方格,把他们加入开启列表中
3.从开启列表中删除点A，把它加入到一个“关闭列表”，列表中保存所有不需要再次检查的方格。
因为A已经走过,所以把A加入关闭列表中,下次在进行遍历时把A除外

继续搜索:
4把当前格子从开启列表中删除，然后添加到关闭列表中。
因为已经到达了当前格子,所以把当前格子放到关闭列表中(已经到达了,没有必要去进行遍历)
5检查所有相邻格子。跳过那些已经在关闭列表中的或者不可通过的，把他们添加进开启列表，把选中的方格作为新的方格的父节点。
当前中的格子周围有两个已经添加到开启列表中,上面三个为不可通过,也就是障碍物,所以只是新添加了左侧的两个格子;

6如果某个相邻格已经在开启列表里了，检查现在的这条路径G值是否会更低一些。
如果新的G值更低，那就把相邻方格的父节点改为目前选中的方格，重新计算F和G的值。
一旦重新选择了一个点那么就需要重新计算一下当前的费用,上面写着只计算G和F的 值,为什么呢!
原因:每个点到目标点的距离是固定的,所以H点(又上角的点)是不需要改变的,会变化的G值仅仅是因为路经改变的原因跟起始点的距离会发生改变,
所以只需要计算G的值和F的值,其他的点也会相应的更新;
<图一>
因为选择的42,但是出现了3个相同的估价,那么我们该怎么选择呢?
<图二>
这里还有另外一个原则:那就是选择一个距离目标点最近的一个值,也就是H值最低的一个.
也就是左侧的48这个方块 ,那么就把48这个点从开启列表中删除,送进关闭列表中.
因为选择了48,新增了左侧两个点,那么跟新一下在开启列表中的当前48下面的两个点(在这里下面那两个点是没有变化的,因为42下面的也是48,所以路径的值是没有改变的);
那么继续走
当我们继续走的时候,发现遍历48所能达到的值,发现这条路径不是最优的.
为什么不是最优的呢:(因为在它的开启列表中还有一个48)
那么在他的开启列表中还有一个48的值,那么就把当前的这个48从开起列表中删除，送进关闭列表中。
我们就回到上一步,选择42下方的48;
同理，这个48也不是最优的，因为他的开启列表中还有一个48，那么我们继续选择42，右侧的这个48；
结束

起始格下方格子的父节点已 经和前面不同的。 之前它的G值是，并且指向 右上方的格子。现在它的G 值是，指向它上方的格子。 这在寻路过程中的某处发生， 当应用新路径时，G值经过 检查变得低了－于是父节点 被重新指定，G和F值被重
新计算。

根据上述的原理得到如上图所示的路径，也就是最佳路径；

总结

1把起始格添加到开启列表。
2重复如下的工作：
寻找开启列表中F值最低的格子。我们称它为当前格。
把它切换到关闭列表。
/1/对相邻的格中的每一个–> 如果它不可通过或者已经在关闭列表中，略过它。反之如下。如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
/2/如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的 G和F值。
停止，当你 把目标格添加进了关闭列表，这时候路径被找到–>没有找到目标格，开启列表已经空了。这时候，路径不存在。
3.保存路径。从目标格开始，沿着每一格的父节点移动直到回到起始格。

算法：步骤架构
<1>开启集合
<2>关闭集合
<3>添加起始点到开始集合中
<4>循环如下步骤： 当前点=开启集合中最小F_Cost的点 将当前点移出开启集合中 将当前点添加到关闭集合中
<5>如果当前点是目标点，结束查询
<6>遍历当前点的每个相邻点 如果相邻点不能访问或者相邻点在关闭集合中，跳过此相邻点 如果新路径到相邻点的距离更短，或者相邻点不在开启集合中 重新设置F_Cost 重新设置其父节点为当前点
<7>如果相邻点不在开启集合中
<8>添加相邻点到开启集合