Noip算法总结之搜索
本章内容
最近翻到一篇自己多年前写的Noip搜索算法总结，趁此机会搬运过来。
搜索的技巧
搜索主要是给出一些条件，在不同则状态之间进行转移，如果状态量少的话，那就可以直接上 DP 了，但搜索一般是状态量大，且不太好转移。
一般对于小数据，如什么 n ≤ 20 之类的是可以打暴搜的，而搜索的剪枝通常有两种：可行性剪枝和最优性剪枝。但有的时候，如果对于自己的这个剪枝没有十足的把握，那就不要加上
搜索的时候考虑使用位运算，速度可以加快些．对于一些可以转移的状态之间的搜索，我们可以考虑 hash 或者是状态压缩下来，进行记忆化，那么对于以后再次搜到这个状态我们就可以直接调用了
搜索的分类
枚举
这恐怕是最暴力的了，一般就是直接从初始状态搜索到结束状态，不加任何的剪枝和优化，复杂度一般为指数级别（n ≤ 20）
深度优先搜索（DFS）
这就相当于是走迷宫的时候一条路直接走到底，除非发现当前这条路非法或者走到终点，由于深搜是栈式的储存方式，所以对空间的消耗比较少，但要注意的是状态量的总数如果达到ｗ级别的话就要注意有爆栈的危险了，Windows 下是 3w 左右，Linux 是 10w 左右，一般和回溯搭配使用
广度优先搜索（BFS）
这就相当于是走迷宫的时候多路同时一起进行，走到终点就停止，对于求最优解且话费均等的情况较好，一般用队列实现。
DFS和BFS的比较
深搜的空间开销小，但对于数据可能走到解答树的某种节点上，这个节点的后继状态很多，但最优解却在另一个子树中． 广搜的空间开销相对于深搜要多很多，但求解的效率貌似要高些，而且不用担心会爆栈，（在对于树的某些操作，注意是否有爆栈的危险，若有的话，最好改成广搜或是手写栈）
迭代加深 和 IDA*
这种算法结合了深搜和广搜的优点，时间的表现也很不错。
搜索仍是DFS，但对于每次的搜索都给它设置一个深度上限，超过当前的深度上限就直接返回。
BZOJ 1085 骑士精神
经典例题：BZOJ 1085 骑士精神：
在一个5×5的棋盘上有12个白色 的骑士和12个黑色的骑士， 且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到 空位上。 给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘： 为了体现出骑士精神，他们必须以最少的步数完成任务。
迭代加深再加上ｈ(x) 即乐观估计函数，对于当前的状态我们可以乐观地估计出当前的状态到目标状态所需的最多层数，如果大于我们所设置的上界，就返回。
基本步骤：
设置一个固定的深度 maxdepth ，通常为 1，即初始的状态。
DFS 进行搜索，限制层数 depth，如果找到答案，则结束，如果没有找到答案则继续下一步。
如果 DFS 途中遇到更深的层，则 depth++ ，并重复 2；如果没有遇到，说明搜索已经结束，没有答案。
（中间可用乐观估价函数进行剪枝）
经典例题：codevs 1288 埃及分数：
在古埃及，人们使用单位分数的和（形如1/a的，a是自然数）表示一切有理数。
如：2/3 = 1/2+1/6，但不允许2/3=1/3+1/3，因为加数中有相同的。 对于一个分数a/b,表示方法有很多种，但是哪种最好呢？
首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。
如： 19/45 = 1/3 + 1/12 + 1/180 , 19/45 = 1/3 + 1/15 + 1/45 , 19/45 = 1/3 + 1/18 + 1/30 , 19/45 = 1/4 + 1/6 + 1/180 , 19/45 = 1/5 + 1/6 + 1/18。
最好的是最后一种，因为1/18比1/180，1/45，1/30，1/180都大。 给出a,b（0 < a < b < 1000），编程计算最好的表达方式。
双向广搜
这个我还没怎么用过，大概是正着搜一次，再从终点倒着搜一次，直到两者相遇。
Meet in the middle
主要思想：
两人分别从Ａ地和Ｂ地出发，向对方的出发点走去。当他们都走了 L/2 米的时候 ”在中间相遇“，找到了一条长度为 L 米的路径
两种模型
有向图模型
方程模型
经典例题
已知一个n元高次方程：
\(k_1x_1^{p_1}+k_2x_2^{p_2}+...+k_nx_n^{p_n}=0\)
其中：\(x_1,x_2,...,x_n\)是未知数，\(k_1,k_2,...,k_n\)是系数，\(p_1,p_2,...,p_n\)是指数。且方程中的所有数均为整数。
假设未知数\(1 \leq x_i \leq M, i=1,2,...,n\)，求这个方程的整数解的个数。
搜索的优化
剪枝（可行性剪枝，最优性剪枝）
改变搜索顺序,增加更多限制条件（如 NOI 2005 智慧珠游戏，CTSC 2013 复原）
记忆化搜索：对于同一状态的多次搜索，可以记忆化，下次就可以直接调用之前搜索过的结果（例：HNOI 2013 比赛）
吐槽
话说现在 BZOJ 没了真的好不方便啊...
看着原来的总结笔记，现在差不多全忘光了...