教程教案讲稿search-day2

搜索day2

更快地搜索1.双向BFS2.id-dfs(迭代加深搜索)3.简单的剪枝双向BFS双向广搜其实就是在BFS的基础上多了一个搜索方向。简单的搜索只是从出发点开始扩展，直到遇到终点时结束，但是双广是从出发点和终点同时开始扩展搜索，直到两方扩展边相遇时结束适用于初末状态都已知的广搜尽管理论比较简单，但是实现起来还是比较麻烦，码量略大双向BFS双广索达到的效果是不容忽视的，若只是用简单的单向搜索对一个平面图进行扩展搜索，当其半径达到一定程度时让内存吃不消，而且单向扩展还会因为搜索了太多不必要的空间而导致时耗大大增加。双广可以同时优化其两方面的不足，因为可以从一个简单的圆面积公式理解：R^2>=(R/2)^2+(R/2)^2(R为起点与终点的搜索长度)例题：HOJ1868题目大意：一个3*3的9方格中，其中八个格子填放了1-9中的数(不重复)，第九个为空格，给出方格的初始状态和目标状态，要求找出从初始状态移动到目标状态的最少移动次数。(初始状态)(目标状态)分析：1.用两个队列，分别从始态和终态进行bfs。队列中保存的是每一个状态，每一个状态可以用一个一维或二维数组保存(一个队列也可以，大家自由发挥)。2.双广时，两个队列交替进行扩展，且每次要扩展一层(一圈一圈的向外扩展，直到两个圈相遇)。3.用Hash记录已访问过的状态关于hash,见传送门：具体可以参考解题报告2023/1/102.id-dfs迭代加深搜索，实质上就是限定下界的深度优先搜索。即首先允许深度优先搜索K层搜索树，若没有发现可行解，再将K+1后重复以上步骤搜索，直到搜索到可行解。迭代加深搜索算法就是仿广度优先搜索的深度优先搜索。既能满足深度优先搜索的线性存储要求，又能保证发现一个最小深度的目标结点。从实际应用来看，迭代加深搜索的效果比较好，并不比广度优先搜索慢很多，但是空间复杂度却与深度优先搜索相同，比广度优先搜索小很多。有些题深度无限，而bfs却MLE时，可以考虑用一下id-dfs比如vijos1308埃及分数。2023/1/10id-dfs其实写起来也非常简单。for(dep=1;dep<=max_dep;dep++)dfs(**);或者while(true){ dep++;dfs(**)}就这样枚举一下深度的限界即可。(我一般习惯这么写的。其他写法也可以。)

2023/1/10例题：埃及分数vijos1308对于给定的分数a/b用1/c[1]+1/c[2]+1/c[3]...的形式表示，如2/3=1/2+1/6对于a/b表示方法可能有多种。我们认为加数少的比加数多的好，加数个数相同的，最小的分数越大越好。如19/45=1/3+1/12+1/180

=1/3+1/15+1/45

=1/3+1/18+1/30=1/4+1/6+1/180

=1/5+1/6+1/18.最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。PS请注意一下。。vijos虽然题目上没有要求。。但是好像数据要求的是当最小的相同时比较第二小的，使第二小的分数越大越好，再比较第三小。。2023/1/10分析:这个题显然不能做普通的dfs因为深度无限。但是如果做bfs的话空间上又不够。所以就考虑用id-dfs。3.剪枝深度搜索编程简单，程序简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，倘若不加优化，其时间效率简直无法忍受；广度优先搜索虽然时间复杂度比前者低一些，但其庞大的空间需求量又往往让人望而却步。

所以，对程序进行优化，就成为搜索算法编程中最关键的一环。

下面所要讨论的便是搜索算法中优化程序的一种基本方法------“剪枝”。剪枝1.剪枝就是在进行搜索(BFS,DFS)前预先进行判断这条路是否可行。如果能预先判断出此路不通，就不必再进行搜索了。从而节约了时间和空间。2.当然，不是所有的枝条都可以剪掉，这就需要通过设计出合理的判断方法，以决定某一分支的取舍。剪枝很灵活，没有固定的方法，但总的来说要遵循三个原则，即正确性、准确性、高效性。剪枝具体理论性的东西，大家可以去阅读包里的剪枝进阶的论文这里简单介绍一道经典的剪枝题作为例子HOJ1049Sticks【题意描述】

给出N根小木棒（以下称小棒）的长度Li，已知这N根小木棒原本由若干根长度相同的长木棒（以下称原棒）分解而来。要求出原棒的最小可能长度。【数据范围】

木棒数N<=64

任意小棒长度Li<=50分析：由小到大枚举所有可能的原棒长度，通过深度优先搜索尝试小棒能否组合成原棒，一旦检验成功则算法结束，当前原棒长度即为最小可能原棒长度。大家可以先写一个裸的DFS试试，再思考一下哪些地方可以剪枝。Hints:1.显然，枚举可能的长度时，应从给出的各小棒中最长的长度MAX开始枚举。另外设所有棒长度和为SUM，SUM应该能被MAX整除。2.深搜时优先选较长的棒，可以大大减少可行的搜索状态。所以DFS前可以先排序。3.对于长度相同的两个棒，如果第一个棒不成功，第二个棒就不必再搜了。。。。。。。这题还有很多可以剪枝的地方，大家可以看sticks剪枝经典.doc可以自行尝试哪些剪枝是必要的，哪些是效率不高的，体会优化的效果。今日题单：八数码(HOJ1868)由于