[关闭]
@shixinyi 2017-12-25T10:19:47.000000Z 字数 4326 阅读 534

搜索

OI

搜索

什么时候用搜索？

你想不到能其他方法解决的问题。
一般状态数不多
一般时间复杂度是指数级
一般数据范围

BFS&DFS

BFS与DFS的一些差别

BFS:队列 DFS:栈
DFS常用于解决连通性问题,BFS则更多是为了遍历
DFS要考虑回溯,但是在很多地方编程更容易.(可以很好地表示状态)
一般BFS所用空间要比DFS大.

BFS与SPFA

BFS不会再次进队,不会多次更新.

例题

[SCOI2009]生日快乐

windy的生日到了，为了庆祝生日，他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。现在包括windy，一共有N个人来分这块大蛋糕，要求每个人必须获得相同面积的蛋糕。windy主刀，每一切只能平行于一块蛋糕的一边（任意一边），并且必须把这块蛋糕切成两块。这样，要切成N块蛋糕，windy必须切 N-1次。为了使得每块蛋糕看起来漂亮，我们要求N块蛋糕的长边与短边的比值的最大值最小。你能帮助windy求出这个比值么？
1 <= X,Y <= 10000 ； 1 <= N <= 10

[POI2008]POD Subdivision of Kingdom

给出一个具有N个结点的无向图,将其分成两个集合S1,S2. 这两个集合的点的个数一样多,但连接它们的边最少.

我们无法在搜索之后O(n)check来过掉这题； 这个复杂度只允许一个搜索； 于是就有了这么一个思路：在搜索的过程中维护答案！
每次选中一个点就相当于是将其从不选集合放到选中集合； 而对于答案的影响是减去它与选中集合的边数，加上它与不选集合的边数；
这个做到O(1)，那么这么顺便做答案的复杂度就是可以接受的了； 我们将边表示成邻接矩阵，然后用int状压表示；
如果一个集合也用同样的方法表示，那么与那个点边集做and(&)就是连边的集合了； 统计一个数中1的个数则是预处理一个数组，直接到数组中查；
虽说开不下，但是把数分成两半再查就好了；

[SCOI2010] 幸运数字

在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在[1,100]的区间内就只有6个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。lxhgww规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如12，16，666都是“近似幸运号码”。 现在lxhgww想知道在一段闭区间[a, b]内，“近似幸运号码”的个数。

一个非常显然的事实就是幸运号码不会太多。把表打出来，就会发现在以内的幸运数只有2000多一点.
这个时候一个非常显然的想法就是对这些数进行容斥，即加上每个数的倍数个数，减去两个数的倍数个数，加上三个的，……以此类推。
这样的复杂度显然是不对的，理论上可达，其中x为幸运数个数。但是由于多个数的倍数不能超过右边界，就可以减一大刀，实际复杂度低了不知道多少。
但是这样仍然不够。我们还可以对幸运数进行处理，将其中是另外的幸运数的倍数的数给去掉。这样可以将需要考虑的数的个数减掉一半左右。
最后还有一个小优化，那就是将最后需要处理的幸运数按从大到小排好序。这样可以让乘积尽早变得更大，可以减掉许多不必要的计算。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<cmath>
  6. #define maxn 10010
  8. using namespace std;
  9. typedef long long llg;
  11. int la,lb,ci;
  12. llg now,ans,mi[15],l,r;
  13. llg a[maxn],b[maxn];
  15. void search(int d){
  16.     if(now>r) return;
  17.     llg xx=now;
  18.     now=xx+6*mi[d]; search(d+1);
  19.     now=xx+8*mi[d]; search(d+1);
  20.     if(xx) a[++la]=xx; now=xx;
  21. }
  23. llg gcd(llg a,llg b){
  24.     llg r=a%b;
  25.     while(r) a=b,b=r,r=a%b;
  26.     return b;
  27. }
  29. void dfs(int j){
  30.     if(j==lb+1){
  31.         if(!ci) return;
  32.         if(ci&1) ans+=r/now-(l-1)/now;
  33.         else ans-=r/now-(l-1)/now;
  34.         return;
  35.     }
  36.     dfs(j+1); llg xx=now; ci++;
  37.     now=xx/gcd(xx,b[j]);
  38.     if((double)now*b[j]<=r){
  39.         now*=b[j];
  40.         if(now<=r) dfs(j+1);
  41.     }
  42.     ci--; now=xx;
  43. }
  45. int main(){
  46.     File("a");
  47.     mi[0]=1;
  48.     for(int i=1;i<=10;i++) mi[i]=mi[i-1]*10;
  49.     scanf("%lld %lld",&l,&r);
  50.     search(0); sort(a+1,a+la+1);
  51.     for(int i=1;i<=la;i++){
  52.         b[++lb]=a[i];
  53.         for(int j=1;j<lb;j++)
  54.             if(a[i]%b[j]==0){lb--; break;}
  55.     }
  56.     for(int i=1;i<=lb/2;i++) swap(b[i],b[lb-i+1]);
  57.     now=1; dfs(1);
  58.     printf("%lld",ans);
  59.     return 0;
  60. }

[Poi2013]Tales of seafaring

一个n点m边无向图，边权均为1，有k个询问，每次询问给出(s,t,d)，要求回答是否存在一条从s到t的路径，长度为d，路径不必是简单路(可以自交)。
n,m<=5000,k<=1000000,d<=1000000000

考虑到若从s可以走d步到达t，则s必然可以走t+2步到达t，所以只要从每个点开始看该点奇数步或偶数步到达某个点最短路即可。
因为边权相同,所以不用spfa,可以直接从每个点开始BFS

  1. void BFS(int x)  
  2. {  
  3.     static pair<int,bool> q[M<<1];  
  4.     int i,r=0,h=0;  
  5.     memset(f,0x3f,sizeof f);  
  6.     f[x][0]=0;  
  7.     q[++r]=make_pair(x,0);  
  8.     while(r!=h)  
  9.     {  
  10.         pair<int,bool> temp=q[++h];  
  11.         int x=temp.first;  
  12.         bool flag=temp.second;  
  13.         for(i=head[x];i;i=table[i].next)  
  14.             if(f[table[i].to][!flag]==0x3f3f3f3f)  
  15.                 f[table[i].to][!flag]=f[x][flag]+1,q[++r]=make_pair(table[i].to,!flag);  
  16.     }  
  17. }

[SDOI2015]排序

小A有一个~的排列,他希望将数组从小到大排序,小A可以执行的操作有种,每种操作最多可以执行一次,对于所有的,第i中操作为将序列从左到右划分为段,每段恰好包括个数,然后整体交换其中两段.小A想知道可以将数组从小到大排序的不同的操作序列有多少个,小A认为两个操作序列不同,当且仅当操作个数不同,或者至少一个操作不同(种类不同或者操作位置不同).
下面是一个操作事例:

第一次操作,执行第3种操作,交换和,
交换后的为.
第二次操作,执行第1种操作,交换和,
交换后的为.
第三次操作,执行第2中操作,交换和,
交换后的为.

首先我们很容易发现一个操作序列是否合法与序列的顺序是无关的
因此我们只需要确定某个操作序列中每个操作选不选就行了 那么这类操作序列对答案的贡献就是选择的操作数的阶乘
我们从小到大DFS，对于第i次操作我们将序列分成2^(n-i)段，每段长度2^i
我们找到序列中不是连续递增的段，如果这样的段超过2个，显然就废了
如果没有这样的段，就不需要执行这个操作
如果有一个这样的段，判断将这个段的前半部分和后半部分交换后是否连续递增，如果是就交换然后继续DFS
如果有两个这样的段，判断四种交换情况然后DFS

双向BFS

就是字面意思，双向的bfs，从两边同时开始bfs。

ID-DFS&IDA*

迭代加深搜索(IDDFS)

IDDFS实质上就是限定下界的深度优先搜索。即首先允许深度优先搜索K层搜索树，若没有发现可行解，再将K+1后重复以上步骤搜索，直到搜索到可行解。
迭代加深搜索算法就是仿广度优先搜索的深度优先搜索。
既能满足深度优先搜索的线性存储要求，又能保证发现一个最小深度的目标结点
有利于可行性剪枝(ans越小越容易)，没有最优性剪枝(因为枚举ans相当于最优性剪枝)

估价函数

s ： 问题的某种状态。
h*(s) ： s到目标的实际最短距离。
h(s) ： s的估价函数，表示s到目标距离的下界，h(s)<=h*(s)
若h函数是相容的，则还需要满足h(s1)<=h(s2)+c(s1,s2)，其中c(s1,s2)表示s1转移到s2的距离。
g(s) ： 到达s状态之前经过的距离。
f(s) ： s的启发函数，f(s)=g(s)+h(s)，f(s)单调递增。

当估价函数确定以后，我们每到达一个状态s，可以用f(s)进行剪枝。
ans表示当前最优答案，若f(s)>=ans，则当前状态舍去。
我们可以根据估价函数和启发函数来选择搜索顺序，加快搜索。

A* & IDA*

将估价函数运用到广搜的算法称为A*算法，需用堆来实现。
A*算法是理论上时间最优的算法，但所需空间太大。
为了解决A*算法的空间问题，IDA*算法被提出，它是将估价函数与迭代加深算法结合起来的算法。

(高级的)搜索算法

爬山法搜索 ？？
模拟退火搜索 ？？
遗传算法 ？？

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注