第13讲广度优先搜索算法_第1页
第13讲广度优先搜索算法_第2页
第13讲广度优先搜索算法_第3页
第13讲广度优先搜索算法_第4页
第13讲广度优先搜索算法_第5页
已阅读5页，还剩8页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

第13讲广度优先搜索算法BFS2014.05.25Dfs最基本的框架：Proceduredfs(i:当前状态x[i]）beginif当前状态i是目标then处理；if越界退出；

按k个规则扩展新状态xx；if状态xx符合要求thenbegin

记下状态x[i+1]=xx；[标记新状态，避免重复走；]dfs(i+1:状态x[i+1]);//新状态作为新起点继续搜索[去掉标记，供后面继续走；]end;end;【问题描述】

在n×n的国际象棋盘上，放置n个皇后，使任何一个皇后都不能吃掉另一个,需满足的条件是：同一行、同一列、同一对角线上只能有一个皇后。求所有满足要求的放置方案。4皇后问题【输入】一个正整数n。【输出】每行代表一种放置方案：第i行的第一个数是i，表示第i种方案，后面一个冒号，然后是用空格隔开的n个数，其中第i个数x[i]表示第i行上的皇后放在第x[i]列.【样例输入】4【样例输出】1:24132:31424皇后的放置方案如下：****12341234****12341234（2，4，1，3）（3，1，4，2）搜素树深度优先搜索dfs广度优先搜索bfsBFS：广度优先搜索算法（宽度优先搜索算法）BFS，其英文全称是BreadthFirstSearch利用队列数据结构（FIFO）解决从初始状态到最终状态最少步骤问题head=0：队列的首指针；tail=1：队列的尾指针；Quene[1]:初始结点;Whilehead<taildo//还有未扩展的结点，队列不空

BeginInc（head）；//移动队列的首指针：出队列记录head状态；

Fori=1tomethoddo//按规则扩展下一层新的子结点

if条件满足thenBegin

生成新的结点;if新结点队列中没出现过then保存新结点（入队列）；

if新结点是目标结点thenprint(tail)搜索结束；

EndEnd；Print(-1);//无解BFS的基本框架：1.最少换乘次定n(<=100)个城市及城市间的交通路线（双向），每列火车只能在固定的两个城市间运行，也就是说从城市A到城市B，如果中间经过城市C，则要从A到C后，必须在C处换乘另一辆火车才能到达B。求从1号城市到n号城市的最少的换乘次数。从1到10，最少换乘1次。输入：10151415191643535791069623878710210810输出：12.七数码问

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论