




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、广度搜索在程序设计中的应用深度优先: SLMN F F O P F Q F 广搜优先: SLOMF PQN FFF “广搜广搜”用来解决那类问题用来解决那类问题?用深度优先搜索找最优解时必须搜索完所有路径,即使一个目标用深度优先搜索找最优解时必须搜索完所有路径,即使一个目标结点在很浅的树枝上,也得等到它左边所有结点均被搜索后才能结点在很浅的树枝上,也得等到它左边所有结点均被搜索后才能找到它。用这种方法求某些最优解时,效率比较低。而广度优先找到它。用这种方法求某些最优解时,效率比较低。而广度优先搜索,能较好地解决这个问题。搜索,能较好地解决这个问题。广度优先搜索是最简便和常用的图形搜索算法之一,
2、从对图形的广度优先搜索是最简便和常用的图形搜索算法之一,从对图形的遍历来看,遵循遍历来看,遵循“从浅入深从浅入深”的搜索策略。在这种搜索过程中,的搜索策略。在这种搜索过程中,树上的结点扩展是沿着深度的树上的结点扩展是沿着深度的“断层断层”进行的,所以这种方法一进行的,所以这种方法一定能保证找到最短(步数最少)的解答序列。在不少题中要求找定能保证找到最短(步数最少)的解答序列。在不少题中要求找到经历步骤最少而达到目标的方案时,多采用此种搜索方法。到经历步骤最少而达到目标的方案时,多采用此种搜索方法。“广搜广搜”所用的数据结构所用的数据结构-队列队列为了体现先生成先扩展的执行方式又能保留所有生成的
3、结点以待为了体现先生成先扩展的执行方式又能保留所有生成的结点以待进一步扩展,广度优先搜索在数据结构上引用了进一步扩展,广度优先搜索在数据结构上引用了“队列队列”结构。结构。队列是一种线性表,具有队列是一种线性表,具有先进先出先进先出的特点,对于它所有的插入和的特点,对于它所有的插入和删除操作分别仅在队列尾和队列首进行。定义两个删除操作分别仅在队列尾和队列首进行。定义两个“指针指针”变量变量head和和tail,分别用来指向队列的头和尾。初始结点先入队,头,分别用来指向队列的头和尾。初始结点先入队,头指针指向待扩展结点,每生成一个子结点,则尾指针指针指向待扩展结点,每生成一个子结点,则尾指针ta
4、il增加增加1,当前结点的所有子结点均生成后,头指针向后移动(即加当前结点的所有子结点均生成后,头指针向后移动(即加1),),位于位于head指针之前的(已被删除)为已扩展结点,指针之前的(已被删除)为已扩展结点,tail指向所有指向所有已生成结点的最后一个。若已生成结点的最后一个。若head指针大于指针大于tail指针,表示所有解指针,表示所有解答树上的结点已产生。如果目标结点仍求出现,说明答树上的结点已产生。如果目标结点仍求出现,说明“无解无解”。原理解析原理解析headtailsLOMFPQNFFF01122334678广度优先搜索的算法描述广度优先搜索的算法描述Procedure BF
5、S初始化,初始状态存入初始化,初始状态存入OPEN表;表;队列首指针队列首指针head:=0;尾指针;尾指针tail:=1;repeatfor I:=1 to max do /其中,其中,max为产生子结点的规则数为产生子结点的规则数 begin if 子结点符合条件子结点符合条件 then begin tail指针增指针增1,把新结点存入队列尾;,把新结点存入队列尾; if 新结点与原已产生的结点重复新结点与原已产生的结点重复 then 删去该结点(取消入队,删去该结点(取消入队,tail减减1)else if 新结点是目标结点新结点是目标结点 then 输出并退出;输出并退出; end e
6、nduntil (head=tail);广度优先搜索的注意事项广度优先搜索的注意事项(1)每生成一个子结点,就要提供指向它们)每生成一个子结点,就要提供指向它们父亲结点的指针。当解出现时,通过逆向跟踪,父亲结点的指针。当解出现时,通过逆向跟踪,找到从根结点到目标结点的一条路径。找到从根结点到目标结点的一条路径。(2)生成的子结点要与前面的所有已产生结)生成的子结点要与前面的所有已产生结点比较,以免出现重复结点,浪费时间,还可点比较,以免出现重复结点,浪费时间,还可能陷入死循环。能陷入死循环。(3)广度优先搜索的效率还有赖于目标结点)广度优先搜索的效率还有赖于目标结点所有位置情况,如果目标结点处
7、在比较深的层所有位置情况,如果目标结点处在比较深的层上时,需搜索的结点数基本上以指数增长。上时,需搜索的结点数基本上以指数增长。例例1:电子老鼠闯迷宫电子老鼠闯迷宫电子老鼠闯迷宫。如下图电子老鼠闯迷宫。如下图1212方方格图,找出一条自入口(格图,找出一条自入口(2,9)到)到出口(出口(11,8)的最短路径。)的最短路径。 12 /迷宫大小2 9 11 8 /起点和终点1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 1 11 0 1 0 1 1 0 0 0 0 0 11 0 1 0 1 1 0 1 1 1 0 11 0 1 0 0 0 0 0 1 0
8、0 11 0 1 0 1 1 1 1 1 1 1 11 0 0 0 1 0 1 0 0 0 0 11 0 1 1 1 0 0 0 1 1 1 11 0 0 0 0 0 1 0 0 0 0 11 1 1 0 1 1 1 1 0 1 0 11 1 1 1 1 1 1 0 0 1 1 11 1 1 1 1 1 1 1 1 1 1 11 223344455566667788899101112131415152322222125252424161617 1802026262619192727272828输入:输出:28数据结构定义:A1.maxn,1.maxn表示邻接矩阵Father1.maxn*max
9、n表示队列State1.maxn*maxn,1.2,1表示当前点的横坐标,2表示纵坐标,记录状态procedure bfs; var tail,head,k,i:integer; begin head:=0;tail:=1;state1,1:=px;state1,2:=py; father1:=0; /初始点状态 repeat for k:=1 to wayn do if check(statehead,1+dxk,statehead,2+dyk) /扩展子节点 then begin tail:=tail+1;/入队 fathertail:=head; statetail,1:=statehe
10、ad,1+dxk; statetail,2:=statehead,2+dyk; astatetail,1,statetail,2:=1;/判重标记 if (statetail,1=qx) and (statetail,2=qy)/是否为目标节点 then begin print(tail); tail:=0; end; end; until head=tail; end;例例2:骑士旅行骑士旅行在一个n*m (m,n=1) and (x=1) and (y=tail; end;例例3:翻币问题翻币问题有有N个硬币个硬币(6=N=w) and (n-statehead=5-w)/生成子节生成子节
11、点条件点条件 then begin tail:=tail+1; fathertail:=head; statetail:=statehead-w+5-w; for k:=1 to tail-1 do /判重判重 if statek=statetail then begin tail:=tail-1; break; end; if statetail=0 then /判断是否为目标结点判断是否为目标结点 begin step:=0; print(tail); tail:=0; end; end; until head=tail;例例4:最优乘车最优乘车 一名旅客最近到一名旅客最近到H城旅游,他很想去城旅游,他很想去S公园游玩,但如果从他所在的饭店公园游玩,但如果从他所在的饭店没有一路已士可以直接到达没有一路已士可以直接到达S公园,则他可能要先乘某一路巴士坐几站,再公园,则他可能要先乘某一路巴士坐几站,再下来换乘同一站台的另一路巴士下来换乘同一站台的另一路巴士, 这样换乘几次后到达这样换乘几次后到达S公园。公园。 现在用整数现在用整数1,2,N 给给H城的所有的巴士站编号,约定这名旅客所在饭店城的所有的巴士站编号,约定这名旅客所在饭店的巴士站编号为的巴士站编号为1S公园巴士站的编号为公园
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年短视频平台内容监管与平台经济报告
- 2025年文化遗产数字化保护与文化遗产旅游市场的营销策略报告
- 教育大数据在教育资源优化配置中的应用实践报告
- 2025年云计算服务模式演进与行业应用市场前景研究报告
- 2025年元宇宙社交平台游戏化设计:用户体验与互动体验报告
- 2025年元宇宙社交平台用户互动性与社交价值研究报告
- 2025年元宇宙社交平台虚拟现实设备兼容性与用户体验研究
- 2025年元宇宙社交平台虚拟社交活动策划与用户体验优化报告
- 2025年医院信息化建设医院图书馆管理系统初步设计评估报告
- 零售行业私域流量运营数据分析与效果评估报告
- 新交际英语(2024新版)一年级上册Unit 1~6全册教案
- 三家比价合同范例
- 2025年慢性阻塞性肺疾病全球创议GOLD指南修订解读课件
- GB/T 19077-2024粒度分析激光衍射法
- GB/T 44481-2024建筑消防设施检测技术规范
- 风险评估培训课件x
- 代牧牛羊合同模板
- 感术行动专项考核试题及答案
- DB34∕T 3468-2019 民用建筑楼面保温隔声工程技术规程
- 《西兰花先生的理发店》幼儿园小学少儿美术教育绘画课件创意教程教案
- 江苏省淮安市2023-2024学年八年级下学期期末数学试卷(含答案详解)
评论
0/150
提交评论