您的当前位置是：第三章 确定性推理>>学习内容>>知识点三
下面继续学习A*算法
定义3 采用h*（x）的下界h（x）为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。
4．A*算法的特点
①A*算法能找到基于评价函数的由起始节点S至目标节点g的最佳路径；
②与盲目搜索略相比，A*算法减小了搜索空间，因而操作费用较小。
③当深度特性函数g（n）定义为深度函数d（n），启发式函数h（n）=0时，A*算法退化为宽度优先搜索算法，即：宽度优先搜索算法是A*算法的特例。
例3.6
设八数码问题的初始状态S0和目标状态Sg分别如图3.19所示，请利用A*搜索算法求解该问题。
问题求解
①g（n）：
g（n）= d（n）
其中，d（n）为深度函数，即节点n的深度或算法由S0搜索至n的操作次数，这意味着每次操作费用为1。
②启发式函数 h（n）：
h（n）= e（n）
其中，e（n）为误差函数，即节点n不在目标位置上的数码的个数。
图3.20是该问题对应的A*算法搜索树，其中，节点旁的括号内容标明了启发式函数值的计算过程。
