时间真是过的飞快！每次放松去享受一下生活，就感觉里职业高端精英的梦想远了一些。而森林里松树的气息，实在让人心旷神怡。真希望每天可以去森林公园给大脑补补氧气！回头看看2019这已经过去的2个月，完全想不起任何知识点了。还是不能只学数学！ 看起计算机有不会的数学再去查阅吧 ~

-----------------------------------------------------废话分割线----------------------------------------------------

基本概念：

启发式搜索： 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。

 IDA*算法： 这种算法被称为迭代加深A算法，可以有效的解决A空间增长带来的问题，甚至可以不用到优先级队列。

搜索区域（The Search Area）： 图中的搜索区域被划分为了简单的二维数组，数组每个元素对应一个小方格，当然我们也可以将区域等分成是五角星，矩形等，通常将一个单位的中心点称之为搜索区域节点（Node）。　　

开放列表(Open List)： 我们将路径规划过程中待检测的节点存放于Open List中，而已检测过的格子则存放于Close List中。

关闭列表(Close List)： 我们将路径规划过程中已经检查过的节点放在Close List。

启发函数（Heuristics Function）（估价函数）： H为启发函数，也被认为是一种试探，由于在找到唯一路径前，我们不确定在前面会出现什么障碍物，因此用了一种计算H的算法，具体根据实际场景决定。在我们简化的模型中，H采用的是传统的曼哈顿距离（Manhattan Distance）估价函数，也就是横纵向走的距离之和。 F(n) = G + H。F代表当前检查点的总花费，G代表起点到当前检查点的花费，H代表当前检查点到终点的预估花费。

父节点（parent）： 在路径规划中用于回溯的节点。

---------------------------------------前提介绍分割线--------------------------------------------------------

  我理解的高效学习计算机，”理论公式+ 图形动态演示+ 代码演示“三合一疗效显著！

一.A算法

1.A算法的公式表示：

A算法由f(n)=g(n)+h(n) 俩个因素决定，g(n)是这一步的代价函数,h(n)是这一步的预估函数； 对于A*算法来说，评判函数也是f(n)=g∗(n)+h∗(n) 这个，只不过加了约束条件，g∗(n)>0，h*(n)<=任意h(n)； 以上只不过是定义，对于一个实例来说，h(n)由很多种，h(n)只是估值函数的一个集合，有各种方法h1(n)h2(n) h3(n)…，取其中任意一个方法带入上述公式，组成评判函数，都是A算法的实现，现在取从集合中一个函数h∗(n) h∗(n)h*(n)，使得它比集合中任意的函数都优秀，这样的算法叫A*算法。 也就是A*算法是最优的A算法。（因为估值函数最优）。

2.算法的过程8步：

3.代码演示

二.A*算法

A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。

1.公式表示为： 

其中

 f(n) 是从初始状态经由状态n到目标状态的代价估计，

g(n) 是在状态空间中从初始状态到状态n的实际代价，

 h(n) 是从状态n到目标状态的最佳路径的估计代价。

（对于路径搜索问题，状态就是图中的节点，代价就是距离）

h(n)的选取

保证找到最短路径（最优解的）条件，关键在于估价函数f(n)的选取（或者说h(n)的选取）。 我们以d(n)表达状态n到目标状态的距离，那么h(n)的选取大致有如下三种情况：

 1. 如果h(n)< d(n)到目标状态的实际距离，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。

 2. 如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行， 此时的搜索效率是最高的。

3. 如果 h(n)>d(n)，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

该算法在最短路径搜索算法中分类为： 直接搜索算法：直接在实际地图上进行搜索，不经过任何预处理； 启发式算法：通过启发函数引导算法的搜索方向； 静态图搜索算法：被搜索的图的权值不随时间变化。

看了这些还是不清楚他是什么！？做个题来亲自体会一下 ！

距离估计与实际值越接近，估价函数取得就越好 例如对于几何路网来说，可以取两节点间曼哈顿距离做为距离估计，即f=g(n) + (abs(dx - nx) + abs(dy - ny))；这样估价函数f(n)在g(n)一定的情况下，会或多或少的受距离估计值h(n)的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijkstra算法的毫无方向的向四周搜索。 算法实现（路径搜索） 创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。 算起点的h(s); 将起点放入OPEN表; 

2.算法过程

1）将起点A添加到open列表中（A没有计算花费F是因为当前open列表只有这一个节点）。

2 ）检查open列表，选取花费F最小的节点M（检查M如果为终点是则结束寻路，如果open列表没有则寻路失败，直接结束）。

3）对于与M相邻的每一节点N：（下面本来没有序号的，csdn markdown的bug）

a.如果N是阻挡障碍，那么不管它。

b.如果N在closed列表中，那么不管它。

c.如果N不在open列表中：添加它然后计算出它的花费F(n)=G+H。

d.如果N已在open列表中：当我们使用当前生成的路径时，检查F花费是否更小。如果是，更新它的花费F和它的父节点。

4 )重复b,c步。

3.代码演示

用不同计算机语言实现A*算法不同。可以在网络上查找到代码。我没找到动图。

推荐一个 app:算法动画图解。

刚开始学习计算机，有些凌乱，有错误之处还请指出！

多谢！

Have a nice day !

希望通过结构化知识，提高学习效率，让你的工作时间更值钱，赚钱更高效！------------《 数据分析笔记》