a算法:初识A*算法

　　 写这篇文章初衷是应个网友要求当然我也发现现在有关人工智能中文站点实在太少我在这里抛砖引玉希望大家都来热心参和 　　还是说正题我先拿A*算法开刀是A*在游戏中有它很典型使用方法是人工智能在游戏中代表

　　A*算法在人工智能中是种典型启发式搜索算法为了说清楚A*算法我看还是先说说何谓启发式算法

、何谓启发式搜索算法

　　在说它的前先提提状态空间搜索状态空间搜索如果按专业点说法就是将问题求解过程表现为从状态到目标状态寻找这个路径过程通俗点说就是在解个问题时找到条解题过程可以从求解开始到问题结果(好象并不通俗哦)由于求解问题过程中分枝有很多主要是求解过程中求解条件不确定性不完备性造成使得求解路径很多这就构成了个图我们说这个图就是状态空间问题求解实际上就是在这个图中找到条路径可以从开始到结果这个寻找过程就是状态空间搜索

　　常用状态空间搜索有深度优先和广度优先广度优先是从状态层层向下找直到找到目标为止深度优先是按照定顺序前查找完个分支再查找另个分支以至找到目标为止这两种算法在数据结构书中都有描述可以参看这些书得到更详细解释

　　前面说广度和深度优先搜索有个很大缺陷就是他们都是在个给定状态空间中穷举这在状态空间不大情况下是很合适算法可是当状态空间十分大且不预测情况下就不可取了他效率实在太低甚至不可完成在这里就要用到启发式搜索了

　　启发式搜索就是在状态空间中搜索对每个搜索位置进行评估得到最好位置再从这个位置进行搜索直到目标这样可以省略大量无畏搜索路径提到了效率在启发式搜索中对位置估价是十分重要采用了区别估价可以有区别效果我们先看看估价是如何表示

　　启发中估价是用估价表示如:

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

　　其中f(n)是节点n估价g(n)实在状态空间中从节点到n节点实际代价h(n)是从n到目标节点最佳路径估计代价在这里主要是h(n)体现了搜索启发信息g(n)是已知如果说详细点g(n)代表了搜索广度优先趋势但是当h(n)>>g(n)时可以省略g(n),而提高效率这些就深了不懂也不影响啦！我们继续看看何谓A*算法

2、初识A*算法

　　启发式搜索其实有很多算法比如:局部择优搜索法、最好优先搜索法等等当然A*也是这些算法都使用了启发但在具体选取最佳搜索节点时策略区别象局部择优搜索法就是在搜索过程中选取“最佳节点”后舍弃其他兄弟节点父亲节点而直得搜索下去这种搜索结果很明显由于舍弃了其他节点可能也把最好节点都舍弃了求解最佳节点只是在该阶段最佳并不定是全局最佳最好优先就聪明多了他在搜索时便没有舍弃节点(除非该节点是死节点)在每步估价中都把当前节点和以前节点估价值比较得到个“最佳节点”这样可以有效防止“最佳节点”丢失那么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*算法

延伸阅读

• 2008-12-14-- 点灯游戏:点灯游戏算法实现代码
• 2009-2-12-- a算法:深入A*算法