队列(queue)是一种简单的数据结构,它所遵循的规则是先进先出(First in First out, FIFO),对比LIFO的数据结构“栈”,你可以阅读[这篇文章]。这里所说的队列和我们现实中的队列是一样的,就比如说公交车排队,早到的,排在靠前位置的人自然可以优先上车(假设大家都很文明),利用这种特性,人们可以用来管理各种各样需要按照先后循序的事物,比如银行,因为银行的服务窗口有限,不能同时给所有人提供服务,所以利用计算机提供一个队列系统,给客户一个排队号码,计算机系统可以根据这个排队号码的大小来决定为谁优先提供服务。
按照和栈类似的介绍方法,为了使代码的表意更加明确,我使用C++标准库提供的队列适配器queue来构造队列这种数据结构。
使用queue需要引用头文件:

初始化一个空的队列:

令一个元素进入队尾:

令队首元素出列:

获取队尾元素:

获取队首元素:

判断目前队列是否为空:

返回当前队列中元素的数目:

由于队列本身的概念十分简单,所以关于上面这些方法我就不做具体说明了,相信看官看其作用的名字就能知道它们该怎么用了,在这里,我想着重介绍下BFS搜索(Breadth First Search, 广度优先搜索),不要被这个名字吓到,这个搜索算法主要是适用于“树”以及“图”的搜索,那么顾名思义,就是一层一层的搜索,比如对于一棵树,就是以这个样子的顺序进行搜索,见[图1]:

BFS的遍历方式是从深度最低的开始,扫清同一深度之后再进行进行下一深度的搜索,也就是如同[图1]所标注的序号的顺序进行搜索。
对于树的每个节点而言,它只知道自己所连接的子节点是什么,比如1号节点只知道2、3号节点,而2号节点只知道4、5节点……那么怎么做才能按照图上所示的那种顺序搜索呢?这时候,我们就能看到队列的作用了,下面几幅图,就是BFS搜索算法的核心内容,请务必睁大眼睛看好:
1.首先是一个空队列,蓝色箭头表示队列的方向,左边是队首,右侧是队尾:

2.根结点提前入列,作为搜索的起点:

3.然后队首元素出列,同时与队首元素相连接的节点进入队列:

4.重复步骤3:

5.最后由于所有的绿色节点都没有子节点了,所以就是顺序出列即可:

看到这个队列的作用了么?利用这个队列,我们成功的完成了BFS搜索,整个算法按照我们预先想要的顺序完成了搜索任务!

BFS搜索的这种宽度优先的特性,使得我们可以利用其解决“最少路径”问题,比如一个迷宫,你需要找到一个路径,这个路径是能够抵达出口的最短路径,这个时候,用BFS就最合适不过,因为BFS当首次搜索到规定值的时候,肯定是在满足搜索条件的最浅的深度。
比如走这个迷宫(#代表墙壁,$代表起点,%代表终点):

 

让你找最短路径,你该怎么办?迷宫很容易构造出图(Graph)这种结构,我们默认每个节点所连接的就是其上下左右不是墙的部分,我们就利用刚刚介绍的BFS搜索算法来找到这个最短的路径,在这里我们只给出核心部分的代码,请你对照之前的讲解来看这段代码,并自己理解BFS具体实现的方法:

在搜索中我们记录了每个节点父节点的位置,是为了便于我们最后输出路径,因为对于子节点而言,只需要不断找回其父节点的位置,就一定可以到达根节点。
下面就是路径的输出:

对于刚才给出的那个迷宫而言,其输出的路径图就是:

如果我们把迷宫图稍微做一点变动:

那么BFS搜索依旧会给出最短的一条路径:

说点什么

4 评论 在 "队列与BFS搜索"

  Subscribe  
最新 最旧 得票最多
提醒

[…] 记得当年第一次见到A*这个名字的时候,感觉非常的高端洋气,于是在气势上就输给了它,所以大家在继续阅读这篇文章的时候一定要放松,这个算法的确很著名,而且也的确非常的高效,但是它并不复杂,而且非常容易理解。 首先说下A*算法的作用:找到一条从起始状态到最终状态的最短路径。不知道大家看到这个作用有没有联想到什么?具有同样作用的一个算法“BFS广度优先搜索”在我之前的博客中介绍过,如果你不知道,可以点击这里回顾一下这个算法。 BFS通过“一层一层”地扩展节点,以此确保在发现目标状态的时候整个搜索树的深度最低,这是一种非常盲目的搜索方法,因为如果解的深度较深的话,我们有时候不得不搜索过所有的节点才能找到目标,而A*算法则不然,我编一个故事说明BFS和A*算法的区别: […]

[…] 转载文章:http://blueve.me/archives/417 […]

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

超赞!!!