下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 队列应用——广度优先搜索

队列应用——广度优先搜索.doc

队列应用——广度优先搜索

奔奔洛小奔
2017-09-26 0人阅读 举报 0 0 暂无简介

简介:本文档为《队列应用——广度优先搜索doc》,可适用于IT/计算机领域

队列应用广度优先搜索队列应用广度优先搜索如图:求出从节点到节点的最短路径的长度(到最少的边数)。使用计算机求解的问题中有许多问题是无法用数学公式进行计算推导找出答案的。就像这一题需穷举从节点到节点的所有路径才能找到答案。穷举是最朴素的搜索。穷举所有路径面对大规模数据将是很可怕的采用广度优先搜索法(BFS)就不必穷举所有路径大大提高效率。用广度优先搜索法解答此题的过程:先搜索所有节点中距节点最近的点节点(距离为)再搜索与节点距离为的节点然后搜索与节点距离为的节点与节点中某点距离为且尚未搜索过的节点再搜索距节点距离为的节点与节点中的某点距离为且尚未搜索过的节点由以上过程可以确定到的最短距离为(可以用反证法证明此结论的正确性)。整个过程如下图:可以看出搜索的过程是“一层一层”的从第一层开始每层的节点都会被“用”来产生下一层的节点当这一层的节点被“用完”后才用它们所产生的下一层节点来产生新的节点层而同一层的节点可以按任意顺序“使用”一般采用的原则是先生成的结点先“使用”。对“使用”一词更恰当的说法是“扩展”。广度优先搜索算法中为了便于进行搜索要设置一个表存储所有的节点为了满足先生成的节点层(节点)先扩展的原则存储节点的表一般设计成队列的数据结构。搜索过程中不断地从队列头取出节点进行扩展。对生成的新节点要检查它是否已在队列中存在还要检查它是否目标节点。如果新节点是目标节点则搜索成功程序结束若新节点不是目标节点并且未曾在队列中出现过则将它加入到队列尾否则将它丢弃再从队列头取出节点进行扩展。最终可能产生两种结果:找到目标节点或扩展完所有节点有找到目标节点。题一:求两点间的最短路径长度在一由n(<=n<=)个节点m(<=m<=n*(n))条边构成的图中求出节点s到t的最短路径长度。输入(inputtxt):第一行n,m,s,t接下来m行每行两个整数ij(<=i,j<=n)表示ij间有一条边。输出(outputtxt):S到t的最短路径的长度(从s到t经过的最少边数)若从s无法到达t输出分析:布尔数组bVisitedi非零表示节点i已在队列中为零表示尚未入队布尔数组bAdjij非零表示节点i与节点j之间有一条边否则无边队列q,队首iH,队尾iTstepi表示起点到节点i的最短距离。(数据见习题)源代码:#include<fstream>usingnamespacestdifstreamfin("inputtxt")ofstreamfout("outputtxt")constintLQ=,N=intbNoAns,bVisitedN={},bAdjNN={}intn,m,s,t,iH,iT,qLQ,stepN={}intInputDataAndInitialize(void)intBFS(void)intOutputAnswer(void)intmain(intargc,char*argv){InputDataAndInitialize()BFS()OutputAnswer()return}intInputDataAndInitialize(void){fin>>n>>m>>s>>tinti,jfor(m){fin>>i>>jbAdjij=bAdjji=}for(i=i<=ni)bAdjii=iH=iT=q=sbVisiteds=bNoAns=return}intBFS(void){if(q==t){bNoAns=return}inti,jwhile(iH<iT){i=qiHfor(j=j<=nj){if((!bVisitedj)(bAdjij)){qiT=jstepj=stepibVisitedj=if(j==t){bNoAns=return}}}}return}intOutputAnswer(void){if(bNoAns){fout<<"n"return}fout<<stept<<endlreturn}采用广度优先搜索算法(BFS)解答问题时需要构造一个表明状态特征和不同状态之间关系的数据结构这种数据结构称为结点(节点)。根据问题所给定的条件从一个结点出发可以生成一个或多个新的结点这个过程通常称为扩展。结点之间的关系一般可以表示成一棵树它被称为解答树。搜索算法的搜索过程实际上就是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的结点的过程。广度优先搜索算法中解答树上结点的扩展是沿结点深度的“断层”进行也就是说结点的扩展是按它们接近起始结点的程度依次进行的。首先生成第一层结点同时检查目标结点是否在所生成的结点中如果不在则将所有的第一层结点逐一扩展得到第二层结点并检查第二层结点是否包含目标结点对长度为n的任一结点进行扩展之前必须先考虑长度为n的结点的每种可能的状态。因此对于同一层结点来说求解问题的价值是相同的我们可以按任意顺序来扩展它们。这里采用的原则是先生成的结点先扩展。如果目标结点存在于解答树的有限层上广度优先搜索算法一定能保证找到一条通向它的最佳路径因此广度优先搜索算法特别适用于只需求出最优解的问题。当问题需要给出解的路径则要保存每个结点的来源也就是它是从哪一个节点扩展来的。对于不同的问题用广度优先搜索法的算法基本上都是一样的。但表示问题状态的结点数据结构、新结点是否目标结点和是否重复结点的判断等方面则有所不同对具体的问题需要进行具体分析。题二:有两个水桶编号为容量分别为A升,B升,还有一个数C对两个水桶可以有如下操作:FILL(i)将桶i(i=)充满DROP(i)将桶i(i=)中的水倒掉POUR(i,j)将桶i中的水倒入桶j中这个操作后桶j变满(桶i中可能还有剩余)或桶i变空(水全部倒入桶j中)问经过哪几个操作后能使其中一个桶里的水量达到C。输入:A,B,C(<=A,B,C<=,C<=MAX(A,B))输出:第一行最少操作数接下来每行为一个操作若无解只输出“impossible"样例输入:样例输出:FILL()POUR(,)DROP()POUR(,)FILL()POUR(,)分析:这个题目可以用bfs把它做出来对于两个桶的每一种状态我们都可对它进行六种操作即FILL(),FILL(),DROP(),DROP(),POUR(,),POUR(,),我们可以把它的每一种状态记录下来一层一层的往下扩展直到找到我们要找的容量为止。不过这里有一个麻烦就是要你输出得到容量C的过程。所以对于每一个结点我们都得对它设置一个pre指针使它指向其父结点等到我们找到正确的结果之后再沿着其父结点返回来找那条正确的路径。具体代码如下:有点长但思路简单到北大OnlineJudgeP提交。Potscpp#include<iostream>#include<string>usingnamespacestdintiAA,iBB,iCC输入的数据intInputDataAndInitialize(void)输入数据并初始化constintN=保存搜索树节点的队列的最大长度intiH,iT队列的首尾元素的下标intiAN桶的状态intiBN桶的状态intiPreNiPrej得到节点j的节点的下标intiOperatorNiOperatorj得到节点j的操作的序号constintM=intbFlagMM={}bFlagab判断水量为a水量为b的情况是否出现过intBFS(void)BFS主函数stringOPERATOR"FILL()","FILL()","DROP()","DROP()","POUR(,)","POUR(,)"操作intbNoAnswer有无解标志intOutputAnswer(void)输出intmain(intargc,char*argv){InputDataAndInitialize()BFS()OutputAnswer()return}intInputDataAndInitialize(void){cin>>iAA>>iBB>>iCCbNoAnswer=iH=iT=iA=iB=iPre=bFlag=OPERATOR="FILL()"OPERATOR="FILL()"OPERATOR="DROP()"OPERATOR="DROP()"OPERATOR="POUR(,)"OPERATOR="POUR(,)"return}intBFS(void){while(iH<iT){操作if((iAiH<iAA)(!bFlagiAAiBiH)){iAiT=iAAiBiT=iBiHbFlagiAiTiBiT=iPreiT=iHiOperatoriT=iTif((iAiT==iCC)||(iBiT==iCC)){bNoAnswer=return}}操作if((iBiH<iBB)(!bFlagiAiHiBB)){iAiT=iAiHiBiT=iBBbFlagiAiTiBiT=iPreiT=iHiOperatoriT=iTif((iAiT==iCC)||(iBiT==iCC)){bNoAnswer=return}}操作if((iAiH>)(!bFlagiBiH)){iAiT=iBiT=iBiHbFlagiAiTiBiT=iPreiT=iHiOperatoriT=iTif((iAiT==iCC)||(iBiT==iCC)){bNoAnswer=return}}操作if((iBiH>)(!bFlagiAiH)){iAiT=iAiHiBiT=bFlagiAiTiBiT=iPreiT=iHiOperatoriT=iTif((iAiT==iCC)||(iBiT==iCC)){bNoAnswer=return}}操作倒完if((iAiH>)(iBiH<iBB)(iAiH<=iBBiBiH)(!bFlagiBiHiAiH)){iAiT=iBiT=iBiHiAiHbFlagiAiTiBiT=iPreiT=iHiOperatoriT=iTif((iAiT==iCC)||(iBiT==iCC)){bNoAnswer=return}}操作倒满if((iAiH>)(iBiH<iBB)(iAiH>=iBBiBiH)(!bFlagiAiHiBiHiBBiBB)){iAiT=iAiHiBiHiBBiBiT=iBBbFlagiAiTiBiT=iPreiT=iHiOperatoriT=iTif((iAiT==iCC)||(iBiT==iCC)){bNoAnswer=return}}操作倒完if((iBiH>)(iAiH<iAA)(iBiH<=iAAiAiH)(!bFlagiAiHiBiH)){iAiT=iAiHiBiHiBiT=bFlagiAiTiBiT=iPreiT=iHiOperatoriT=iTif((iAiT==iCC)||(iBiT==iCC)){bNoAnswer=return}}操作倒满if((iBiH>)(iAiH<iAA)(iBiH>=iAAiAiH)(!bFlagiAAiBiHiAiHiAA)){iAiT=iAAiBiT=iBiHiAiHiAAbFlagiAiTiBiT=iPreiT=iHiOperatoriT=iTif((iAiT==iCC)||(iBiT==iCC)){bNoAnswer=return}}iH}return}intOutputAnswer(void){if(bNoAnswer){cout<<"impossiblen"return}intp,oN,to=for(p=iTpp=iPrep){oto=iOperatorp}cout<<to<<endlfor(p=top>=p)cout<<OPERATORop<<endlreturn}题三:八数码在×的棋盘上摆有八个棋子每个棋子上标有至的某一数字。棋盘中留有一个空格空格用来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为)找到一种最少步骤的移动方法实现从初始布局到目标布局的转变。输入格式输入初始状态一行九个数字空格用表示输出格式只有一行该行只有一个数字表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)样例输入样例输出注:完美地解答此题需应用一些数据结构和算法所以特别为此题生成了一些较弱的测试数据(见习题)。题四:字串变换(来源:noip提高组第二题。)已知有两个字串A$,B$及一组字串变换的规则(至多个规则):A$>B$A$>B$规则的含义为:在A$中的子串A$可以变换为B$、A$可以变换为B$„。例如:A$,'abcd'B$,'xyz'变换规则为:‘abc'>‘xu'‘ud'>‘y'‘y'>‘yz'则此时A$可以经过一系列的变换变为B$其变换的过程为:‘abcd'>‘xud'>‘xy'>‘xyz'共进行了三次变换使得A$变换为B$。输入格式A$B$A$B$$B$。。。。。。。所有字符串长度的上限为。输出格式若在步(包含步)以内能将A$变换为B$则输出最少的变换步数否则输出"NOANSWER!"样例输入abcdwyzabcxuudyyyz样例输出题五:聪明的打字员(NOI)阿兰是某机密部门的打字员她现在接到一个任务:需要在一天之内输入几百个长度固定为的密码。当然她希望输入的过程中敲击键盘的总次数越少越好。不幸的是出于保密的需要该部门用于输入密码的键盘是特殊设计的键盘上没有数字键而只有以下六个键:Swap,Swap,Up,Down,Left,Right为了说明这个键的作用我们先定义录入区的个位置的编号从左至右依次为。下面列出每个键的作用:Swap:按Swap光标位置不变将光标所在位置的数字与录入区的号位置的数字(左起第一个数字)交换。如果光标已经处在录入区的号位置则按Swap键之后录入区的数字不变Swap:按Swap光标位置不变将光标所在位置的数字与录入区的号位置的数字(左起第六个数字)交换。如果光标已经处在录入区的号位置则按Swap键之后录入区的数字不变Up:按Up光标位置不变将光标所在位置的数字加(除非该数字是)。例如如果光标所在位置的数字为按Up之后该处的数字变为如果该处数字为则按Up之后数字不变光标位置也不变Down:按Down光标位置不变将光标所在位置的数字减(除非该数字是)如果该处数字为则按Down之后数字不变光标位置也不变Left:按Left光标左移一个位置如果光标已经在录入区的号位置(左起第一个位置)上则光标不动Right:按Right光标右移一个位置如果光标已经在录入区的号位置(左起第六个位置)上则光标不动。当然为了使这样的键盘发挥作用每次录入密码之前录入区总会随机出现一个长度为的初始密码而且光标固定出现在号位置上。当巧妙地使用上述六个特殊键之后可以得到目标密码这时光标允许停在任何一个位置。现在阿兰需要你的帮助编写一个程序求出录入一个密码需要的最少的击键次数。输入文件(cleverin)文件仅一行含有两个长度为的数前者为初始密码后者为目标密码两个密码之间用一个空格隔开。输出文件(cleverout)文件仅一行含有一个正整数为最少需要的击键次数。输入样例输出样例

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/20

队列应用——广度优先搜索

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利