人工智能 —— A算法

一、算法思想

在状态空间搜索中，如果每一步都利用估价函数 f(n)=g(n)+h(n) 对Open表中的结点进行排序，则称A算法。它是一种为启发式搜索算法。

算法类型：

• 全局择优： 从Open表的所有结点中选择一个估价函数值最小的进行扩展。
• 局部择优：仅从刚生成的子结点中选择一个估价函数值最小的进行扩展。

二、全局择优搜索A算法过程

1. 把初始结点S0放入Open表中，f(S0)=g(S0)+h(S0)；
2. 如果Open表为空，则问题无解 ，失败退出；
3. 把Open表的第一个结点取出放入Closed表，并记该结点为n；
4. 考察结点n是否为目标结点。若是，则找到了问题的解，成功退出；
5. 若结点n不可扩展，则转第(2)步；
6. 扩展结点n，生成其子结点ni(i=1, 2, …)，计算每一个子结点的估价值f(ni)(i=1, 2, …)，并为每一个子结点设置指向父结点的指针，然后将这些子结点放入Open表中；
7. 根据各结点的估价函数值，对Open表中的全部结点按从小到大的顺序重新进行排序；
8. 转第(2)步。

三、全局择优搜索A算法搜索