搜索的奇技淫巧

搜索的基本形式

DFS：一棵树
BFS：扩散

-1 搜索使用的条件与范围

例如T2：枚举角度

最优解问题

可行解问题

解数量问题

0 DFS与BFS的判断

BFS：
一个状态到另一个状态的最小步数
状态可压缩且内存可保证或无需判重（sizeof(队列)=元素数*大小，内存开销大）
状态层数不会太深
DFS：
不能使用BFS的情况
一般来说上述三个条件满足那么BFS优于DFS

1 状态表示与判重

希望一个状态只被搜一次，因此需要判重
将一个状态表示出来：
如T3：
1）用3*3*4的数组表示一个状态
2）用3*3的数组表示一个状态，因为每一个方格的颜色不变，记录每个方格的位置即可
3）一个九位数int表示
因此用尽量简单的方式表示状态是思考主要方向

判重：
1)bool数组，前提的内存足够，如今天T3会有$10^9$的大小
2)set判重，较慢但省空间，O(logn)

#include <set>
using namespace std;
set<int> s;
int a;
s.insert(a);//加入
if(s.count(a)) /*...*/
//判断a出现次数，为1即存在
//s.erase(a);

对于难以压缩的状态：

struct rec{
    int map[4][4];
};
//必须，否则会报错
bool operator<(const rec &x,const rec&y){
    for(int a=0;a<4;++a){
        for(int b=0;b<4;++b){
            if(x.map[a][b]!=y.map[a][b])
                return x.map[a][b]<y.map[a][b];
        }
    }
    return false;
}
set<rec> s;
s.insert(a);

//&的用法
int gg(int x,int y) /*..*/
将x,y拷贝一份进行运算
int gg(int &x,int &y) /*..*/
直接引用地址
int gg(const int &x,const int &y) /*..*/
保证x,y不变

2 通用剪枝方法

具体问题：

最优解：超过当前解则break;
尤其是DFS应用多
可行解：无通法
解数量：记忆化搜索，记录某一状态的答案

通用方法：

排除不可能的分支
走玄学意义上更好的分支
随机化：防止丧病出题人出恶意数据卡某一搜索顺序
（eg：靶形数独）
因此建议搜索绝对不要正着按顺序搜索

//random_shuffle可以生成一个随机排列
#include <algorithm>
for(int i=1;i<=6;++i) z[i]=i;
random_shuffle(z+1,z+7);

建议开了dev-cpp的取消自动补全某些头文件功能

3 卡时

最优解问题
将=0变成>=0
1s建议设置到0.85s

#include <ctime>
void dfs(){
    if(1000*(clock()-t)>=850*CLOCKS_PER_SECOND){ 
        //这玩意表示一秒有多少时间单元
        printf("%d",&ans);
        exit(0);//退出整个程序
    }
}
    int t=clock();//单位为时钟单元

还可以卡评测机

4 双向BFS（Meet int the middle）

如果考到搜索约有10%概率会考
假设每一状态有三个状态
正常状态为$\sum^L_{i=1} 3^i$，约有$2*3^L$个状态
如果从终点也拓展状态，有$2\sum^{(\dfrac{l}{2})}_{i=1} 3^i$，约有$4*3^{(\dfrac{L}{2})}$个状态
相当于$\sqrt{n}$个状态
使用的条件：
1）知道终止状态
2）可以从终止状态向前回推
3）终止状态逆转移状态与顺转移状态同阶

5 A*搜索

基本思想

以最短路为例
定义c为最优代价，表示长度
函数f(s)表示从起点走到s的最短路，g(s)表示s到终点的最短路
则c=min{f(s)+g(s)}
但是我们的搜索是顺着搜，因此我们只能确定f(s)
我们就猜测g(s)的值，用估价函数h(s)表示
会出现3种：
h(s)=g(s)，达到最高效率，求出最优解
h(s)>c'，直接剪枝，此时可能会剪掉)
h(s)>g(s)，比较慢，但保证能搜出

本质：搜索顺序的改变

用优先队列维护拓展状态，每次取出f(s)+h(s)最小的状态
结合卡时效果更佳

举例：八数码问题

h(s)：曼哈顿距离之和

6 分支界定

按某种权值
用priority_queue维护取出最优解
结合卡时以提高输出正解的概率
玄学优化，例如T3以连通块个数为权值

7 迭代加深搜索

如果真的考到可以尝试现场yy
出题人卡BFS内存不得不使用DFS
那么限定搜索深度
例如求最短路，搜10->有解，搜9->有解，...，搜4—>无解
则深度为5，即最短路为5
可以二分深度或者枚举深度
->推荐使用枚举：状态数是指数级增长的，因此枚举代价最大的是新拓展的一层，二分反而耗时

例题

八数码

八皇后

靶形数独（Luogu1074)

玄学优化：
正搜70-80
倒着搜95
倒着按列搜100
正常优化：
1）从里往外搜，优先填大数，加一个卡时可A
2）从可能性少的格子开始搜索

Mayan游戏（Luogu1312）

最小步数->BFS，不能双向
问题在于状态压缩，只能记录整张map
这样一个状态要5*7数组，每次移动最坏有35*2个分支
显然tan$\dfrac{\pi}{2}$
可以开结构体扔set判重，不过开销也很大
所以我们用DFS解决
但DFS的问题在于，可能某一步无解，可能需要很深
这里我们可以采用迭代加深的方法优化
此外：
1）最优解优化
2）左换右=右换左，搜索量减半

Flowfree

直接暴搜比较慢
1，从外圈开始搜可以优化，一圈一圈往里搜
2，优先搜曼哈顿距离小的
3，如果某一路径将图分为两半，且在路径两侧有点存在，那么就会减去
这里我们可以每走几步BFS一次求出是否相交