A* 搜索算法

启发式搜索算法

• 要理解 A* 搜寻算法，还得从启发式搜索算法开始谈起。所谓启发式搜索，就在于当前搜索结点往下选择下一步结点时，可以通过一个启发函数来进行选择，选择代价最少的结点作为下一步搜索结点而跳转其上（遇到有一个以上代价最少的结点，不妨选距离当前搜索点最近一次展开的搜索点进行下一步搜索）。
  DFS 和 BFS 在展开子结点时均属于盲目型搜索，也就是说，它不会选择哪个结点在下一次搜索中更优而去跳转到该结点进行下一步的搜索。在运气不好的情形中，均需要试探完整个解集空间, 显然，只能适用于问题规模不大的搜索问题中。
  而与 DFS、BFS 不同的是，一个经过仔细设计的启发函数，往往在很快的时间内就可得到一个搜索问题的最优解，对于 NP 问题，亦可在多项式时间内得到一个较优解。是的，关键就是如何设计这个启发函数。

A* 搜寻算法

• A* 搜寻算法，俗称 A 星算法，作为启发式搜索算法中的一种，这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的 NPC 的移动计算，或线上游戏的 BOT 的移动计算上。该算法像 Dijkstra 算法一样，可以找到一条最短路径；也像 BFS 一样，进行启发式的搜索。
  A* 算法最为核心的部分，就在于它的一个估值函数的设计上：f(n) = g(n) + h(n)
  其中f(n)是每个可能试探点的估值，它有两部分组成：一部分，为g(n)，它表示从起始搜索点到当前点的代价（通常用某结点在搜索树中的深度来表示）。另一部分，即h(n)，它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值，
  h(n) 设计的好坏，直接影响着具有此种启发式函数的启发式算法的是否能称为 A* 算法。
  一种具有 f(n) = g(n) + h(n) 策略的启发式算法能成为 A* 算法的充分条件是：
  1、搜索树上存在着从起始点到终了点的最优路径。
  2、问题域是有限的。
  3、所有结点的子结点的搜索代价值>0。
  4、h(n) <= h*(n) （h*(n)为实际问题的代价值）。
  当此四个条件都满足时，一个具有 f(n) = g(n) + h(n) 策略的启发式算法能成为 A* 算法，并一定能找到最优解。
  对于一个搜索问题，显然，条件1,2,3都是很容易满足的，而条件4：h(n) <= h*(n) 是需要精心设计的，由于h*(n)显然是无法知道的，所以，一个满足条件4的启发策略 h(n) 就来的难能可贵了。
  不过，对于图的最优路径搜索和八数码问题，有些相关策略 h(n) 不仅很好理解，而且已经在理论上证明是满足条件 4 的，从而为这个算法的推广起到了决定性的作用。
  且 h(n) 距离 h*(n) 的呈度不能过大，否则 h(n) 就没有过强的区分能力，算法效率并不会很高。对一个好的 h(n) 的评价是：h(n) 在 h*(n) 的下界之下，并且尽量接近 h*(n)。