一、算法思想
在状态空间搜索中，如果每一步都利用估价函数 f(n)=g(n)+h(n) 对Open表中的结点进行排序，则称A算法。它是一种为启发式搜索算法。
算法类型：
- 全局择优： 从Open表的所有结点中选择一个估价函数值最小的进行扩展。
- 局部择优：仅从刚生成的子结点中选择一个估价函数值最小的进行扩展。
二、全局择优搜索A算法过程
- 把初始结点S0放入Open表中，f(S0)=g(S0)+h(S0)；
- 如果Open表为空，则问题无解 ，失败退出；
- 把Open表的第一个结点取出放入Closed表，并记该结点为n；
- 考察结点n是否为目标结点。若是，则找到了问题的解，成功退出；
- 若结点n不可扩展，则转第(2)步；
- 扩展结点n，生成其子结点ni(i=1, 2, …)，计算每一个子结点的估价值f(ni)(i=1, 2, …)，并为每一个子结点设置指向父结点的指针，然后将这些子结点放入Open表中；
- 根据各结点的估价函数值，对Open表中的全部结点按从小到大的顺序重新进行排序；
- 转第(2)步。