启发式搜索算法的基本思路(启发式搜索的概念)

A算法——启发式路径搜索

A是一种路径搜索算法，比如为游戏中的角色规划行动路径。

启发式搜索算法的基本思路(启发式搜索的概念)

A 算法的输入是， 起点（初始状态） 和 终点（目标状态） ，以及两点间 所有可能的路径 ，以及涉及到的 中间节点（中间状态） ，每两个节点间的路径的 代价 。

一般还需要某种 启发函数 ，即从任意节点到终点的近似代价，启发函数能够非常快速的估算出该代价值。

输出是从 起点到终点的路径 ，即代价小。同时，好的启发函数将使得这一搜索运算尽可能高效，即搜索尽量少的节点/可能的路径。

f(n)=g(n)+h(n)

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

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

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

A算法是从起点开始，检查所有可能的扩展点（它的相邻点），对每个点计算g+h得到f，在所有可能的扩展点中，选择f小的那个点进行扩展，即计算该点的所有可能扩展点的f值，并将这些新的扩展点添加到扩展点列表（open list）。当然，忽略已经在列表中的点、已经考察过的点。

不断从open list中选择f值小的点进行扩展，直到到达目标点（成功找到路径），或者节点用完，路径搜索失败。

算法步骤：

参考

A 算法步骤的详细说明请参考 A寻路算法 ，它包含图文案例清楚的解释了A算法计算步骤的一些细节，本文不再详细展开。

看一下上面参考文档中的案例图，终搜索完成时，蓝色边框是close list中的节点，绿色边框是open list中的节点，每个方格中三个数字，左上是f（=g+h），左下是g（已经过路径的代价），右下是h（估计未经过路径的代价）。蓝色方格始终沿着f值小的方向搜索前进，避免了对一些不好的路径（f值较大）的搜索。（图片来自 A寻路算法 ）

现在我们可以理解，A算法中启发函数是重要的，它有几种情况：

1) h(n) = 0

一种极端情况，如果h(n)是0，则只有g(n)起作用，此时A演变成Dijkstra算法，这保证能找到短路径。但效率不高，因为得不到启发。

2) h(n) < 真实代价

如果h(n)经常都比从n移动到目标的实际代价小（或者相等），则A保证能找到一条短路径。h(n)越小，A扩展的结点越多，运行就得越慢。越接近Dijkstra算法。

3) h(n) = 真实代价

如果h(n)精确地等于从n移动到目标的代价，则A将会仅仅寻找佳路径而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，你仍可以在一些特殊情况下让它们精确地相等（译者：指让h(n)精确地等于实际值）。只要提供完美的信息，A会运行得很完美，认识这一点很好。

4) h(n) > 真实代价

如果h(n)有时比从n移动到目标的实际代价高，则A不能保证找到一条短路径，但它运行得更快。

5) h(n) >> 真实代价

另一种极端情况，如果h(n)比g(n)大很多，则只有h(n)起作用，A演变成BFS算法。

关于启发函数h、Dijkstra算法、BFS（佳优先搜索）算法、路径规划情况下启发函数的选择、算法实现时List的数据结构、算法变种等等更多问题，请参考： A算法

谁能介绍一下JPS寻路算法的思想

这是一个近年来发现的高效寻路算法。不过有一个限制就是只能在规则的网格地图上寻路，而且图上的点或边不能带权重，也就是不能有复杂的地形，只支持平坦和障碍两种地形。

其思想就是跳过矩形平坦区域的大量对称路径，只寻找所谓的跳跃点，作为搜索的节点。这样做的好处是裁剪了矩形区域内大量的节点，使open

list中的节点数相对较少。要知道，通常启发式搜索算法如A，大量时间耗费在对open

list的操作上。实现得好的A算使用优先队列，甚至HOT(heap on top）来对操作进行优化。但当open

list中的节点过多，这些操作还是会变得很昂贵。不过JPS有个缺点是每生成一个节点，也就是要找到一个跳跃点，相比较A算法，是比较昂贵的。幸好通

常来说，得到的收益更多些。所以，在适用的情况下，还是使用JPS的。

具体的实现，主要有两部分。第一部分，从open list中取一个佳节点，然后从几个特定方向展开搜索，把每个方向得到的跳跃点，加入open list里。第二部分，就是找到一个跳跃点。

对于起始点，可以向所有方向展开搜索。对于其他节点，要看父节点指向本节点的方向，向所有自然邻居和被迫邻居节点方向进行搜索。

例如下图的例子，对于节点n和父节点p和障碍x，+是n的自然邻居，也就是说从p到n到+是佳路径。如果x不是障碍，从p到n到-不是佳路径，因为从p到x到-近。但是如果x是障碍，那么从p到n到-就是佳路径了，所以这时候称-为被迫邻居。

- + +

x n +

p x -

以上是n和p对角的例子。还有种情况是n和p是直线：

x x -

p n +

x x -

搜寻跳跃点是递归进行的。首先判断一个节点是否是跳跃点。如果这个点有被迫邻居，那么这个节点就是跳跃点。第二种情况，如果这个节点是目的地节点那么也当作

跳跃点。如果不是，那么就递归地沿本来方向继续搜寻下去。对于对角方向要额外多做两步，即先对其相应的（左右两个）直线方向进行搜索，如果找到跳跃点，就

把自身也当作跳跃点返回。如果直线没找到，那么就一样继续按对角方向递归寻找跳跃点，并返回那个跳跃点。

什么是盲目搜索？启发式搜索和盲目搜索有什么区别？

盲目搜索算法，也称为无信息搜索，是一种只依据预定的搜索策略进行搜索，而不考虑问题特性的方法。通常适用于简单的问题求解，其中较为常见的包括宽度优先搜索算法和深度优先搜索。

宽度优先搜索算法（BFS）以队列实现，从根节点开始遍历，遍历完再按照同样的方式遍历下一层节点。其优点在于能够找到短路径，并且如果短路径存在，则可以保证找到。但其缺点在于可能需要遍历许多无用节点，导致时间开销高。

深度优先搜索算法（DFS）以栈实现，从根节点开始遍历至深层，直至找到目标节点或无节点可扩展为止。其优点在于空间复杂度低，但其缺点在于可能会漏掉短路径，因此不适合用于求短路径的问题。

启发式搜索算法则是基于具有启发性的搜索策略，例如利用问题领域知识，结合评估函数来指导搜索方向，从而更加高效地求解复杂问题。其中典型的启发式搜索算法包括A搜索算法等。

相比盲目搜索算法，启发式搜索算法具有更高的效率和准确性，但会涉及到问题领域的先验信息和评估函数设计等问题，因此也存在一些缺点和局限性，例如易受局部解影响、评估函数的不确定性和复杂度高等。

关于A算法和3D算法

A算法是一种启发式搜索的算法，公式表示为： f(n)=g(n)+h(n)g(n) 是在状态空间中从初始节点到n节点的实际代价，

h(n)是从n到目标节点佳路径的估计代价。3D算法，没看懂你说什么意思

A算法 和 佳优先搜索算法（Best-First-Search）

佳优先搜索算法是一种启发式搜索算法（Heuristic Algorithm），其基于广度优先搜索算法，不同点是其依赖于估价函数对将要遍历的节点进行估价，选择代价小的节点进行遍历，直到找到目标点为止。 BFS算法不能保证找到的路径是一条短路径，但是其计算过程相对于Dijkstra

算快很多 。

佳优先搜索是一种启发式搜索算法。广度优先搜索和深度优先搜索都属于穷举类型的搜索，需要依次遍历所有的节点，当空间非常大的时候，这种方式的效率就会非常。而启发式的搜索是对状态控件中的每个点进行评估，然后选出的位置。

启发估价函数公式为：

n表示当前的点，g(n)为从起始点到点n的实际代价，h(n)为从点n到目标点的估价。

（图片来源于网络）

A算法将BFS算法和Dijkstra算法结合在一起，结合两算法的优点，既可以查找短路径的，有拥有和BFS不多的效率。

（图片来源于网络）

A算法详解

模拟寻路的地址