基本的搜索算法

响应李老师的号召，抽空写了一下基本的搜索算法。我的搜索技术很有限，写的东西很难足够充实与深刻，但结合了具体的POJ 的题目，相信对于初学的队员多少还是有一点用处的。我主要说了四个部分：
1． 二分搜索 （Binary Search）
2． 记忆化搜索 (Dynamic Programming)
3． 广度优先搜索(BFS)
4． 深度优先搜索（DFS）

另外，有一点我觉得初学的人要理解，搜索就是穷举，当在做题的时候你发现一个题目需要枚举所有的情况的时候，你在做的就是搜索，当然，搜索也有很多策略和技巧可以优化你的搜索，这就是经常听说的剪枝。惭愧，我的搜索基本没剪枝。根据不同的具体题目剪枝策略很不相同，该怎么剪枝我也就不再多说了，但是在搜索的时候要时刻考虑有哪些剪枝条件可以加上以优化搜索，否则就跟我一样只能平庸的搜索了。

1． 二分搜索 （Binary Search）

二分也是搜索，因为解空间具有单调性，所以可以利用二分的思想去掉一大部分解空间，也即做了一个强有力的剪枝。同时二分也是一种基本的算法思想，当在思考一个问题的时候如果不能灵光一闪可以尝试用一些算法思想来考虑，比如对于一个问题你可以这样思考，这题贪心是否可以呢如果贪心的话该怎样贪呢，找不出合理的贪心方法的时候再想，这题动态规划是否可以呢，有没有第推关系呢，还找不出来再想用图论模型是否可以呢，该用哪种图论模型呢最短路径，最小生成树还是网络流呢，如果还不行还可以想那用二分可不可行呢，该怎样二分，为什么是可行的呢。
什么时候二分是可行的呢？下面简单的探讨一下。
先来看这样的一个小问题，给一个函数 F(x) 在闭区间 [A，B]上单调递增（假设F(x)的定义域均为整数），要求找出在区间[A，B]上最小的一个满足 F(n)>=0 的整数n。对于这个小问题最直观的想法就是从A开始穷举，这样写出来的程序可能会是这个样子。

For (int n=A; n<=B; n++)
{
If (F(n) >= 0)
Break;
}
这就是传说中的纯暴力，但是这个问题是可以用二分优化的，它之所以可以二分是因为 函数 F(n) 满足单调性，这点十分重要，这是一个问题可否二分的先决条件。那为什么满足单调性就可以二分呢，这是因为如果n满足F(n)>=０的话，所有　Ｂ＞＝ｘ＞＝ｎ　的数肯定也满足。所以所要求的目标解肯定在区间　［Ａ，ｎ］中。二分程序我一般都这样写。

Int min = A; // 解空间的最小值
Int max = B;//解空间的最大值
Int ans; //存储目标解
While (min <= max) //当解空间非空
{
Int mid = (min +max) / 2; // 取当前解空间的中值

If（ok(mid) ）// 如果mid 满足要求
{ //继续在 [min, mid-1] 中寻找更优的解
Max = mid-1;
Ans = mid; //记录下当前找到的解
}
Else //否则在区间 [mid+1,max]中寻找最优解
{
Min = mid + 1;
}

}
Ans 即为想要的答案，实际应用时注意在区间里找不到最优值得情况，注意看题目说明这个时候应该输出什么值。

下面结合一道具体的POJ 的题目来说下二分的应用


POJ 3273 Monthly Expense

题意不再多说，说得抽象一点，这个题可以这样思考。
设函数 f(x) 表示 如果要使每个月的钱都没有超过 x ，则划分出来的月的个数，设题目的解空间为[min, max] （相信理解了题意很容易确定）则，题目的要求可以描述为在区间 [min, max]中寻找最小的值ans 使得 f(ans) == M; 当然如果找到最小的ans 使得 f(ans)=m < M 的话肯定也满足要求，很显然，因为用m月来划分尚且没有使得每个月的钱超过 ans 那用 M个月划分就更不会超过ans，于是题目要求更新为在区间[min,max]中寻找最小值 ans 使得 f(ans) <= M； 上面说过要是可以二分必然满足函数 f(x) 在区间上单调， 这个函数 f(x)显然单调，理由，对于解空间的两个值 x1 < x2 ，如果用x1作为每个月钱的上限划分出来的月数为 y1，则用更多的钱 x2作为每个月钱的上限划分出来的月数 y2没有理由比y1会小，所以原函数满足单调性，所以可以用二分来解决。现在只剩下一个问题了，对于一个任意值x判断它的可行性，也即函数f(x)的值该如何求。方法就是尽量往一个月中加入尽量多的连续的天数使得当前月的钱数总合没有超过 x，如果加入一天的钱超出了x则函数值++，置当前月的钱数为该天的钱数，继续进行下去。
具体实现不再多说了。

推荐的题目：

3122：分析方法与上面类似，推荐。
3179：二分+枚举区间，有点难度，有兴趣的队员可以做下。
2922：综合题有一定的难度，BFS+二分+枚举区间，有兴趣的队员可以做下。
2． 记忆化搜索 （Dynamic Programming）

动态规划其实也是搜索，只不过，在搜索过程中它把一些已经搜索到的结果记录下来，当再次需要时如果发现当前状态的结果已经记录下来的时候，没有必要再次搜索，直接取出值来就可以。
来看一道POJ 的例题
POJ 3186


注意到题目的描述，FJ是按照时间顺序，也即天来卖treat的，每一天FJ手中的treat都有一个特定的状态。设为d[i,j]，表示为当前FJ手中的treat 标号为从i到j ，即 i,i+1, i+2,…,j，初始时状态为d[1,n]，每一天FJ都要做一个决策，选择卖出一个treat，对于状态为d[i,j]时他只有两种选择，要么卖标号为i的treat要么卖标号为j的treat，所以如果让dp[i,j]表示当FJ面对的状态为d[i,j]时他所能得到的最大值，则他所能得到的最大值是他所做的两种决策的最大值，则
dp[i,j] = max(dp[i+1,j]+wt(i,j,i), dp[i,j-1]+wt(i,j,j))；由此得到了第推关系，其中wt(i,j,i)表示当状态是d[i,j]时，卖标号为i的treat，标号为i的treat能贡献的值，具体是什么样子的可以看题意。
有两种方式可以实现，一种是第规的方式，一种是非第规，如果用第规的方式的话，更能体会为什么会叫作记忆化搜索，实现的时候，用一个数组dp[i，j]记录下搜索得到的当前状态的最优值，可以赋初值为-1，设函数 f(i,j) 表示寻找dp[i,j]的最优值，可以在进入函数的时候检查dp[i,j]是否为-1，如果不为-1则表示它的值已经计算出来了，直接返回dp[i,j]的值即可，如果为-1则表示它还没有被计算，返回f(i+1,j)+wt(i,j,i)和
f(i,j-1) + wt(i,j,j)的最大值；

这种第规形式的动态规划，我印象中几乎没做过，有我也是改成了非第规的形式。如果谁知道的话可以共享一下。
3． 广度优先搜索 （BFS）

这种题太多了，从易到难，数不过来，所以如果学会了广搜的话你会感觉你可以AC掉很多很多的题目。如果没学会的话，赶紧着学吧，我就推荐几个题目吧。

如果你刚学会BFS，或者不太会的话，可以做一下这几个题目。
POJ 1562，2386，3194，1915，1979
如果你觉得基本的BFS题可以顺利的AC了可以做下这几个题目。
这些题就是考得耐心和细心，其实都不难。
POJ 1101 传说中的连连看
POJ 2935 简单的题目但要求输出路径
POJ 2046 记录状态判重比较麻烦
POJ 2049 不是很容易，数据比较阴险，我做了好长时间。


4． 深度优先搜索 （DFS）

深搜是在万不得已，不得不枚举所有状态的时候才会用到，而且往往要用到比较巧妙的剪枝。我就推荐几个题目吧 （不用剪枝）
BFS推荐题中的1562，2386，1979都可以用DFS做，可以体会一下。
POJ 2676 数独问题，硬搞就行不难，
POJ 1011 很难的题目，要求有精妙的剪枝，推荐早晚把它做了。
POJ 2362 类似POJ 1011 但比那个要简单一些，推荐先做2362再作1011。