搜索

搜索，也就是对状态空间进行枚举，通过穷尽所有的可能来找到最优解，或者统计合法解的个数。

搜索有很多优化方式，如减小状态空间，更改搜索顺序，剪枝等。

搜索是一些高级算法的基础。在 OI 中，纯粹的搜索往往也是得到部分分的手段，但可以通过纯粹的搜索拿到满分的题目非常少。

状态空间

状态空间（英语：State-space_representation），是控制工程中的一个名词。状态是指在系统中可决定系统状态、最小数目变量的有序集合[1]。而所谓状态空间则是指该系统全部可能状态的集合[2]。简单来说，状态空间可以视为一个以状态变数为坐标轴的空间，因此系统的状态可以表示为此空间中的一个向量。

状态空间表示法即为一种将物理系统表示为一组输入、输出及状态的数学模式，而输入、输出及状态之间的关系可用许多一阶微分方程来描述。

为了使数学模式不受输入、输出及状态的个数所影响，输入、输出及状态都会以向量的形式表示，而微分方程（若是线性非时变系统，可将微分方程转变为代数方程）则会以矩阵的形式来表示。

状态空间表示法提供一种方便简捷的方法来针对多输入、多输出的系统进行分析并建立模型。一般频域的系统处理方式需限制在常系数，启始条件为0的系统。而状态空间表示法对系统的系数及启始条件没有限制。

DFS

DFS 为图论中的概念，详见 DFS（图论） 页面。在 搜索算法 中，该词常常指利用递归函数方便地实现暴力枚举的算法，与图论中的 DFS 算法有一定相似之处，但并不完全相同。

例题

把正整数 n 分解为 3 个不同的正整数，如 6=1+2+3，排在后面的数必须大于等于前面的数，输出所有方案。

简单暴力解法

for (int i = 1; i <= n; ++i)
  for (int j = i; j <= n; ++j)
    for (int k = j; k <= n; ++k)
      if (i + j + k == n) printf("%d = %d + %d + %d\n", n, i, j, k);

递归暴力解法

int m, arr[103];  // arr 用于记录方案

void dfs(int n, int i, int a) {
  if (n == 0) {
    for (int j = 1; j <= i - 1; ++j) printf("%d ", arr[j]);
    printf("\n");
  }
  if (i <= m) {
    for (int j = a; j <= n; ++j) {
      arr[i] = j;
      dfs(n - j, i + 1, j);  // 请仔细思考该行含义。
    }
  }
}

// 主函数
int n = in::number();
m = in::number();
dfs(n, 1, 1);

双向搜索

将开始结点和目标结点加入队列 q
标记开始结点为 1
标记目标结点为 2
while (队列 q 不为空)
{
  从 q.front() 扩展出新的 s 个结点

  如果 新扩展出的结点已经被其他数字标记过
    那么 表示搜索的两端碰撞
    那么 循环结束

  如果 新的 s 个结点是从开始结点扩展来的
    那么 将这个 s 个结点标记为 1 并且入队 q 

  如果 新的 s 个结点是从目标结点扩展来的
    那么 将这个 s 个结点标记为 2 并且入队 q
}