人教版 信息技术 必修1 搜索及优化课件（共56张ppt)

课件56张PPT。搜索及优化搜索是noip阶段甚至到noi阶段都非常重要的算法，在竞赛入门阶段是几乎每场比赛都需要使用的算法，而在的近年noip中，又常出现大暴搜代码题，成为noip冲击500分以上的挑战之一，例如noip2011manya游戏，noip2013华容道，noip2015斗地主。但是，搜索算法最重要的应用是写暴力，几乎所有noip阶段的题目都可以写出搜索算法
搜索算法是noip内容学习的基础，是必须掌握的算法之一。今天要讲的内容
深度优先搜索(dfs)
广度优先搜索(bfs)
迭代加深搜索
双向广搜
A*算法深度优先搜索 dfs深度优先搜索一般应用在需要遍历所有情况的搜索中，比广度优先搜索要简洁明了，内存占用较小
深度优先搜索可以方便的记录这个状态的所有信息，所以比较容易地实现剪枝
俗称的打暴力就是指这种算法，noip阶段一般情况下每道题都会给dfs的暴力分深度优先搜索 dfs深度优先搜索，简单的说就是不到南墙不回头，只要从这个状态出发还有合法状态，就继续扩展
来感性地认识一下dfs一棵树的过程。
深度优先搜索 dfs摘自王建德noip2014夏令营课件例题 八皇后问题在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。伪代码void dfs(int dep)
{
if (dep==n+1) { 输出方案 return;}
for (int j=1;j<=n;j++)
if 第dep个可以放置在第dep行第j列
{
vis[dep][j]=1; 记录第dep行第j列放置了一个一个皇后
dfs(dep+1);
vis[dep][j]=0; 消除影响
}
} 常用枚举方法枚举1~n的n!个排列
枚举1~n的2^n个子集
大家动笔写一写常用的枚举方法枚举所有排列
void dfs(int dep)
{
if (dep>n) { check(); return;}
for (int i=1;i<=n;i++)
if (!vis[i])
{
vis[i]=1; a[dep]=i;
dfs(dep+1);
vis[i]=0;
}
}枚举所有子集
void dfs(int dep,int tot)
{
if (dep>n) { check(tot); return;}
dfs(dep+1,tot);
a[tot+1]=dep; vis[dep]=1;
dfs(dep+1,tot+1);
vis[dep]=0;
}一轮省队集训day1 lyk的整数拆分大家用纸+笔或者用电脑写一下ll calc(int len)
{
ll ret=0;
if(len==1) return 0;
for(int i=1;i for(int j=i+1;j<=len;j++)
ret+=GCD[a[i]][a[j]];
return ret;
}void dfs(int pos,int now)
{
if(now==n) { ans+=calc(pos-1); return; }
for(int i=a[pos-1];i<=n-now;i++)
{
if(cannot[i]) continue;
a[pos]=i;
dfs(pos+1,now+i);
}
}广度优先搜索 bfs广度优先搜索一般应用在求至少需要几步，且状态可以比较容易记录的情况
作为一个sd的OIer，你在考省队选拔赛的时候有很大概率会用到。
广度优先搜索基于队列的储存结构，每次弹出队首的元素，并将扩展到的状态加入队尾，这样可以保证所有比x深度浅的状态都可以在x之前出队，并且可以保证所有点在深度最浅的部位被访问到。
以那棵树为例再来看一下bfs的过程
例题你有一个数x，还有一个数y，可以把x变为x+1,x-1,2*x，要求x时刻非负，并<=10^7,问最少几步变成y
xy均<=10^7
q[1]=X; dep[X]=1;
int h=0,w=1,mxn=10000000;
//q是一个队列，h,w分别表示队首队尾
while (h!=w)
{
int x=q[++h],y; if (x==Y) { printf("%dn",dep[x]-1); return 0; }
y=x+1;
if (y<=mxn&&!dep[y]) { q[++w]=y; dep[y]=dep[x]+1; }
y=x-1;
if (y>=0&&!dep[y]) { q[++w]=y; dep[y]=dep[x]+1;}
y=x*2;
if (y<=mxn&&!dep[y]) { q[++w]=y; dep[y]=dep[x]+1; }
}Floodfill算法有一个n*m的点阵，有一些点是陆地，其他点是海洋，问有多少块陆地，多少片海洋。模拟这个过程，就是一个点只能扩展到与它相邻的所有与它数字相同的点。
枚举所有的点，如果他没有被扩展到就以它为起点进行扩展
具体实现时要注意不要超出网格图的边界让我们来模拟一下搜索的过程
001110
001010
001110
000001
011011
010110让我们来模拟一下搜索的过程
Sea=1 land=0
221110
221010
221110
222221
211011
210110让我们来模拟一下搜索的过程
Sea=1 land=1
223330
223030
223330
222221
211011
210110让我们来模拟一下搜索的过程
Sea=2 land=1
223332
223032
223332
222221
211011
210110让我们来模拟一下搜索的过程
Sea=3 land=1
223332
223232
223332
222221
211011
210110让我们来模拟一下搜索的过程
Sea=3 land=2
223332
223232
223332
222223
211033
210330让我们来模拟一下搜索的过程
Sea=3 land=3
223332
223232
223332
222223
233033
230330让我们来模拟一下搜索的过程
Sea=4 land=3
223332
223232
223332
222223
233233
230330让我们来模拟一下搜索的过程
Sea=5 land=4
223332
223232
223332
222223
233233
232330让我们来模拟一下搜索的过程
Sea=6 land=4
223332
223232
223332
222223
233233
232332搜索的剪枝搜索的搜索树非常大，但是有很多状态是明显不会有解或者更新最优解的，遇到这种情况，我们显然不需要继续进行搜索
对暴力搜索的剪枝常常可以达到意想不到的效果，而也有极大概率成为比赛中关键的几分搜索的剪枝最基本的是有可行性剪枝和最优性剪枝
可行性剪枝就是在这个不可能成为合法解的时候剪枝
最优性剪枝就是在这个不可能成为最优解的时候剪枝省队集训某题LYK 有一个 n*m 的网格图，每个格子都填有-1 至 n*m-1 中的其中一个数表示它的颜色 且每个格子都有一个代价 ai,j。 它想选择一个四联通块，使得该四联通块中，存在至少 k 种不同的颜色，且不包含-1， 要使得所选的格子的代价和最小。
n,m,k<=4考虑最简单的暴力，枚举所有的网格是否选择，检查是否连通以及有k种及以上颜色
Question: 你会加什么剪枝?可行性剪枝：如果剩下的格子数+当前已有的颜色数最优性剪枝：如果当前花费的代价>当前的最优解，那么剪枝
在考场上加入这两个剪枝比纯枚举的暴力要多得不少分，也有神犇直接用搜索A掉了此题通过预处理加快搜索这是noip十分喜欢出的一种搜索方式，比如noip2013华容道通过预处理向前后左右移动所需要的步数，使这道大暴搜题目变成最短路问题，noip2015斗地主通过预处理出不考虑顺子时所需步数，进行复杂度很优的搜索。例题：机房里正在进行酣畅淋漓的cs大战。
突然，Oxer的电脑出现了故障，使他不能进行任何操作。
弱弱的heheda很高兴，因为她从来没有秒掉过Oxer。
Cs的场景可以看作一个n*m的矩阵，有一些格子是障碍物，不能通过，子弹也不能穿过。
heheda每秒可以向上下左右移动一个格子，然后开枪，攻击不浪费时间。
其实heheda的水平也没有那么菜，她可以瞬间秒掉在8个方向上的Oxer，但是不能穿越障碍物。
这是个千载难逢的好机会，请你们帮帮heheda，尽快秒掉Oxer，要不他的电脑就恢复正常了。
n*m<=10^5
你会怎么做？预处理出所有heheda能直接秒掉Oxer的位置，然后搜索heheda到这些位置的最短路迭代加深搜索一道题要求求步数最少的解，我们应该使用bfs，但是这道题又无法方便地记录所有可能的情况，又应该采用dfs。
解决方法是枚举深度进行dfs，同时也方便了剪枝。迭代加深搜索由于搜索是指数级别的，这样枚举不会太增加时间。
假设每次只扩展两个合法状态，设最终答案为n，耗费时间为2^0+2^1+……+2^n=2^(n+1)-1
Bzoj 1085 骑士精神在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士， 且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。
给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘： 为了体现出骑士精神，他们必须以最少的步数完成任务。如果无解或步数>15输出无解你会怎么做？一个较为显然的剪枝是如果当前的步数+与目标棋盘不同的位置个数>=最优解就剪枝
为什么？但是纯粹的深搜可能导致初始解非常大，导致剪枝效果不好。
看到最大步数只有15，那么我们可以套上迭代加深搜索来完成此题。
另外，这个算法也体现了A*算法的思想A*算法A*算法是一种高效的启发式搜索方式，可以较快地找到最优解，时间复杂度玄学，但可以尝试。A*算法f(x)=g(x)+h(x)
F(x)表示经过状态x的代价的估计值
G(x)表示走到x状态实际产生的代价
H(x)表示从x状态走到终止状态的估计代价
每次选择f(x)最小的状态进行扩展（用堆维护）
要求h(x)要小于等于实际走到点x所需要的步数，保证搜索出的是最优的
使h(x)与实际需要的步数尽可能接近，尽可能加快搜索速度
在骑士精神一题里，f(x) g(x) h(x) 分别表示什么？ A*算法f(x):估计这么走至少要走多少步才能结束，如果大于枚举的深度，就退出
g(x):目前为止走了多少步
h(x):有多少个骑士不在目标位置上，至少需要这么多步才会完成A*算法可以发现，这样可以使更多的搜索时间集中于较优的分支，例如这两张图片，左图是普通bfs搜索，右图是使用了A*搜索而骑士精神用到的搜索方法，更明确的叫法应该是IDA*双向广搜双向广搜是从初始状态和目标状态交替进行搜索，直至找到交集的搜索过程，对算法的优化是显然的。
例如左图，红色+紫色部分是从初始状态进行搜索遍历到的区域，蓝色+紫色部分是从目标状态进行搜索遍历到的区域，而紫色部分是双向广搜遍历到的区域Bzoj 1616: [Usaco2008 Mar]Cow Travelling游荡的奶牛奶牛们在被划分成N行M列(2 <= N <= 100; 2 <= M <= 100)的草地上游走，试图找到整块草地中最美味的牧草。Farmer John在某个时刻看见贝茜在位置 (R1, C1)，恰好T (0 < T <= 15)秒后，FJ又在位置(R2, C2)与贝茜撞了正着。 FJ并不知道在这T秒内贝茜是否曾经到过(R2, C2)，他能确定的只是，现在贝茜在那里。 设S为奶牛在T秒内从(R1, C1)走到(R2, C2)所能选择的路径总数，FJ希望有一个程序来帮他计算这个值。每一秒内，奶牛会水平或垂直地移动1单位距离（奶牛总是在移动，不会在某秒内停在它上一 秒所在的点）。草地上的某些地方有树，自然，奶牛不能走到树所在的位置，也不会走出草地。 现在你拿到了一张整块草地的地形图，其中'.'表示平坦的草地，'*'表示挡路的树。你的任务是计算出，一头在T秒内从(R1, C1)移动到(R2, C2)的奶牛可能经过的路径有哪些。 从起点出发走T/2步，记录每个格子到达次数a[i][j]
从终点出发走T-T/2步，记录每个格子到达次数b[i][j]
所有格子的a[i][j]*b[i][j]就是答案
复杂度4^(T/2)+n*m
此题如果T更大，可以用dp解决，做到O(n*m*T)或O((n*m)^3*logT)
八数码问题八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻 的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。实际上这道题使用最暴力的广度优先搜索也可以在1s之内出解，但是使用广度优先搜索可以快很多
另外补充一种状态的存储方式，减少内存占用首先把空格看成填9，那么我们需要存储的就是一个1到9的排列
定义每个排列的编号是这个排列写成一个数之后是所有排列中第几小的，编号从0开始
对于任一排列cn,……c2,c1,其中倒数第i个元素ci与它后面的i-1个元素构成的逆序对个数为di，那么这个数是第M小的，M=sigma(d[i]*(i-1)!)
这样每个比当前排列小的排列都会在第一位与这个排列不同的位置上被计算