算法入门之搜索

WarPlayer 2016-04-15

展开全文

来自：英雄哪里出来 - C++博客

　　链接：http://www./menjitianya/archive/2015/10/09/211980.html

　　一、深度优先搜索

　　1、DFS

　　1) 算法原理

　　深度优先搜索即Depth First Search，是图遍历算法的一种。用一句话概括就是：“一直往下走，走不通回头，换条路再走，直到无路可走”。

　　DFS的具体算法描述为选择一个起始点v作为当前结点，执行如下操作：

　　a、访问当前结点，并且标记该结点已被访问，然后跳转到b；

　　b、如果存在一个和当前结点相邻并且尚未被访问的结点u，则将u设为当前结点，继续执行a；

　　c. 如果不存在这样的u，则进行回溯，回溯的过程就是回退当前结点；

　　上述所说的当前结点需要用一个栈来维护，每次访问到的结点入栈，回溯的时候出栈（也可以用递归实现，更加方便易懂）。

　　如图1所示，对以下图以深度优先的方式进行遍历，假设起点是1，访问顺序为1 -> 2 -> 4，由于结点4没有未访问的相邻结点，所以这里需要回溯到2，然后发现2还有未访问的相邻结点5，于是继续访问2 -> 5 -> 6 -> 3 -> 7，这时候7回溯到3，3回溯到6，6回溯到5，5回溯到2，最后2回溯到起点1，1已经没有未访问的结点了，搜索终止，图中圆圈代表路点，红色箭头表示搜索路径，蓝色虚线表示回溯路径。

　　图1

　　2) 算法实现

　　深搜最简单的实现就是递归，写成伪代码如下：

　　def DFS(v):

　　visited[v] = true

　　dosomething(v)

　　for u in adjcent_list[v]:

　　if visited[u] is false:

　　DFS(u)

　　其中dosomething表示访问时具体要干的事情，根据情况而定，并且DFS是允许有返回值的。

　　3) 基础应用

　　a. 求N的阶乘；

　　令f(N) = N!，那么有f(N) = N * f(N-1) （其中N>0）。由于满足递归的性质，可以认为是一个N个结点的图，结点 i (i >= 1 ) 到结点 i-1 有一条权值为i的有向边，从N开始深度优先遍历，遍历的终点是结点0，返回1(因为0! = 1)。如图2所示，N!的递归计算看成是一个深度优先遍历的过程，并且每次回溯的时候会将遍历的结果返回给上一个结点（这只是一个思想，并不代表这是求N!的高效算法）。

　　图2

　　b. 求斐波那契数列的第N项；

　　令g(N) = g(N-1) + g(N-2)， (N > 2)，其中g(1) = g(2) = 1，同样可以利用图论的思想，从结点N向N-1和N-2分别引一条权值为1的有向边，每次求g(N)就是以N作为起点，对N进行深度优先遍历，然后将N-1和N-2回溯的结果相加作为N结点的值，即g(N)。这里会带来一个问题，g(n)的计算需要用到g(n-1)和g(n-2)，而g(n-1)的计算需要用到g(n-2)和g(n-3)，所以我们发现g(n-2)被用到了两次，而且每个结点都存在这个问题，这样就使得整个算法的复杂度变成指数级了，为了规避这个问题，下面会讲到基于深搜的记忆化搜索。

　　图3

　　c. 求N个数的全排列；

　　全排列的种数是N!，要求按照字典序输出。这是最典型的深搜问题。我们可以把N个数两两建立无向边（即任意两个结点之间都有边，也就是一个N个结点的完全图），然后对每个点作为起点，分别做一次深度优先遍历，当所有点都已经标记时输出当前的遍历路径，就是其中一个排列，这里需要注意，回溯的时候需要将原先标记的点的标记取消，否则只能输出一个排列。如果要按照字典序，则需要在遍历的时候保证每次遍历都是按照结点从小到大的方式进行遍历的。

　　图4

　　4) 高级应用

　　a. 枚举：

　　数据范围较小的的排列、组合的穷举；

　　b. 容斥原理：

　　利用深搜计算一个公式，本质还是做枚举；

　　c. 基于状态压缩的动态规划：

　　一般解决棋盘摆放问题，k进制表示状态，然后利用深搜进行状态转移；

　　d.记忆化搜索：

　　某个状态已经被计算出来，就将它cache住，下次要用的时候不需要重新求，此所谓记忆化。下面会详细讲到记忆化搜索的应用范围；

　　e.有向图强连通分量：

　　经典的Tarjan算法；

　　求解2-sat问题的基础；

　　f. 无向图割边割点和双连通分量：

　　经典的Tarjan算法；

　　g. LCA：

　　最近公共祖先递归求解；

　　h.博弈：

　　利用深搜计算SG值；

　　i.二分图最大匹配：

　　经典的匈牙利算法；

　　最小顶点覆盖、最大独立集、最小值支配集向二分图的转化；

　　j.欧拉回路：

　　经典的圈套圈算法；

　　k. K短路：

　　依赖数据，数据不卡的话可以采用2分答案 + 深搜；也可以用广搜 + A*

　　l. 线段树

　　二分经典思想，配合深搜枚举左右子树；

　　m. 最大团

　　极大完全子图的优化算法。

　　n. 最大流

　　EK算法求任意路径中有涉及。

　　o. 树形DP：

　　即树形动态规划，父结点的值由各个子结点计算得出。

　　2、基于DFS的记忆化搜索

　　1) 算法原理

　　上文中已经提到记忆化搜索，其实就是类似动态规划的思想，每次将已经计算出来的状态的值存储到数组中，下次需要的时候直接读数组中的值，避免重复计算。

　　来看个例子，如图5所示，图中的橙色小方块就是传说中的作者，他可以在一个N*M的棋盘上行走，但是只有两个方向，一个是向右，一个是向下（如绿色箭头所示），棋盘上有很多的金矿，走到格子上就能取走那里的金矿，每个格子的金矿数目不同（用蓝色数字表示金矿的数量），问作者在这样一个棋盘上最多可以拿到多少金矿。

　　图5

　　我们用函数DFS(i, j)表示从(1, 1)到(i, j)可以取得金矿的最大值，那么状态转移方程 DFS(i, j) = v[i][j] + max{ DFS(i, j-1), DFS(i-1, j) }（到达(i, j)这个点的金矿最大值的那条路径要么是上面过来的，要么是左边过来的），满足递归性质就可以进行深度优先搜索了，于是遇到了和求斐波那契数列一样的问题，DFS(i, j)可能会被计算两次，每个结点都被计算两次的话复杂度就是指数级了。

　　所以这里我们可以利用一个二维数组，令D[i][j] = DFS(i, j)，初始化所有的D[i][j] = -1，表示尚未计算，每次搜索到(i, j)这个点时，检查D[i][j]的值，如果为-1，则进行计算，将计算结果赋值给D[i][j]；否则直接返回D[i][j]的值。

　　记忆化搜索虽然叫搜索，实际上还是一个动态规划问题，能够记忆化搜索的一般都能用动态规划求解，但是记忆化搜索的编码更加直观、易写。

　　3、基于DFS的剪枝

　　1) 算法原理

　　搜索的过程可以看作是从树根出发，遍历一棵倒置的树——搜索树的过程。而剪枝，顾名思义，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝（原话取自1999年OI国家集训队论文《搜索方法中的剪枝优化》（齐鑫））。如图6所示，它是一棵利用深度优先搜索遍历的搜索树，可行解（或最优解）位于黄色的叶子结点，那么根结点的最左边的子树完全没有必要搜索（因为不可能出解）。如果我们在搜索的过程中能够清楚地知道哪些子树不可能出解，就没必要往下搜索了，也就是将连接不可能出解的子树的那根“枝条”剪掉，图中红色的叉对应的“枝条”都是可以剪掉的。

　　图6

　　好的剪枝可以大大提升程序的运行效率，那么问题来了，如何进行剪枝？我们先来看剪枝需要满足什么原则：

　　a. 正确性

　　剪掉的子树中如果存在可行解（或最优解），那么在其它的子树中很可能搜不到解导致搜索失败，所以剪枝的前提必须是要正确；

　　b. 准确性

　　剪枝要“准”。所谓“准”，就是要在保证在正确的前提下，尽可能多得剪枝。

　　c. 高效性

　　剪枝一般是通过一个函数来判断当前搜索空间是否是一个合法空间，在每个结点都会调用到这个函数，所以这个函数的效率很重要。

　　剪枝大致可以分成两类：可行性剪枝、最优性剪枝（上下界剪枝）。

　　2) 可行性剪枝

　　可行性剪枝一般是处理可行解的问题，如一个迷宫，问能否从起点到达目标点之类的。

　　举个最简单的例子，如图7，问作者能否在正好第11秒的时候避过各种障碍物（图中的东西一看就知道哪些是障碍物了，^_^）最终取得爱心，作者每秒能且只能移动一格，允许走重复的格子。

　　图7

　　仔细分析可以发现，这是永远不可能的，因为作者无论怎么走，都只能在第偶数秒的时候到达爱心的位置，这是他们的曼哈顿距离（两点的XY坐标差的绝对值之和）的奇偶性决定的，所以这里我们可以在搜索的时候做奇偶性剪枝（可行性剪枝）。

　　类似的求可行解的问题还有很多，如N (N

　　3) 最优性剪枝（上下界剪枝）

　　最优性剪枝一般是处理最优解的问题。以求两个状态之间的最小步数为例，搜索最小步数的过程：一般情况下，需要保存一个“当前最小步数”，这个最小步数就是当前解的一个下界d。在遍历到搜索树的叶子结点时，得到了一个新解，与保存的下界作比较，如果新解的步数更小，则令它成为新的下界。搜索结束后，所保存的解就是最小步数。而当我们已经搜索了k歩，如果能够通过某种方式估算出当前状态到目标状态的理论最少步数s时，就可以计算出起点到目标点的理论最小步数，即估价函数h = k + s，那么当前情况下存在最优解的必要条件是h

　　4、基于DFS的A*（迭代加深，IDA*）

　　1) 算法原理

　　迭代加深分两步走：

　　1、枚举深度。

　　2、根据限定的深度进行DFS，并且利用估价函数进行剪枝。

　　2) 算法实现

　　迭代加深写成伪代码如下：

　　def IDA_Star(STATE startState):

　　maxDepth = 0

　　while true:

　　if( DFS(startState, 0, maxDepth) ):

　　return

　　maxDepth = maxDepth + 1

　　图8

　　3) 基础应用

　　如图8所示，一个“井”字形的玩具，上面有三种数字1、2、3，给出8种操作方式，A表示将第一个竖着的列循环上移一格，并且A和F是一个逆操作，B、C、D...的操作方式依此类推，初始状态给定，目标状态是中间8个数字相同。问最少的操作方式，并且要求给出操作的序列，步数一样的时候选择字典序最小的输出。图中的操作序列为AC。

　　大致分析一下，一共24个格子，每个格子三种情况，所以最坏情况状态总数为3^24，但实际上，我们可以分三种情况讨论，先确定中间的8个数字的值，假设为1的话，2和3就可以看成是一样的，于是状态数变成了2^24。

　　对三种情况分别进行迭代加深搜索，令当前需要搜索的中间8个数字为k，首先枚举本次搜索的最大深度maxDepth（即需要的步数），从初始状态进行状态扩展，每次扩展8个结点，当搜索到深度为depth的时候，那么剩下可以移动的步数为maxDepth - depth，我们发现每次移动，中间的8个格子最多多一个k，所以如果当前状态下中间8个格子有sum个k，那么需要的剩余步数的理想最小值s = 8 - sum，那么估价函数：

　　h = depth + (8 - sum)

　　当h > maxDepth时，表明在当前这种状态下，不可能在maxDepth歩以内达成目标，直接回溯。

　　当某个深度maxDepth至少有一个可行解时，整个算法也就结束了，可以设定一个标记，直接回溯到最上层，或者在DFS的返回值给定，对于某个搜索树，只要该子树下有解就返回1，否则返回0。

　　迭代加深适合深度不是很深，但是每次扩展的结点数很多的搜索问题。

　　二、广度优先搜索

　　1、BFS

　　1) 算法原理

　　广度优先搜索即Breadth First Search，也是图遍历算法的一种。用一句话概括就是：“我会分身我怕谁？！”。

　　BFS的具体算法描述为选择一个起始点v放入一个先进先出的队列中，执行如下操作：

　　a. 如果队列不为空，弹出一个队列首元素，记为当前结点，执行b；否则算法结束；

　　b. 将与当前结点相邻并且尚未被访问的结点的信息进行更新，并且全部放入队列中，继续执行a；

　　维护广搜的数据结构是队列和HASH，队列就是官方所说的open-close表，HASH主要是用来标记状态的，比如某个状态并不是一个整数，可能是一个字符串，就需要用字符串映射到一个整数，可以自己写个散列HASH表，不建议用STL的map，效率奇低。

　　广搜最基础的应用是用来求图的最短路。

　　如图9所示，对以下图进行广度优先搜索，假设起点为1，将它放入队列后。那么第一次从队列中弹出的一定是1，将和1相邻未被访问的结点继续按顺序放入队列中，分别是2、3、4、5、7，并且记录下它们距离起点的距离dis[x] = dis[1] + 1 (x 属于集合 {2, 3, 4, 5, 7})；然后弹出的元素是2，和2相邻未被访问的结点是10，将它也放入队列中，记录dis[10] = dis[2] + 1；然后弹出5，放入6（4由于已经被访问过，所以不需要再放入队列中）；弹出7，放入8、9。队列为空后结束搜索，搜索完毕后，dis数组就记录了起点1到各个点的最短距离；

　　图9

　　2) 算法实现

　　广搜一般用队列维护状态，写成伪代码如下：

　　def BFS(v):

　　resetArray(visited,false)

　　visited[v] = true

　　queue.push(v)

　　while not queue.empty():

　　v = queue.getfront_and_pop()

　　for u in adjcent_list[v]:

　　if visited[u] is false:

　　dosomething(u)

　　queue.push(u)

　　3) 基础应用

　　a. 最短路：

　　bellman-ford最短路的优化算法SPFA，主体是利用BFS实现的。

　　绝大部分四向、八向迷宫的最短路问题。

　　b. 拓扑排序：

　　首先找入度为0的点入队，弹出元素执行“减度”操作，继续将减完度后入度为0的点入队，循环操作，直到队列为空，经典BFS操作；

　　c. FloodFill：

　　经典洪水灌溉算法；

　　4) 高级应用

　　a. 差分约束：

　　数形结合的经典算法，利用SPFA来求解不等式组。

　　b. 稳定婚姻：

　　二分图的稳定匹配问题，试问没有稳定的婚姻，如何有心思学习算法，所以一定要学好BFS啊；

　　c. AC自动机：

　　字典树 + KMP + BFS，在设定失败指针的时候需要用到BFS。

　　详细算法参见：http://www./menjitianya/archive/2014/07/10/207604.html

　　d. 矩阵二分：

　　矩阵乘法的状态转移图的构建可以采用BFS；

　　e. 基于k进制的状态压缩搜索：

　　这里的k一般为2的幂，状态压缩就是将原本多维的状态压缩到一个k进制的整数中，便于存储在一个一维数组中，往往可以大大地节省空间，又由于k为2的幂，所以状态转移可以采用位运算进行加速，HDU1813和HDU3278以及HDU3900都是很好的例子；

　　f. 其它：

　　还有好多，一时间想不起来了，占坑；

　　2、基于BFS的A*

　　1) 算法原理

　　在搜索的时候，结点信息要用堆（优先队列）维护大小，即能更快到达目标的结点优先弹出。

　　2) 基础应用

　　a.八数码问题

　　如图10所示，一个3*3的棋盘，放置8个棋子，编号1-8，给定任意一个初始状态，每次可以交换相邻两个棋子的位置，问最少经过多少次交换使棋盘有序。

　　图10

　　遇到搜索问题一般都是先分析状态，这题的状态数可以这么考虑：将数字1放在九个格子中的任意一个，那么数字2有八种摆放方式，3有七种，依此类推；所以状态总数为9的排列数，即9!（9的阶乘） = 362880。每个状态可以映射到0到362880-1的一个整数，

　　对于广搜来说这个状态量不算大，但是也不小，如果遇到无解的情况，就会把所有状态搜遍，所以这里必须先将无解的情况进行特判，采用的是曼哈顿距离和逆序数进行剪枝，具体参见 SGU 139的解法：

　　http://www./menjitianya/archive/2014/06/23/207386.html

　　网上对A*的描述写的都很复杂，我尝试用我的理解简单描述一下，首先还是从公式入手：

　　f(state) = g(state) + h(state)

　　g(state) 表示从初始状态到 state 的实际行走步数，这个是通过BFS进行实时记录的，是一个已知量；

　　h(state) 表示从 state 到目标状态的期望步数，这个是一个估计值，不能准确得到，只能通过一些方法估计出一个值，并不准确；

　　f(state) 表示从初始状态到目标状态的期望步数，这个没什么好说的，就是前两个数相加得到，也肯定是个估计值；

　　对于广搜的状态，我们是用队列来维护的，所以state都是存在于队列中的，我们希望队列中状态的f(state)值是单调不降的（这样才能尽量早得搜到一个解），g(state)可以在状态扩展的时候由当前状态的父状态pstate的g(pstate)+1得到；那么问题就在于h(state)，用什么来作为state的期望步数，这个对于每个问题都是不一样的，在八数码问题中，我们可以这样想：

　　这个棋盘上每个有数字的格子都住了一位老爷爷（-_-|||），每位老爷爷都想回家，老爷爷的家就对应了目标状态每个数字所在的位置，对于 i 号老爷爷，他要回家的话至少要走的路程为当前状态state它在的格子pos[i] 和目标状态他的家target[i] 的曼哈顿距离。每位老爷爷都要回家，所以最少的回家距离就是所有的这些曼哈顿距离之和，这就是我们在state状态要到达目标状态的期望步数h(state)，不理解请回到两行前再读一遍或者看下面的公式。

　　h(state) = sum( abs(pos[i].x - (i-1)/3) + abs(pos[i].y - (i-1)%3) ) (其中 1

　　最后附上原题链接：http://acm./showproblem.php?pid=1043

　　b.K短路问题

　　求初始结点到目标结点的第K短路，当K=1时，即最短路问题，K=2时，则为次短路问题，当K >= 3时需要A*求解。

　　还是一个h(state)函数，这里可以采用state到目标结点的最短距离为期望距离；

　　附上原题链接：http:///problem?id=2449

　　3、双向广搜

　　1) 算法原理

　　初始状态和目标状态都知道，求初始状态到目标状态的最短距离；

　　利用两个队列，初始化时初始状态在1号队列里，目标状态在2号队列里，并且记录这两个状态的层次都为0，然后分别执行如下操作：

　　a.若1号队列已空，则结束搜索，否则从1号队列逐个弹出层次为K(K >= 0)的状态；

　　i. 如果该状态在2号队列扩展状态时已经扩展到过，那么最短距离为两个队列扩展状态的层次加和，结束搜索；

　　ii. 否则和BFS一样扩展状态，放入1号队列，直到队列首元素的层次为K+1时执行b；

　　b.若2号队列已空，则结束搜索，否则从2号队列逐个弹出层次为K(K >= 0)的状态；

　　i. 如果该状态在1号队列扩展状态时已经扩展到过，那么最短距离为两个队列扩展状态的层次加和，结束搜索；

　　ii. 否则和BFS一样扩展状态，放入2号队列，直到队列首元素的层次为K+1时执行a；

　　如图11，S表示初始状态，T表示目标状态，红色路径连接的点为S扩展出来的，蓝色路径连接的点为T扩展出来的，当S扩展到第三层的时候发现有一个结点已经在T扩展出来的集合中，于是搜索结束，最短距离等于3 + 2 = 5；