资源描述：
《最新Handout-16教学讲义PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Handout-16内容提要深度优先搜索POJ2815城堡问题POJ1011棍子问题例题：POJ2815城堡问题右图是一个城堡的地形图。请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。城堡被分割成m×n(m≤50，n≤50)个方块，每个方块可以有0~4面墙。比如，对于样例输入的标记1122333111234311153531555553从而一共有5个房间，最大的房间（1）占据9个格子room[i,j]的表示和生成过程表示：从方块(i,j)可达的方块的标记初始时，room[i,j]的每个方块都未标记结束时，room[i,j]
2、的所有方块都被标记生成过程从东、南、西、北四个方向分别递推每一次递推，使得room[i,j]中被标记方块的数量加1关键：对任何一个方块，东、南、西、北四个方向的递推都要做到没有遗漏，可以使用一个队列，保存从已标记方块可达的那些方块每次从队列中取出一个方块：东、南、西、北四个方向可达、且未被标记的方块继续放入队列中策略深度优先搜索(本讲内容)：每次从队列中取方块时，总是取最后放入的那一块广度优先(下一讲介绍)：每次从队列中取方块时，总是取最早放入的那一块room[i,j]生成过程的特点room[i,j]={(ij)}room[i-1,
3、y]room[i+1,y]room[i,y-1]room[i,y+1]对方块(ij)标记后，再求解子问题room[i-1,y]、room[i+1,y]、room[i,y-1]、room[i,y+1]子问题room[i-1,y]、room[i+1,y]、room[i,y-1]、room[i,y+1]一旦生成，就与room[i,j]独立room[i,j]不需要用到room[i-1,y]、room[i+1,y]、room[i,y-1]、room[i,y+1]的解注意该问题解决策略与递归策略、动态规划策略的区别，在这两种解题策略下，解决
4、room[i,y](标记方块(ij))时要依赖room[i-1,y]、room[i+1,y]、room[i,y-1]、room[i,y+1]的结果按照递归的策略：先分解出room[i-1,y]、room[i+1,y]、room[i,y-1]、room[i,y+1]并解决之，再解决room[i,j]按照动态规划的策略：先解决room[i-1,y]、room[i+1,y]、room[i,y-1]、room[i,y+1]，再解决room[i,j]搜索的过程：形式化描述两个状态的集合:未处理完的状态:已处理的状态状态的处理:有顺序的尝试备
5、选动作,每一次的尝试都演化出另一个状态已处理的状态:全部备选动作都已经尝试一个树结构:状态之间的演化关系递归的出口为空演化出目标状态S*演化出的状态不属于搜索的难点状态的表达状态演化关系树的表达当前状态的备选动作集合、以及其中已经尝试的动作和未尝试的动作影响搜索效率的因素两个状态的集合:未处理完的状态:已处理的状态判重：每次演化出一个状态s时，s是否属于或者剪枝：状态s的任意演化结果是否都属于属于，则剪枝演化出来的状态数量：的大小深度优先搜索(Depth-First-Search)将整个问题空间表示为一颗树。每
6、个顶点表示一个问题顶点的子节点表示对该问题的分解所有顶点都解决后，整个问题就解决了问题求解顺序：从图中某顶点v出发访问顶点v依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止深度优先搜索：形式化描述两个状态的集合:未处理完的状态:已处理的状态从中选择被演化状态的原则：离初态S0最远的状态sS0到s的距离：从S0到达s使用的动作数量实现方法：用stack表示每次取stack顶部的状态
7、演化每次演化出的状态s若不属于，则s将压入stack的顶部如何实现深度优先搜索？假定有两个二维数组nData,nMark分别存放输入数据和标记数据，则深度优先搜索可表示为voidmark(intx,inty,intnID)其中(x,y)为当前的位置，nID为当前的标记则可以用递归来实现深度优先搜索分别按{左、上、右、下}的顺序遍历，若其与邻居间没有墙，则以其邻居作为新起点重新进行搜索示例程序代码:#include#include#includeusingnamespacest
8、d;int**nData;int**nMark;voidmark(intx,inty,intnID){if(nMark[y][x])return;//alreadymarkednMark[y][x]=nID;if((nD
