常见的搜索优化策略

现在acm的难度不断增加，简单的常规的搜索算法，(因为这些搜索的本质是盲目搜索)已经不能很好地解决问题，下面介绍 一些常见的优化方式

首先是深度优先搜索，对于DFS的优化主要是在时间复杂度上的，方法也有很多种，但是无论是何种优化方式，其本质都是通过减少扩展点的数量来降低时间复杂度的，当然减少的只能是那些不含可行解，或是不含最优解的状态。

常见的优化方式主要有以下几种:

1．剪枝 当我们发现某个状态的所有子状态都不可能是可行解时，我们就可以通过剪枝来避免拓展这个状态，（当然在有些时候 我们也可以通过预处理来实现，如 相同状态的合并，状态的有序化等）。剪枝的动机主要是通过主观判断，和数学推理来实现的，说来容易，但优秀的剪枝策略是需要通过大量的实践和 深厚的数学功底才能实现的。

例如， zju 1008 , 和zju 1909 都是属于深度优先加剪枝的经典题目，前者需要通过预处理的同状态合并，和判断来实现剪枝。而后者 则是通过有序枚举 状态中的元素 来消除重复的状态提高速度的。

2．有序搜索 也可以叫做 最优先搜索 是通过一定次序的搜索方式或是某种估价函数的判断来拓展状态从而寻找最优解的搜索，一般我们比较少使用估价函数，因为这已经不属于盲目搜索的范围了。有时对于某些DFS 问题中 我们可以先规定一个搜索的顺序，使我们能尽快地找到最优解 ， 或者保证我找到的第一个可行解 即为所求得最优解。

例如 zju 1499 由于题目要求从一个数字串中求出一个递增序列 使最后一个数尽可能的小，在这个基础上使第一个数字尽可能的大。我们可以从小到大枚举最后一个数字，对于每一在这样的数字 我们再由大到小枚举序列的 第一个数字，让后再DFS查找是否存在一个这样的可行解 ，这样一旦我们找到了一个可行解，这个解也就必定是最优解了。

下面说说广度优先的优化，广度优先搜索的主要矛盾是空间复杂度上的矛盾，所以优化也主要是集中在处理空间复杂度的问题

1．双向广度优先搜索 同时从初始状态 和 目标状态 进行层次遍历 因为层次遍历中空间成指数级增长，所以双向的BFS 能为我们节省等多的空间，这一点从下图中可以清楚看见

<shapetype coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f" id="_x0000_t75"></shapetype><stroke joinstyle="miter"></stroke><formulas></formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f><lock v:ext="edit" aspectratio="t"></lock><shape type="#_x0000_t75" style="width: 360.75pt; height: 134.25pt;" id="_x0000_i1026"></shape><imagedata src="file:///C:%5CDOCUME%7E1%5CN410C%5CLOCALS%7E1%5CTemp%5Cmsohtml1%5C01%5Cclip_image001.png" o:title="sbfs"></imagedata>

图中黄色的部分即为空间的需求，双向BFS 实现起来也是比较方便的，添加一张节点表，作为反向扩展表。此外我们只需在原来的状态中增加一个参数指出这个状态的根节点是目标状态还是初始状态，当我们添加一个状态时如果我们发现在我们的队列中有同样的状态但来自不同的根节点 我们就可以得到所求的解。这里还有一个改进就是略微修改一下控制结构，每次扩展正反两个方向中节点数目较少的一个，可以使两边的发展速度保持一定的平衡，从而减少总扩展节点的个数，加快搜索速度。

这种优化可以帮我们更好的解决诸如 8数码之类的问题 而几乎所有能用单向BFS 的问题都能使用双向BFS,当然双向广度优先也不是没有缺点， 例如在某些问题无解是 它的空间复杂度就会大大大于一般的单向BFS

<shape type="#_x0000_t75" style="width: 349.5pt; height: 146.25pt;" id="_x0000_i1025"></shape><imagedata src="file:///C:%5CDOCUME%7E1%5CN410C%5CLOCALS%7E1%5CTemp%5Cmsohtml1%5C01%5Cclip_image003.png" o:title="failbfs"></imagedata>

对于这一点对于无解状态很多的问题显然是致命的，所以使用时一定要加以考虑。

2，状态空间的优化，在确定使用广度优先之后 我们需要仔细的估算状态的数量，和规模，如果规模太大，超过了承受范围，我们就需要试着去考虑缩小状态的规模。

例如 zju 的 2288 ，第一眼看到题目，自然而然的想到 使用 4个int 和 1 个 bool 来表示一个状态 分别表示两岸的人数 和 船当前的位置 可是这里的范围是1-200 状态的规模相当于 (200^4)*2这是我们无法接受的。可是一想因为两岸的人数和是一个定值，只需要两个 int就可以完整的表示一个状态 ，这样规模一下子就成了 200^2*2 很容易就搞定了。题目虽然简单，但却足以说明 控制状态规模的重要性，当然很多难题具体如何优化也是需要靠经验积累的

3．状态储存的优化，有些问题的状态数量可以满足要求，但是状态比较复杂，储存起来比较困难，这个时候我们就要考虑一下如何表示一个状态

例如 pku 2697 初看题目最直观的想法就是开个char 的二位数组来记录状态，这样需要的空间就是 16 个字节 储存一个状态 。但是实际上整个状态中只有 8 个点对我们有意义， 每个点我们可以用 两个坐标表示 这样我们可以用 16个整数来表示 一个状态，这样占用的空间反而大了 （16*4）字节，这时我们会发现这里的每个整数实际上最多只有3，也就是2位二进制，于是我们就可以将这16个数利用位操作压缩到1个32位的int 中，分别表示白点和黑点的位置，而储存空间只有原来的1/4了，同时由于变成了标准数据类型，使下一步的比较等工作，方便了不少

4．判重过程中的优化，大家知道在BFS中去除重复状态的工作是必需的，然而简单的遍历所有队列中的状态，代价是极大的，在大多数情况下会换来一个tle 。为解决这个问题我们一般会使用hash表来解决这个问题。Hash函数的设计是需要经验的，好的hash函数能极大增快程序的速度，在考虑hash 表来判重时因该首先考虑哪些没有冲突的hash 方案，例如 前面讲到的 zju 的2288 我们只需要开个200*200 的bool 数组 就可以解决问题 所也不用去想其他方案了。但是对于有些问题使用没有冲突的hash 表超过了储存空间的上限，这样的例子很多 也可以说 绝大多数问题属于这一类 如pku 2697 ,zju 1361 都是这样 这时我建议使用stl 中的map 来代替hash ，map 的本质是一个平衡二叉树，插入，和查找的复杂度都在logN左右 和一般的hash表差距不大，加之已经被高度封装 使用起来相当方便。

相比之下，写带有冲突处理机制的hash表再自己设计hash函数就十分复杂了。在使用map 的过程中 需要注意的是 如果我们使用的是自定义数据类型，我们需要为之定义一个判断大小关系的函数，如果不是很熟练可能会带来一点麻烦，所以最好的办法还是将状态压缩到一些标准数据类型中，这样我们就无需自己定义函数了，也给比较等工作带来了很多方便，

例如 上面我们说到的pku 2697可以被压缩到一个int中，而zju 1361 的状态也可以被压缩到一个string 中。其实大多数问题的状态都可以被压缩成标准数据类型不但节省了空间，也方便了操作。

Trackback: http://tb.donews.net/TrackBack.aspx?PostId=628996