文档介绍：: .
佳的节点”。这样可以有效的防止“最
佳节点”的 丢失。那么 A*算法又是一种什么样的算法呢？其实 A*算法
也是一种最好优先的算法。只不过要加上一些约束 条件罢了。由于在
一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就
是用最快的方法求 解问题，A*就是干这种事情的！我们先下个定义，
如果一个估价函数可以找出最短的路径，我们称之为可采 纳性。A*算
法是一个可采纳的最好优先算法。A*算法的估价函数克表示为：f’(n) = g’(n) + h’(n)
这里，f’(n)是估价函数，g’(n)是起点到终点的最短路径值，h’(n)
是 n 到目标的最断路经的启发值。由 于这个 f’(n)其实是无法预先知道
的，所以我们用前面的估价函数 f(n)做近似。g(n)代替 g’(n)，但
g(n)>=g’(n)才可 （大多数情况下都是满足的，可以不用考虑），h(n)
代替 h’(n)，但 h(n)<=h’(n)才可（这一点特别的重 要）。可以证明应
用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应
用这种估价函数的 最好优先算法就是 A*算法。哈！你懂了吗？肯定没
懂！接着看！
举一个例子，其实广度优先算法就是 A*算法的特例。其中 g(n)是
节点所在的层数，h(n)=0，这种 h(n)肯 定小于 h’(n)，所以由前述可
知广度优先算法是一种可采纳的。实际也是。当然它是一种最臭的 A*
算法。
再说一个问题，就是有关 h(n)启发函数的信息性。h(n)的信息性
通俗点说其实就是在估计一个节点的值 时的约束条件，如果信息越多
或约束条件越多则排除的节点就越多，估价函数越好或说这个算法越
好。这就 是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，
一点启发信息都没有。但在游戏开发中由于实 时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小
h(n)的信息，即 减小约束条件。但算法的准确性就差了，这里就有一
个平衡的问题。可难了，这就看你的了！
好了我的话也说得差不多了，我想你肯定是一头的雾水了，其实这
是写给懂 A*算法的同志看的。哈哈！ 你还是找一本人工智能的书仔细
看看吧！我这几百字是不足以将 A*算法讲清楚的。只是起到抛砖引玉
的作用 希望大家热情参与吗！
预知 A*算法的应用，请看《深入 A*算法》。
第二部分：深入 A*算法———浅析 A*算法在搜索最短路径中的应用
一、前言
在这里我将对 A*算法的实际应用进行一定的探讨，并且举一个有
关 A*算法在最短路径搜索 的例子。值得注意的是这里并不对 A*的基
本的概念作介绍，如果你还对 A*算法不清楚的话， 请看姊妹篇《初识
A*算法》。
这里所举的例子是参考 AMIT 主页中的一个源程序，你可以在 AMIT
的站点上下载也可以在我 的站点上下载。你使用这个源程序时，应该遵守一定的公约。
二、A*算法的程序编写原理
我在《初识