DFS&BFS及其优化

简介及声明

本文所涉及的DFS/BFS仅指指数级以上复杂度的暴搜，不包括图和网格上$O(n)$级别的搜索！

Part 1：DFS

例题1：[FAIOJ1220]字符序列

直接暴力搜索每个位置填$A,B,C$，对于以最后一位为末尾的子串检查其前面是否冲突即可。复杂度$O(3^n)$。

例题2：[FAIOJ1224]最佳调度问题

如果直接枚举每个任务在每个机器上完成，复杂度将会达到$O(k^n)$，代入数据范围得到$5^{20}\approx 10^{14}$，严重超时！

所以我们需要加入一些必要的剪枝。

最优性剪枝

本题要求的是最短时间，因此如果在向某个车间加入当前任务之后，该车间完成所有任务的总时间已超过当前答案，则可以直接剪掉接下来的所有搜索，退回上一步。

同时，我们可以在最开始先利用一种贪心算法求出一个解，这个解不是最优的，但它可以快速剪掉所有比它更劣的解。

贪心算法的设计很简单。每次选择当前用时最短的车间加入任务即可。错误性显然。但它比较接近最优解。

这个剪枝的力度极大。但很遗憾还是会TLE。。。。。。

我们发现，这道题的$k$个车间是相同的，也就是我们会重复搜索$k!$种状态，使复杂度凭空增加一个$k!$。

所以强制每次新加一个车间时，都加入第一个没用过的车间即可。

Part 2：BFS

例题3：[NOIP2002][luogu1037][FAIOJ1130]产生数

依照题意，直接DFS/BFS。注意已经产生的数用一个vis数组记录一下（$10^{30}$用整型已存不下，需要用字符串&map）。

显然以上做***T。。。。。。

观察到每个数位是独立的，因此只需对$0$到$9$分别处理它会变成哪些数，再乘法原理即可。

复杂度仅为$O(n+k)$

（这道题其实不是搜索，只不过是被放到搜索题里了。。。）

例题4：[NOIP2002][luogu1032][FAIOJ1252]字串变换

首先本题数据范围不严格，应改为$|S|\le 10$。原因下面讲。

依照题意，本题要求最小步数所以用BFS。

每次取出队首的串，对$x$串依次进行匹配，如果匹配成功则将把$x$换成对应$y$的新串加入队列。

直接BFS的复杂度是$O(nS{)}^m)$的，代入数据范围得到$120^{10}\approx 8\times 10^{20}$，严重超时！

但是这种做法竟然可以轻松通过原题。。。。。。

Part 3：对搜索顺序的优化

例题5：[NOIP2009][luogu1074][FAIOJ10093]靶形数独

本题看起来十分复杂。但由于题目中已给出至少$24$个数字，因此数独的解中剩下的方案数也不多。我们可以直接搜索所有的方案。

首先本题有一个最暴力的算法，就是从左上角开始填所有的数。然而这样显然是不行的，让我们考虑以下极端情况：

你在左上角搜出了很多很多种方案，可你在左上角的第一个数搜到的数就注定了无解……

此方法可得到$40-70$分不等。

因此，我们要避免这种情况的发生。这种情况的本质是：我们先搜了方案数很多的位置，然后才搜方案数很少的位置。

因此，每当我们填完一个数之后，都去找全图中可填方案最少的那个位置并对它进行搜索，即可最大程度避免以上问题。

找可填方案数最少的位置用一个三重循环即可做到。看似很浪费时间，但与做大量无用搜索相比绝对是值得的。

经此优化可通过全部数据。

例题6：[NOIP2015][luogu2668][FAIOJ10152]斗地主

伴随着某PKU出题人整整四年的毒瘤题目名称

本题肯定是搜索了。但具体如何搜呢？

我觉得是个人都不会选择先出单牌。。。

根据斗地主的经典新手玩法，我们选择：

先出飞机，再出连对，再出顺子，再出三带和四带，最后出剩下的牌。

而且，飞机、连对和顺子都是从长到短搜索。

首先，牌的花色是毫无用处的，我们可以不管。我们只需存每个点数都有几张即可。注意：把A视为14。

飞机、连对和顺子

这部分暴力搜索即可。因为只有三种牌型，每种牌型最多也只有几十种。

我们第一维从长到短枚举长度，第二维枚举最大牌的点数。

如果飞机存在，就把飞机相应的点数-=3再搜下一层。搜完回溯时再+=3。连对和顺子同理。

这样就可以搜完这三种牌型了。

三带一、四带二、1234单出

这部分只能用$DP$解决。

首先明确指出：贪心是不行的！因为一个对子可以拆成两个单牌，一个炸弹也可以拆成两个对子。。。

设$f[i][j][k][l]=$当前手牌有$i$单牌，$j$对子，$k$三张，$l$炸弹的不出飞机/连对/顺子的最小步数。

分别考虑各种转移方式即可。（有$13$种转移，要全部考虑才能AC~）

注意最后还要讨论王的情况（是当成两张单牌带出去还是一起扔出去）

Part 4：双向BFS

双向BFS

双向BFS，指从初始状态和目标状态同时展开搜索，如果产生交叉则将两边步数相加作为答案。

该方法可将步数减半。这个减半意味着指数减半，即总复杂度开根！

若已知初始状态和目标状态，则可用双向BFS。用map记录已到达过的状态即可。

例题7：[SCOI2005][luogu2324]骑士精神

本题有两种做法，双向BFS和下文要讲的IDA*。

双向BFS做法显然。因为步数上限已经确定（$15$步），所以我们不用让初始和目标轮流走（写起来太麻烦），直接预处理目标状态移动$1$至$8$步的所有状态并存入map。这部分需计算不多于$7^8\approx 6\times 10^6$种状态。

然后对于每组询问，我们搜索初始状态移动$1$至$7$步的所有状态并在map中查询即可。

一共需计算不多于$10\times 7^7+7^8\approx 1.5\times 10^7$种状态。可通过本题。

Part 5：A*和IDA*算法

A*算法

考虑一道最优化代价的搜索问题。

假设我们现在得到了一个状态$S$，花费的代价是$x$，我们并不知道它具体还需要多少代价才能达到目标。

但我们知道，它至少（不一定能取到下界）还需要$y$的代价才能达到目标。

如果$x+y\ge ans$，那么我们就知道再往下搜索已经毫无意义。可以直接退出了。

A*算法实质上是最优性剪枝的进一步优化。

例如著名的“次短路问题”就是利用$A\ast$算法求解的。（不过因为它还需要其他的数据结构维护，所以这里暂时不做讲解。）

IDA* = IDFS + A*

IDFS全称“迭代加深搜索”。在某些不确定步数上限的搜索问题中使用。

直接枚举达到目标所需的步数上限，达到上限即停止搜索，避免陷入过深的搜索树中无法自拔。

然而很容易发现，这种搜索几乎等同于BFS。。。所以它单独使用时没有什么用，我们需要结合$A\ast$算法来达到强大的剪枝效果。

例题7的第二种解法

首先我们从$1$到$15$枚举答案步数。

然后进行暴力$DFS$。但直接暴力到底会达到$7^{15}\approx 5\times 10^{12}$的计算量，显然是不可行的。

因此采用A*算法进行优化。

我们发现，每次移动最多会使一个放错位置的棋子移动到正确位置。

因此至少还需要**(位置错误的棋子)步**达到目标状态。以此估价来剪枝可剪去大量状态。事实上，多数方向相反的状态会在$5$步以内被剪去。

光速通过本题，甚至比双向BFS还快。

练习题

[NOIP2001][luogu1019]单词接龙

这也是一道假题。。。不过假得不算太离谱，把范围改成$n\le 15$还是合理的。

[NOIP2001][luogu1021]邮票面值设计

这又是一道假题。。。把范围改成$n+k\le 10$比较合理。

[NOIP2004][luogu1092]虫食算

大体思路就是从低位往高位搜索，并判断当前位是否合法来剪枝。注意利用竖式加法对应位的性质。

[NOIP2011][luogu1312]Mayan游戏

细节极多的暴搜题目。但时限很宽松，几乎不需要剪枝。

[luogu1379]八数码难题

本题和例题7类似，双向BFS和IDA*都可以解决。实现优秀的普通BFS也可以解决。

总结

搜索类题目在早期NOIP当中出现频率很高，但在2010年之后就很少出现了。现在的搜索常常会以最低档部分分的形式出现。因此熟练掌握搜索和基本剪枝技巧就意味着几乎可以每道题都不爆0。