DFS(搜索)


引入

DFS 为图论中的概念,详见

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

解释

考虑这个例子:

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

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

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

=== "C++"

```cpp
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);
```

=== "Python"

```python
for i in range(1, n + 1):
    for j in range(i, n + 1):
        for k in range(j, n + 1):
            if i + j + k == n:
                print("%d = %d + %d + %d" % (n, i, j, k))
```

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

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

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

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

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

设一组方案将正整数 分解成 个正整数 的和。

我们将问题分层,第 层决定 。则为了进行第 层决策,我们需要记录三个状态变量:,表示后面所有正整数的和;以及 ,表示前一层的正整数,以确保正整数递增;以及 ,确保我们最多输出 个正整数。

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

代码如下:

=== "C++"

```cpp
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);
```

=== "Python"

```python
arr = [0] * 103  # arr 用于记录方案

def dfs(n, i, a):
    if n == 0:
        print(arr[1:i])
    if i <= m:
        for j in range(a, n + 1):
            arr[i] = j
            dfs(n - j, i + 1, j)  # 请仔细思考该行含义。

# 主函数
n, m = map(int, input().split())
dfs(n, 1, 1)
```

例题

Luogu P1706 全排列问题

C++ 代码:

贡献者:@Menci@Jimmy@WenzelTian@wysunrise2@Ir1d@kenlig@mgt@ksyx@zyouxam@H-J-Granger@Henry-ZHR@ouuan@暗夜@hewenyang@partychicken@Haoshen@TrisolarisHD@DeepThink1@心旷神怡@qq1010903229

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组