搜索讲座课件

1、搜索FZUACM集训队 陈顶搜索FZU某大牛说过，一切题目皆搜索，只不过搜索的空间，范围不同而已在比赛中碰到的题目其实很多都是搜索题，只不过搜索的范围不同，有的只能盲目地搜索，有的可以在小范围内搜索搜索就是给出初始状态和目标状态,以及一些约束条件,要求寻找在符合这些约束条件的情况下,从初始状态到目标状态的解搜索的分类暴力枚举（完全盲目的搜索所有可能的状态，没人不会吧，这里不再赘述）深度优先搜索（DFS）广度优先搜索（BFS）启发式搜索A*IDA*较为复杂的智能搜索，这里不做介绍暴搜这恐怕是大家最喜欢的算法了，想不出来，就暴力！最土最土的暴力就是枚举了即枚举所有可行解USACO Prime Cr

2、yptarithm没有什么好说的，对于被乘数和乘数，枚举所有给出的数字，O(105)，完全可以接受当然，根据算式的特点还可以进行相应的剪枝剪枝何谓剪枝？剪枝就是搜索过程中把不必要，不可能的状态去掉，不必列入考虑的范围就像走迷宫时已经知道哪些路是死路，不继续往下走一样深度优先搜索(DFS)在深度优先搜索中,从初始节点开始扩展, 总是先扩展最新产生的节点.这就使得搜索沿着状态空间的某条单一的路径进行下去,直到搜索出符合我们要求的目标节点。因此,深度优先搜索第一个找到的解并不一定是问题的最优解,要综合所有的解,才能确定哪个解为最优解.与栈性质相似通过递归实现经常需要剪枝回溯，纯暴力一般会超时USAC

3、O Superprime Rib直接DFS 19，加入当前数末尾，并判断是不是素数，是则递归处理下一位数，不是则回溯，直到位数n。加几个剪枝1.首位只能是质数2 3 5 7 2.其余位只能是1 3 7 9 （为什么？）3.若n=1，直接输出2 3 5 7USACO Superprime RibN皇后问题搜索中一个经典问题在一个N*N棋盘上放置N个国际象棋的皇后，使得相互不攻击，求放置方案数暴力枚举显然超时我们使用几个bool数组记录该行，该列，该对角线是否有皇后，每次搜索的时候只要扩展没有皇后的状态即可，这样一来优化了不少但是N稍微大一点还是受不了TLE考虑对称性将棋盘对折，一个方案可行，那么

4、与这个方案对称的方案也可行剪掉一半状态了N再大，还是TLE其他优化位运算刘汝佳黑书上提到启发式修补（相当深奥）Dancing linkN皇后问题表达式求解总共最多就11个整数，10个符号只有两种符号|和&所有可能的状态210完全在1s可承受的范围之内，暴力枚举！如何实现？DFS表达式求解从第一个数字后面的第一个符号开始向后拓展，逐层深入，对于每层，要拓展的状态只有两种：|或&程序的递归框架出现表达式求解Void dfs(int x)if (x=n).;return;/到最后一层，计算表达式并回溯f=|;/分别拓展两种状态dfs(x+1);f=&;dfs(x+1);Equation这题规模有点大

5、，像刚才那样暴力枚举可能会超时，不过答案只有19*10种，我们可以打表怎么打？和刚才那题一样，DFS，对于每层，向下拓展只有3种状态，+或-或 程序框架类似DFS深度优先搜索所遵循的搜索策略是尽可能“深”地搜索。在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续下去。当结点v的所有边都己被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。 void dfs(i)for i:=1 to r do if 子

6、节点 mr 符合条件 产生的子节点mr入栈； if 子节点mr是目标节点 输出 else dfs(i+1); 栈顶元素出栈（即删去mr）；DFS框架广度优先搜索广度优先搜索（BFS）是从初始节点开始,利用这个状态去生成下一层的状态(可能不止一个),同时检查目标状态是否在这些新生成的状态中,如果在,则得到结果,否则,在利用这些新生成的状态继续反复扩展,直到目标状态出现。 先产生的状态先进行扩展.且要扩展出这种状态的所有下一状态.与队列性质相似，实现时常利用STL的queue最坏情况需遍历所有可行状态USACO Mothers Milk和FOJ的等分液体类似3个桶的容量最大为20，而牛奶总量一定，

7、可能的状态不超过20*20*20种可以开一个三维bool数组can212121记录状态，canijk表示A桶i升牛奶，B桶j升，C桶k升这种状态是否可达初始状态为can00c=true目标状态为求所有k，满足can0c-kk=true从初始状态一遍BFS即可得出解PKU 1915 Knight Moves 广度优先搜索有一类题目就是最短路问题，当然这里规模都比较小像小鼠迷宫那样一格一格走的模型像这题这种马走方格的模型给出起点和终点，求最少步数Distnm保存从起点到地图各点的最短距离初始状态Dists.xs.y=0，目标状态Diste.xe.y搜索时按照马的走法每次向八个方向扩展状态以此题为例

8、初始化：清空队列，Dist数组赋初值为无穷大，Dists.xs.y=0，s入队列While (队列非空） 队首元素出队，作为当前状态 向八个方向扩展状态，并判断是否超出边界 若当前状态的dist+1扩展状态的dist 则更新扩展状态dist，扩展状态入队目标状态Diste.xe.y即为所求 BFS 框架 CDGGs knight广搜常用于求最短路中这道比较经典的广搜题首先对于棋盘每个点(x,y)，要求出到所有点的最短距离，用distxyij保存，这需要做n*m次BFS，每次BFS就是一次求最短路的过程对于CDGG，做一次BFS，求出CDGG到每个点的最短距离CDGGs knight我们要做的事

9、1.确定集合点2.确定去驮CDGG的那个骑士，或者让CDGG自己走3.如果有人驮CDGG，还要确定CDGG和那个骑士在哪里碰面CDGGs knight如果所有的不确定值都用枚举的话，超时将不是一般的严重几个剪枝1.确定去驮CDGG的那个骑士和大家的集合点以后，如果其他骑士到集合点的最短路之和已经大于当前最小的答案，那么直接退出，不必枚举CDGG和驮他的骑士的集合点CDGGs knight2.王和骑士的相遇点可能出现在哪些位置上？显然王走的比骑士要慢，那么应该尽量要让王少走。不难发现，相遇点只应该在王的附近很短的距离以内。估算一下，相遇点就在王的坐标加减2的范围内枚举就可以了加上这两个剪枝，顺利

10、AC Reversi Game 复活赛中我的一道题题由于棋盘比较小4*4，并且只有0或1两种状态，所以共有216种状态，可以承受从起始状态到目标状态的拓展，很明显，BFS问题Reversi Game 对于每一种状态，将其表示成一个二进制数，状态之间的转换即二进制数某特定的两位上01的交换已知起始和终止的二进制数，求最小转换步数Reversi Game 初始时初始二进制数入队每次拓展时取队首元素进行拓展枚举交换的位，16种枚举与其交换的位，上下左右，4种每次拓展16*4个状态注意判重，去除重复的状态找到目标状态即退出，记录下步数Reversi Game 由于使用二进制数表示状态，那么可以使用位运

11、算加速主要处理1个数的两位交换Reversi Game void reser(int i,int j,int &num) /交换num的i,j两位int i,j,iz,jz; iz=num&(1i);jz=num&(1j); if (iz) num|=(1j); else if (jz) num-=(1j); if (jz) num|=(1i); else if (iz) num-=(1=0地图上0的地方不能走！横着的时候占两格，都不能为0！从起始状态到目标状态过程中，不能经过目标状态！只有最后才可以！当然只能是竖起来的时候才要考虑相当恶心的题题BloxOrz 搜索的优化很多问题会有比较复杂的情况和比较特殊的约束条件,很容易就会TLE.优化就是使得我们在搜索过程中尽量去除不必要的状态,使得尽可能快的找到目标状态.常用优化方法1.判重去除和以前相同的状态,避免重复的搜索空间允许的话 直接利用数组保存Hash,二叉搜索树等查找复杂度为O(nlgn)的数据结构来保存利用二进制数的位来保存常用优化方法2.加入记忆化对于某些问题，已经搜索过的状态记