跳转至

DFS（搜索）

引入

DFS 為圖論中的概念，詳見 DFS（圖論） 頁面。在 搜索算法 中，該詞常常指利用遞歸函數方便地實現暴力枚舉的算法，與圖論中的 DFS 算法有一定相似之處，但並不完全相同。

解釋

考慮這個例子：

例題

把正整數 \(n\) 分解為 \(3\) 個不同的正整數，如 \(6=1+2+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);

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

1
2
3
4
5
6
7
for (int i = 1; i < n + 1; i++) {
    for (int j = i; j < n + 1; j++) {
        for (int k = j; k < n + 1; k++) {
            if (i + j + k == n) System.out.printf("%d = %d + %d + %d%n", n, i, j, k);
        }
    }
}

那如果是分解成四個整數呢？再加一重循環？

那分解成小於等於 \(m\) 個整數呢？

這時候就需要用到遞歸搜索了。

該類搜索算法的特點在於，將要搜索的目標分成若干「層」，每層基於前幾層的狀態進行決策，直到達到目標狀態。

考慮上述問題，即將正整數 \(n\) 分解成小於等於 \(m\) 個正整數之和，且排在後面的數必須大於等於前面的數，並輸出所有方案。

設一組方案將正整數 \(n\) 分解成 \(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
17
18
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);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
static int m;

// arr 用於記錄方案
static int[] arr = new int[103];

public static void dfs(int n, int i, int a) {
    if (n == 0) {
        for (int j = 1; j <= i - 1; j++) System.out.printf("%d ", arr[j]);
        System.out.println();
    }
    if (i <= m) {
        for (int j = a; j <= n; ++j) {
            arr[i] = j;
            dfs(n - j, i + 1, j); // 請仔細思考該行含義。
        }
    }
}

// 主函數
final int N = new Scanner(System.in).nextInt();
m = new Scanner(System.in).nextInt();
dfs(N, 1, 1);

例題

Luogu P1706 全排列問題 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iomanip>
#include <iostream>
using namespace std;
int n;
bool vis[50];  // 访问标记数组
int a[50];     // 排列数组，按顺序储存当前搜索结果

void dfs(int step) {
  if (step == n + 1) {  // 边界
    for (int i = 1; i <= n; i++) {
      cout << setw(5) << a[i];  // 保留5个场宽
    }
    cout << endl;
    return;
  }
  for (int i = 1; i <= n; i++) {
    if (vis[i] == 0) {  // 判断数字i是否在正在进行的全排列中
      vis[i] = 1;
      a[step] = i;
      dfs(step + 1);
      vis[i] = 0;  // 这一步不使用该数 置0后允许下一步使用
    }
  }
  return;
}

int main() {
  cin >> n;
  dfs(1);
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用