DFS-BFS

DFS&[e-mail]基本概念搜索算法：在问题的状态空间中寻找特定的目标状态以及到达此目标状态的途径的系统方法。。。解路径搜索空间问题的状态空间DFS(DepthFirstSearch)0131211232221扩展结点时注意剪枝堆栈法下一次扩展的是本次扩展出来的子节点中的一个DFS(con...)回溯法:voidDFS(intcurNode,intcurDepth,intmaxDepth){if(curDepth==maxDepth)return;for(inti=0;in;++i){intnewNode=Expend(curNode,i);if(newNode==target)return;DFS(newNode,curDepth+1);}return;}迭代式DFS(ID_DFS):IterativeDeepeningDFSfor(intdepth=1;depthmaxDepth;++depth)DFS(node,0,depth);BFS(BreadthFirstSearch)队列法下一次扩展的是本次扩展的节点的所有子节点01312112322210111213232221可以解决的问题DFS最优值(比如A到B的最短路径值)BFS最优解(A到B的最短路径的轨迹)典型例题ZOJ1002zstu1017有一幅n×n的地图，用‘X’表示此处有一堵墙，用‘.’表示此处为空地，已知碉堡可以朝四个方向射击，但是不能穿墙，下面求在给定的地图上最多能放多少个碉堡并且两两间可以免受攻击。注:图(1)是某一给定的原始图，其它的是几种合法的放置，其中图(2)是放置的碉堡数为最多。(1)(2)(3)(4)(5)算法选取：此题是n皇后的模型。放置一个碉堡后，此碉堡与该行或列中的第一个墙的区域都不能再不能放置碉堡了。我们采用回溯法来实现深度搜索。合法位置：用N元组statu[0:N]表示某点处的势力statu[i..j1]++;//放置statu[i..j2]--;//撤消statu[i]=0:表示位置i处可以放置碉堡statu[i]≠0:表示位置i处不可以放碉堡+++ZOJ1204(作为练习)对一给定集合U，求出所有的集合U的子集并且其和等于集合U中的某一个数，若存在多种情况，则按其子集的基数即加数的个数排列，然后按照加数的大小排列，且以等式的形式输出，若不存在这样的子集则输出“Can‘tfindanyequations.”。例如：6123546(6集合U的基数，后面的数为集合U)输出的结果为：1+2=31+3=41+4=51+5=62+3=52+4=61+2+3=6算法设计：这题采用迭代深度搜索，可以把加数的个数作为最大深度，并且出要按照加数的个数递增输出，加入变量d来控制搜索的深度，能保证算法找到的第一个解就是加数的个数是最小的。基本的模式为：for(intdepth=1;depthmaxDepth;++depth)DFS(node,depth);在本题中maxDepth可以做为加数的个数。同时要保证等式要按照元素的大小排列，因此首先要对集合U进行递增排序。ZOJ1136zstu1031给定N,x1,x2,…,xm，求N的最小的倍数，且只能由X1，X2，...，XM这几个数字构成。数学小知识：若x1x2x3%N＝t,x1x2x4%N＝t,且x3x4.若含x1x2x4前缀的数为N的倍数，则肯定不是最小的。算法设计：题目的要求是求得最优解，故用广度优先搜索可以解决此题。以位数为深度，先从小到大搜索1位数的情况，记录下每个数模N的情况，然后再从小到大的将数字添加到1位数的后面，扩展出2位数的情况，记录下每个数模N的情况……如果搜索一个数到某一位时，余数已经在这个数以前的搜索中出现，则说明出现循环，这个数就没有必要将这个数再继续扩展了。如此进行，直到出现余数为0为止，此时就求出了最小的倍数。采用的数据结构:树(n叉树)指向父结点练练手ZOJ1909ZOJ1204ZOJ1649ZOJ1675thanks…