搜索

· · 个人记录

搜索 update on 2023/1/15 (\%25/\%100)

Tips：一定一定不要小瞧搜索，搜索也是可以出黑题的

零、前言

想必大家都会搜索吧(默认大家都会)，既然会那我就不讲了吧
今天肯定不讲dfs,bfs那些及其简单的搜索，我们讲点其他的。

一、迭代加深搜索

在爆搜的时候，搜索规模是随着搜索深度指数增加的。

为了更快地搜索到最优解，可以想到要让搜索的深度尽可能小，就会用bfs减少时间复杂度，但是往往bfs不适用于爆搜，或者需要过多的空间。

这是就要请出我们的主角迭代加深搜索了，迭代加深搜索即限定搜索深度D进行dfs，搜索完深度D以内的所有节点后再增大D重新搜索直到找到答案。

是不是有点懵，啊对，我一开始也有一点懵，举个栗子就不懵了: P1763 埃及分数
在主函数从小到大一次枚举最少分数个数，即上文D，在dfs里判断是否合法若合法输出最小的D，否则继续枚举。

int x , y , sz = 1;//sz为最少分数个数，即上文D
int p[] , ans[];
bool flag;//合法为1，不合法为0
int gcd(int x , int y){}
void dfs(int step , int pre){
//step表示当前选到了第几个分数，pre表示前一个分数的分母
    if(step > sz){
        __________;//更新ans数组
        flag = 1;
        return;
    }
    int up = (sz - step + 1) * y * 1. / x;
    int down = ceil(y * 1. / x);
    //此处up,down的取值下文再解释
    for(int i = max(down , pre + 1); i <= up; i++){
        p[step] = i;
        __________;//修改x,y值
        dfs(step + 1 , i);
        x = tx , y = ty;//回溯
    }
}
int main(){
    cin >> x >> y;
    int tx = x , ty = y;
    while(!flag){
        __________;//初始化代码不给了
        dfs(1 , 0);
        sz++;
    }
    for(int i = 1; i < sz; i++) cout << ans[i] << " ";
    return 0;
}
tips$:此代码为伪代码，需要稍加更改才可$AC

下面所说的非常非常关键

up = (sz - step + 1) * y * 1. / x\quad① down = ceil(y * 1. / x)\quad②

为了方便理解上述代码中的up和down，首先我们来化一个式子:

\frac{x}{y}\ge\frac{1}{a}

\frac{y}{x}\le a

在①式中sz-step+1表示还有几个数未选完，y * 1. / x表示上述的a，乘起来就是a的最大值
在②式中y * 1. / x也是上述a，向上取整一下就为a的最小值了

所以这道题结束了，是不是很简单？其实我也觉得他不是很难，应该评不上紫题难度，最多也只有蓝题那种难度，不能再高了。

待更新——启发式搜索(A* 算法)