5_1

这学期学校开了人工智能课程,留了一项小作业,就是使用A*算法解决八数码问题,觉得挺有意思,于是就写下这篇文章来与大家分享。其实我很久很久以前就已经听闻过A*算法的大名了,但是鉴于当时的理解能力不足(懒?),就不了了之了。
记得当年第一次见到A*这个名字的时候,感觉非常的高端洋气,于是在气势上就输给了它,所以大家在继续阅读这篇文章的时候一定要放松,这个算法的确很著名,而且也的确非常的高效,但是它并不复杂,而且非常容易理解。
首先说下A*算法的作用:找到一条从起始状态到最终状态的最短路径。不知道大家看到这个作用有没有联想到什么?具有同样作用的一个算法“BFS广度优先搜索”在我之前的博客中介绍过,如果你不知道,可以点击这里回顾一下这个算法。
BFS通过“一层一层”地扩展节点,以此确保在发现目标状态的时候整个搜索树的深度最低,这是一种非常盲目的搜索方法,因为如果解的深度较深的话,我们有时候不得不搜索过所有的节点才能找到目标,而A*算法则不然,我编一个故事说明BFS和A*算法的区别:

王尼玛同学去食堂吃饭,但是吃完饭回到宿舍门口才发现自己的钥匙落在了食堂的座椅上,于是他返回食堂去找钥匙。他回到食堂的门口,此时面对茫茫多的座椅他有两个方法来找钥匙:
1、从离自己最近的座椅开始一个一个翻
2、直接去自己吃饭时的座椅找

呃(= 。=),想必不用我说也知道哪个方法靠谱了吧?假如说下图就是王尼玛吃饭的食堂,黄色标记的座位是王尼玛吃饭的餐桌(钥匙的所在处):


那么使用方法一的效果是这样的:

这真是太蛋疼了,总共54个座位,王尼玛翻腾了49个才找到了他的钥匙。那么,方法二的结果呢?看下图:

仅仅经过了14个座位就找到了钥匙。
各位看客一定不耐烦了,既然知道钥匙的位置,那用方法一不是脑残么?说的不错,方法一就是典型的BFS搜索,而方法二则是我们今天的主角A*(过程不完全一致,但是就是这个思路)!在见识了BFS的脑残(盲目性)之后,我们需要思考的是,为什么A*会优于BFS?方法二之所以能更快的找到目标,就是因为比方法一多了一条信息“钥匙在自己吃饭时的座椅”,这条信息就是A*算法中所说的“启发信息”,也就是让我们的算法显得智能不脑残的东东。
当我们进行BFS的时候,扩展节点的方式是固定的,就是按层,一层结束之后再下一层,对于下面这个树状图,就是这样的顺序:
A, (B, D, E, F), ((B的子节点), (D的子节点), (G, H, I), (F的子节点))……

那么假如在这棵树中,我们要找的节点是I,我们类比刚才的例子,给BFS加上“智商”,也就是我们搜索的时候知道距离I的大致位置,并按照贴近I的距离大小,我们有顺序的扩展节点,我们把刚才的图改进一下,估计和最终结果越近的点颜色就越深,搜索的时候也就越优先:

这样的话我们的扩展顺序就是
A, (B, D, E, F), (G, H, I)
和用BFS相比,我们的算法根据估计就直接跳过了很多没有价值的节点。
而来进行估计的,就是A*算法中的核心“启发函数”。

下面给出A*算法的具体算法:

启发函数:f(S) = g(S) + h(S)
已经行进:g(S)
估计还要行进:h(S)

改进BFS的地方:
把BFS所用到的队列改成按启发函数值排列的优先队列。
有可能改变父子节点的关系。

没错就是这么简单。实际上如果把g(s)当作深度,h(s) = 0,则A*就变成了BFS。不过A*之所以牛的冒星星,那是因为对启发函数还有一定的限制:
假设从状态S抵达目标状态的实际还需进行的长度为h’(S),那么我们启发函数中的h(S)必须要满足h(S) 在算法实现的过程中,我们需要两个表:

OPEN表,用优先队列实现,用来保存待扩展的节点(改进自BFS的队列)。
CLOSED表,用HASH表或者能够高效检索的数据结构实现,用来保存已经扩展过的节点(可以考察一个状态是否已经被产生过)。

下面我用类C++语言的伪代码来描述:

很简单对吧?
由于这篇文章已经写得很长了,所以我打算先就此收尾,我将在下一篇文章中来进行A*算法的实战演练!看看A*算法是如何帮助我们解决问题的~

说点什么

4 评论 在 "A*算法 – 介绍"

  Subscribe  
最新 最旧 得票最多
提醒

博主 想问一下你是用什么软件画的图?

哈哈 我们也是AI课 老师让我们找八数码的论文 就搜到你的博客了 写的很好啊

[…] 输入的s表示一个状态,index用于查找在搜索树中的此状态,以便获取其深度。 然后我们参看前一篇文章中给出的A*算法模板,写出这个算法: […]