搜索·从入门到入土

· · 个人记录

本蒟蒻由于一开始搜索没学好，所以深受其荼毒……并且由于最近很闲，所以打算整理整理搜索算法这个大毒瘤……如果搜索学不好，没准NOIp连暴力也不会qwq.

虽然可以直接写正解不暴力

好啦不扯淡了qwq,下面记录记录心得

一.最普通的dfs和bfs

一般比较高级的考试都不可能直接考察这两种算法，但是是非常重要的基础工作。在这里整理一下相关的“unfamiliar points”

dfs:

1、关于回溯

这个问题是dfs里的核心问题，因为在深搜树中，回溯好像是一个很显然的操作，但是有时候却有不同的写法（以下内容太小学生） 比如第一种，这种格式就是典型的回溯：

void dfs(step)
{
    … … … … … …
    visit[now]=1;
    step++;
    dfs(step);
    visit[now]=0;
    step--;
    … … … … … … 
}

当然也有第二种

void dfs(step)
{
    … … … … … …
    dfs(step+1);
    … … … … … … 
}

这两种是等价的啦，虽然有些略微的不同，但是……只是略微。

PS:关于return不return的问题

实际有时候加不加return效果一样，原因就是在全部搜索完之后，程序会自动回溯；但是这个地方只是一个小知识而已，并不能盲目不return…………因为搜索完一定会return，但是return却不一定要搜索完。

2、关于剪枝

这个应该不难，因为是要根据题目而言的策略，所以无非就是发现到什么时候越界，到什么时候的搜索是无效的，return就行。

3、关于几种很蒟蒻的dfs题型

1)数列去重题：

比如某年的一道水题，求一个数的所有加和组成方式，不能重复。那我们如果单纯地回溯，会很难去重。那我们这个时候可以想出一个小技巧：虽然这个结果数列不是单调的，但是我们可以将其看作单调数列。那么这样的话，由于单调性，既可以枚举所有情况，又可以防止之后搜索出的与之前的有重复。

2)树的遍历题：

由于肯定会给定后序遍历或先序遍历，所以我们就可以很显然地看出根节点在哪，那么不断切换中序遍历与先后序遍历，递归下去即可。

3)求联通块题：

遇到这种求联通块的题，首先考虑染色。但是染色也可以分成多染色和01染色……视题而定了。(这就是典型的可不回溯dfs)

当然辣，还会有好多奇奇怪怪的用法qwq