DFS(搜索)

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

考虑这个例子:

例题

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

对于这个问题,如果不知道搜索,应该怎么办呢?

当然是 3 重循环,参考代码如下:

1
2
3
4
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);

那如果是分解成四个整数呢?再加一重循环?

那分解成小于等于 m 个整数呢?

这时候就需要用到递归搜索了。

该类搜索算法的特点在于,将要搜索的目标分成若干“层”,每层基于前几层的状态进行决策,直到达到目标状态。

考虑上述问题,即将正整数 n 分解成小于等于 m 个正整数之和,且排在后面的数必须大于等于前面的数,并输出所有方案。

设一组方案将正整数 n 分解成 k 个正整数之和,k 个正整数为 a_1, a_2, \ldots, a_k .

我们将问题分层,第 i 层决定 a_i 。则为了进行第 i 层决策,我们需要记录三个状态变量: n-\sum_{j=1}^i{a_j} ,表示后面所有正整数的和;以及 a_{i-1} ,表示前一层的正整数,以确保正整数递增;以及 i ,确保我们最多输出 m 个正整数。

为了记录方案,我们用 arr 数组,第 i 项表示 a_i . 注意到 arr 实际上是一个长度为 i 的栈。

代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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);  // 请仔细思考该行含义。
    }
  }
}
// 主函数
scanf("%d%d", &n, &m);
dfs(n, 1, 1);

例题

Luogu P1706 全排列问题

C++ 代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool vis[N];  //访问标记数组
int a[N];     //排列数组,按顺序储存当前搜索结果

void dfs(int step) {
  if (step == n + 1)  //边界
  {
    for (int i = 1; i <= n; i++) {
      cout << setw(5) << a[i];
    }
    cout << endl;
    return;
  }
  for (int i = 1; i <= n; i++) {
    if (vis[i] == 0) {
      vis[i] = 1;
      a[step] = i;
      dfs(step + 1);
      vis[i] = 0;
    }
  }
  return;
}

评论