/ ALGORITHM

搜索入门

本文参考自”英雄哪里出来”的博文

深度优先搜索 (DFS)

1. DFS

  • 算法描述:

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

    • a. 访问 当前结点,并且标记该结点已被访问,然后跳转到b;

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

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

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

  • 基础应用:

    a. 求N的阶乘

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

    c. 求N个数的全排列

  • 高级应用:

    a. 枚举:

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

    • 例题:

      Dessert ★☆☆☆☆ 枚举

      Matrix ★☆☆☆☆ 枚举

      Pairs of Integers ★★☆☆☆ 枚举

    b. 容斥原理:

    • 利用深搜计算一个公式,本质还是做枚举;

    • 例题:

      Frogs ★★☆☆☆ 容斥

      幸运数字 ★★☆☆☆ 容斥

    c. 基于状态压缩和数位统计的动态规划:

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

    • 例题:

      棋盘问题 ★★☆☆☆ dfs

      Beautiful Number ★★★☆☆ 数位DP

      Round Number ★★★☆☆ 数位DP

    d.记忆化搜索:

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

    • 例题

      滑雪 ★★★☆☆ 记忆化搜索

      Bribe the Prisoners ★★★☆☆ 记忆化搜索

    e.有向图强连通分量:

    • 经典的Tarjan算法;

    • 求解2-sat问题的基础;

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

    • 经典的Tarjan算法;

    g. LCA:

    h.博弈:

    • 利用深搜计算SG值;

    i.二分图最大匹配:

    • 经典的匈牙利算法;

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

    • 例题

      Chessboard ★☆☆☆☆ 二分图最大匹配

      Air Raid ★★☆☆☆ 最小路径覆盖

      Difference ★★★☆☆ 二分图最大匹配

      Necklace ★★★★☆ 二分图最大匹配

    j.欧拉回路:

    • 经典的圈套圈算法;

    k. K短路:

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

    l. 线段树

    • 二分经典思想,配合深搜枚举左右子树;

    m. 最大团

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

    n. 最大流

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

    o. 树形DP:

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

2. 基于DFS的记忆化搜索

  • 算法原理:

    类似动态规划的思想,每次将已经计算出来的状态的值存储到数组中,下次需要的时候直接读数组中的值,避免重复计算。

  • 例题:往上翻 ლ(╹◡╹ლ)

3. 基于DFS的剪枝

  • 算法原理

    通过某种判断,避免一些不必要的遍历过程

    a. 正确性

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

    b. 准确性

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

    c. 高效性

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

    • 算法原理:

      如果判断子树中不可能存在可行解,俺么剪掉该子树。

  • 最优性剪枝(上下界剪枝) A*

    • 算法原理:

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

  • 例题:

    Dropping the stones ★★★☆☆ DFS+剪枝

    Graph Coloring ★★★☆☆ DFS+剪枝+最大团

4. 基于DFS的IDA*

  • 算法原理:

    迭代加深分两步走:

    • 1、枚举深度。

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

  • 例题:

    The Rotation Game ★★★☆☆ IDA*

广度优先搜索 (BFS)

1. BFS

  • 算法原理:

    广度优先搜索即Breadth First Search,也是图遍历算法的一种

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

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

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

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

  • 基础应用:

    a. 最短路:

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

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

    b. 拓扑排序:

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

    c. FloodFill:

    • 经典洪水灌溉算法;
  • 高级应用

    a. 差分约束:

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

    b. 稳定婚姻:

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

    c. AC自动机:

    • 字典树 + KMP + BFS,在设定失败指针的时候需要用到BFS。 详细算法参见:http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html

    d. 矩阵二分:

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

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

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

    Find The Multiple ★☆☆☆☆ BFS

    Pushing Boxes ★★☆☆☆ BFS

    Jugs ★★☆☆☆ BFS

2. 基于BFS的A*

  • 算法原理

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

  • 基础应用

    a. 八数码问题

    b. K短路问题

  • 例题:

    Eight ★★☆☆☆ BFS+A*

    Gap ★★★☆☆ BFS+A*

3. 双向BFS

  • 算法原理

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

    利用两个队列,初始化时初始状态在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;

  • 例题:

    Solitaire ★★★☆☆ 双向BFS

    魔板 ★★★★☆ 双向BFS

    Eight II ★★★★★ 双向BFS