首页 > 代码库 > 夏令营讲课内容整理 Day 4.

夏令营讲课内容整理 Day 4.

2024-11-22 02:41:39   203人阅读

本日主要内容就是搜索（打暴力
搜索可以说是OIer必会的算法，同时也是OI系列赛事常考的算法之一。
有很多的题目都可以通过暴力搜索拿到部分分，而在暴力搜索的基础上再加一些剪枝优化， 就有可能会拿到更多的分数。
有句话说的好嘛，骗分过样例，暴力出奇迹。
真的可以出奇迹的，只要你用得好。
 
1.搜索的概念
在一个给定的空间内，运用一定的查找（遍历）方式，直到找到目标解（状态）的过程，我们称之为搜索。
搜素是尝试性的，搜索是无脑的，搜索是朴素的，搜索在很多时候是显然的，搜索应该总是暴力的。但搜索也是很常用的。
通常我们要把搜索的解空间划分成几个阶段（可能是抽象的），或者说是若干个状态，然后去按层或者按深度进行遍历，并尝试寻找可能的解。
搜索树。何为搜索树？我们想象一个搜索的阶段，首先，我们在初始位置作为起点开始我们的搜索过程，每到达下一个阶段，这棵树便会向下扩展。在同阶段扩展其他节点，这棵树便会拥有分叉，直到我们遍历完整个解空间，我们搜索的整个过程便记录在了搜索树里，而我们要找的解应该就在搜索树的某个叶子节点上，或者宣告无解。
 
2.常见的几类搜索问题
    • 排列问题：枚举1~n的排列
    • 组合问题：少年，你的这个物品，是要选呢？还是不选呢？
    • 路径问题：神奇海螺告诉我，下一步我该怎么走？
 
3.编写搜索算法时我们应该考虑到的问题
    • 我应该用什么搜索算法
    • 我这样写能不能保证一定出解
    • 我这样写找到的解是不是最优
    • 如果不是最优，那要如何才能找到最优解
    • 求解的效率如何（别想太多，搜索的时间复杂度一般都是指数级
 
我重点说一下深度优先搜索（DFS）和广度优先搜索（BFS）。
还有迭代加深算法和A*等略微丧病的搜索，我也会提一下
（今年没讲双向广搜啊。。
（当然也会有爬山法，模拟退火法，遗传算法等玄学搜索算法，仅供装逼
 
4.DFS
不撞南墙不回头，撞了就掉头，一冲到底不服输。
（好了DFS讲完了
我才没有那么不负责任。。
深度优先搜索，我们的思路就是只要能扩展，就一直向深处扩展，直到走不动，这时候要进行一步「回溯」操作。这个操作通常用递归来进行，当然也有非递归形式，不过不常用。
深度优先搜索的优点是代码量通常相对比较少，框架相对固定，而且比较容易理解，占用空间较小。在数据量比较少的时候可以很快出解。
但它的缺点也是明显的，在数据量大的时候遍历整个解答树会非常慢，递归层数过多也有可能引起爆栈。并且，找到的第一个解在某些时候并不一定是最优解，而只是可行解之一。
很多书上喜欢给一个DFS的大体框架，用来告诉初学者这种算法大概长什么样。那我也给出一个大体的DFS框架吧。。
 1 void dfs(int dep){
 2     if (dep==n+1){
 3         //执行输出操作
 4         return; 
 5     } 
 6     //可以在这里加一些特殊边界什么的，最后直接return就好 
 7     for 枚举每个可能的位置或者决策或者方案{ 
 8         //可以在这里加一些剪枝什么的 
 9     
10         if (这个方案合法){
11             打标记
12             dfs(dep+1); 
13             删除标记//这个时候已经回溯了 
14         } 
15         
16     }
17 }

 

 
其实不难理解。递归进入下一层，判断是否已经到达边界，如果还不是边界就按照一定的规则，取遍所有可能的方案，作为当前状态。
同时我们可能需要「打标记」操作方便我们「回溯」。打标记，便是记录某个数或者某个点是否走过，当我们回溯的时候应该把这个标记擦掉，避免影响之后的搜索。
多思考思考。
举个例子吧。99%的OIer都会的DFS：生成全排列
我会我会！next_permutation!
。。。把那个用STL的拖出去毙了，这里是搜索专场！
 1 void dfs(int now) {
 2     if (now == n) {
 3         for (int i = 0; i < n; i++)
 4             cout << a[i] << " ";
 5         cout << endl;
 6         return;
 7     }
 8     for (int i = 1; i <= n; i++)
 9         if (!check[i]) {
10             a[now] = i;
11             check[i] = true;
12             dfs(now + 1);
13             check[i] = false;
14         }
15 }

 

 
当然，生成全排列也可以用栈，非递归地完成。不过这不常用。
 
思考：如果我要生成1~n的组合呢？
 
 
再来一个99%的OIer都见过的例题，八皇后。
下过国际象棋吧？没下过也没问题，这题不需要你了解多少国际象棋规则。
一个8*8的棋盘，摆放八个皇后，要求这八个皇后中的任意两个不能位于同行同列同对角线，求方案数。
答案是92.
如果你打算实现一下这个搜索解的过程，并且不加任何的优化，也就是说，把八个皇后在所有可能的位置都枚举一遍，并判断是否可行。我可以说的是，上述方法完全正确，但是。。这程序可能要跑个一两年吧。。。
考虑一下优化。既然要求任意两个皇后不能位于同行同列同对角线，那么我们在放第n+1个皇后时，肯定不能在第n个皇后的同一行和同一列，在搜索即将要扩展至此的时候肯定不可行，我们就应该「回溯」。这样只需要判断任意两个皇后是否处在同一对角线就好了。
给一个伪代码：
 1 void dfs(int dep){
 2     if (dep==n+1){
 3         //输出方案 
 4         return; 
 5     }  
 6     for 枚举第dep行的皇后的可能位置{ 
 7     
 8         if (这个位置合法){
 9             打标记
10             dfs(dep+1); 
11             删除标记
12         } 
13         
14     }
15 }

 

 
5.Floodfill算法
又叫灌水法，填充法。
来一道例题：有一个n * m的点阵，有一些点是陆地，其他点是海洋，一共有多少块陆地？
这个算法其实类似于DFS，若要找到某个点所在的起点，就以此点开始DFS，遍历与它联通的所有点，如果枚举到的点没有被访问过并且是陆地，就可以打标记扩展。
 
6.BFS
按层搜索，广度优先，队列储存，首解最优。
其实可以这样想一下遍历解答树的过程：从根节点出发，找到所有与之相连的第一层节点，依次遍历，遍历的同时找到扩展到的下一层节点，储存起来方便下一步搜索，这样就是一个正常向的BFS过程。
一层一层地慢慢展开，每个节点到根节点的距离是慢慢增加的，而不是像DFS那样一直走到最深处再考虑往回走，所以BFS找到的第一个解一般就是最优解。
缺点的话，占用空间是比DFS大一些的，而且框架比DFS要长一些。。
之前说到的拓扑排序，便是一个BFS的过程。
 　　大致的框架：
　　 
 1 void bfs(int s){
 2     queue<int> q;
 3     q.push(s);
 4     vis[s] = true;
 5     while (!q.empty()){
 6         int u = q.front();
 7         q.pop();
 8         for (遍历所有与u相邻的节点){
 9             if (当前找到的扩展节点为解){
10                 执行输出操作 
11             } 
12             
13             if (!vis[u]){
14                 q.push(u);
15                 vis[u] = true;
16             }
17         }
18     }
19     return ;
20 }

 

　　
然后就是有一些对DFS和BFS进行优化的算法，不过实际应用当中用的比较少，我稍微写一下思想。
 
7.迭代加深搜索（就是那个所谓的A*
其实可以把它理解为集DFS占空间小和BFS首解最优两种特性于一体的一种搜索算法。先给DFS一个比较小的深度限制，然后逐渐增加深度限制，直到找到解或找遍所有分支为止。
 
8.启发式搜素
有效摒弃了DFS与BFS的无脑搜索缺点。利用一个“预判”引导搜索方向，就好像人走迷宫预先判断哪里很显然是死路那样，减小搜索范围。
启发式搜索的强度取决于我们“预判”的程度。
如果预判程度太高，虽然能大大减小工作量，但会有可能把本来应该是能找到最优解的道路剪掉，导致我们找不到最优解。
如果预判程度太低，会导致事倍功半，性能上与BFS差不了多少但是写起来可比BFS麻烦多了。所以我们要尽量合理地使用启发方式。
其实这里有一个评价函数f，用来评估我们的行走决策。这里只给出思想，如果有想深入了解此算法的同学可以自行查阅相关资料。
 
9.（据说可以拿来装逼的算法
爬山法，模拟退火，遗传算法
我当时是懵逼的。这我真不会。
 
概念什么的写的很少就是了。。搜索这东西得拿题来多写才行。。
也有可能是我太弱了吧。。
 
 

夏令营讲课内容整理 Day 4.


联系
我们