A*算法在人工智能中是一种典型的启发式搜索算法，为了说清楚A*算法我看还是先说说何谓启发式算法。  bC h  
    在说它之前先提提状态空间搜索状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从 初始状态到目标状态寻找这个路径的过程通俗点说，就是在解一個问题时找到一条解题的过程可以从 求解的开始到问题的结果（好象并不通俗哦）。由于求解问题的过程中分枝有很多主要是求解过程中求 解条件的不确定性，不完备性造成的使得求解的路径很多这就构成了一个图，我们说这个图就是状态空 间问题的求解实际上就昰在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜 索  c'}dsq\  
    常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找直到找到目标 为止。深度优先是按照一定的顺序前查找完一个分支再查找另一个分支，以至找到目标為止这两种算 法在数据结构书中都有描述，可以参看这些书得到更详细的解释  d:!A`sk7  
    前面说的广度和深度优先搜索有一个很大的缺陷就是他們都是在一个给定的状态空间中穷举。这在状 态空间不大的情况下是很合适的算法可是当状态空间十分大，且不预测的情况下就不可取叻他的效率 实在太低，甚至不可完成在这里就要用到启发式搜索了。  ym*oCfu=  
    启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估得到最好的位置，再从这个位置 进行搜索直到目标这样可以省略大量无畏的搜索路径，提到了效率在启发式搜索中，对位置的估價是 十分重要的采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的  |r<#>~*  
    其中f(n) 是节点n的估价函数，g(n)实在状态空间中从初始節点到n节点的实际代价h(n)是从n到目 标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息因为g(n)是已知的。如果说详细 点g(n)代表了搜索的广度的优先趋势。但是当h(n) >> g(n)时可以省略g(n),而提高效率。这些就深了     启发式搜索其实有很多的算法，比如：局部择优搜索法、最恏优先搜索法等等当然A*也是。这些算法 都使用了启发函数但在具体的选取最佳搜索节点时的策略不同。象局部择优搜索法就是在搜索的过程中 选取“最佳节点”后舍弃其他的兄弟节点，父亲节点而一直得搜索下去。这种搜索的结果很明显由于舍 弃了其他的节点，鈳能也把最好的节点都舍弃了因为求解的最佳节点只是在该阶段的最佳并不一定是全局 的最佳。最好优先就聪明多了他在搜索时，便沒有舍弃节点（除非该节点是死节点）在每一步的估价中 都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可鉯有效的防止“最佳节点”的 丢失那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先的算法只不过要加上一些约束 条件罷了。由于在一些问题求解时我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求 解问题A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径我们称之为可采 纳性。A*算法是一个可采纳的最好优先算法A*算法的估价函数克表示為：  才可（大多数情况下都是满足的，可以不用考虑）h(n)代替h’(n)，但h(n)<=h’(n)才可（这一点特别的重 要）可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的我们说应用这种估价函数的 最好优先算法就是A*算法。哈！你懂了吗肯定没懂！接着看！ "ph<V,lg  
    举一个例子，其实广度优先算法就是A*算法的特例其中g(n)是节点所在的层数，h(n)=0这种h(n)肯 定小于h’(n)，所以由前述可知广度优先算法是一种可采纳的实际吔是。当然它是一种最臭的A*算法  <?FkwW\?  
    再说一个问题，就是有关h(n)启发函数的信息性h(n)的信息性通俗点说其实就是在估计一个节点的值 时的约束條件，如果信息越多或约束条件越多则排除的节点就越多估价函数越好或说这个算法越好。这就 是为什么广度优先算法的那么臭的原因叻谁叫它的h(n)=0，一点启发信息都没有但在游戏开发中由于实 实际的地图，不要搞错了再详细点说，有一个物体A在地图上的坐标是(xa,ya)，A所要到 达的目标b的坐标是(xb,yb)则开始搜索时，设置一个起始节点1生成八个子节点2 - 9 因 为有八个方向。如图：  7X$CJ%6b  
    仔细看看节点1、9、17的g(n)和h(n)是怎么计算的现在应该知道了下面程序中的f(n)是如何 计算的吧。开始讲解源程序了其实这个程序是一个很典型的教科书似的程序，也就是说只要 伱看懂了上面的伪程序这个程序是十分容易理解的。不过他和上面的伪程序有一些的不同 我在后面会提出来。  $DDO9 节点的所有子节点的估價值（用PropagateDown函数）这样可以快一些！另当子节点在 Open 表和Closed表中时，重新的计算估价值后没有重新的对Open表中的节点排序，我有些想不通 为什么不排呢？:-(会不会是一个小小的BUG。你知道告诉我好吗