没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
广度优先搜索算法(,)
使用计算机求解的问题中,有许多问题是无法用数学公式
进行计算推导采用模拟方法来找出答案的。这样的问题往往需
要我们根据问题所给定的一些条件,在问题的所有可能解中用
某种方式找出问题的解来,这就是所谓的搜索法或搜索技术。
通常用搜索技术解决的问题可以分成两类:一类问题是给定初
始结点,要求找出符合约束条件的目标结点;另一类问题是给
出初始结点和目标结点,找出一条从初始结点到达目标结点的
路径。
常见的搜索算法有枚举法、广度优先搜索法、深度优先搜索法、
双向广度优先搜索法,算法、回溯法、分支定界法等。这里
来讨论一下广度优先搜索法。
一广度优先搜索算法
一般来说,可以采用搜索算法解决的这类问题的特点是:
有一组具体的状态,状态是问题可能出现的每一种情况。全
体状态所构成的状态空间是有限的,问题规模较小。
在问题的解答过程中,可以从一个状态按照问题给定的条件,
转变为另外的一个或几个状态。
可以判断一个状态的合法性并且有明确的一个或多个目标状
态。
所要解决的问题是:根据给定的初始状态找出目标状态,或
1
根据给定的初始状态和结束状态,找出一条从初始状态到结束
状态的路径。
采用广度优先搜索算法解答问题时,需要构造一个表明状态特
征和不同状态之间关系的数据结构,这种数据结构称为结点。
根据问题所给定的条件,从一个结点出发,可以生成一个或多
个新的结点,这个过程通常称为扩展。结点之间的关系一般可
以表示成一棵树,它被称为解答树。搜索算法的搜索过程实际
上就是根据初始条件和扩展规则构造一棵解答树并寻找符合目
标状态的结点的过程。
广度优先搜索算法中,解答树上结点的扩展是沿结点深度的“断
层”进行,也就是说,结点的扩展是按它们接近起始结点的程度
依次进行的。首先生成第一层结点,同时检查目标结点是否在
所生成的结点中,如果不在,则将所有的第一层结点逐一扩展,
得到第二层结点,并检查第二层结点是否包含目标结点,对
长度为 的任一结点进行扩展之前,必须先考虑长度为 的
结点的每种可能的状态。因此,对于同一层结点来说,求解问
题的价值是相同的,我们可以按任意顺序来扩展它们。这里采
用的原则是先生成的结点先扩展。
广度优先搜索算法中,为了便于进行搜索,要设置一个表存储
所有的结点,为了满足先生成的结点先扩展的原则,存储结点
的表一般设计成队列的数据结构。搜索过程中不断地从队列头
取出结点进行扩展。对生成的新结点,要检查它是否已在队列
2
中存在,还要检查它是否目标结点。如果新结点是目标结点,
则搜索成功,程序结束;若新结点不是目标结点,并且未曾在
队列中出现过,则将它加入到队列尾,否则将它丢弃,再从队
列头取出结点进行扩展。最终可能产生两种结果:找到目
标结点,或扩展完所有结点而没有找到目标结点。
如果目标结点存在于解答树的有限层上,广度优先搜索算法一
定能保证找到一条通向它的最佳路径,因此广度优先搜索算法
特别适用于只需求出最优解的问题。当问题需要给出解的路径,
则要保存每个结点的来源,也就是它是从哪一个节点扩展来的。
对于不同的问题,用广度优先搜索法的算法基本上都是一样的。
但表示问题状态的结点数据结构、新结点是否目标结点和是否
重复结点的判断等方面则有所不同,对具体的问题需要进行具
体分析。
二广度优先搜索算法的算法框架
!定义一个结点数据类型
!根据具体问题确定所需的数据类型
"
#$%& !定义 类型的数组,作为存储
结点的队列
'(%& ! 算法主程序
#$$ ! 型临时结点
#$)*+,*+!队列头指针和尾指针
-#$%.&
*'# !从文件中读入数据进行初始化
)/.
,/. !队列头指针和尾指针都指向队列
头
# 0, )1/, !队列非空时循环
!根据具体问题确定一个结点怎样扩展
$/%.& !取队列头的结点
3
*2 "3 !如果该结点可以扩展则产生一个新
结点
*2 - !如果新结点未曾在队列中出现过
,/, !将新结点加入队列尾
-#$%,&
%,&/$
%,&/) !记录父结点标识
*2' !如果新结点是目标结点
,/, !将队列尾结点的父结点指针指向
队列尾
-#$%,&
%,&/,
!输出路径
"3'( !退出程序
"*2
"*2
"*2
)/) !队列头的结点扩展完后出队,取
下一结点扩展
4
"'(
其中的
*'# 是从文件中读入初始化的数据,对问题的初始状态等进行设置的子
过程
"3 是判断结点是否能扩展的子过程,如果能则产生新结点
- 是检查新结点是否在队列中已经出现的函数,返回一个布尔值
则是检查新结点是否目标结点的函数,也返回一个布尔值
这些过程和函数要根据具体问题进行编写。另外, 用递归方式输出
路径的子过程:
'(%%&5, 6*+&
*267.
6/%6&
6
8'%6&
"*2
"'(
因为当搜索到目标结点时,该结点记录的是其父结点的标识,所以需要再将队
列尾指针前移,将其父结点指向当前的队尾,也即搜索到的目标结点。另外得
到的路径是从队列尾回到队列头的逆向路径,输出时要逆转,所以采用递归方
式,可以自动输出正向路径。子过程 8' 与具体的问题有关,要视需要
输出的结点信息而定。
这里将整个求解问题的过程分成了多个子过程,对不同的问题,程序的框架是
不变的,只需根据实际情况编写子过程的代码即可。
下面的例子中,虽然某些子过程只有一条语句,为与算法框架一致,仍使用单
4
独的子过程表示。
三广度优先搜索算法的例子
下面来看一些可以采用广度优先搜索算法求解的例子。
分油问题
一个一斤的瓶子装满油,另有一个七两和一个三两的空瓶,再
没有其它工具。只用这三个瓶子怎样精确地把一斤油分成两个
半斤油。
选择广度优先算法来求解分油问题可以得到通过最少步骤完成
分油的最优解。
分油过程中需要表示的状态是各个油瓶所装的油,这里用一个
数组来存放当前油瓶中的油,油瓶用数组下标区分,而油瓶中
的油则是数组元素的值。表示分油状态的特征的结点应当包括
各个油瓶的状态和结点的来源,也就是扩展出它的父结点。因
此用一个自定义数据类型来表示。
分油过程中,要将油从一个油瓶倒入另一个油瓶,可能的情形
只有 9 种,每种情形的序号与油瓶编号的关系如下表所示,这
也是一个节点可能扩展的 9 种情形。
!结点数据结构
,%&*+ !当前油瓶中的油
*+ !结点的父结点
5
剩余48页未读,继续阅读
资源评论
老帽爬新坡
- 粉丝: 82
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功