優化

前言

DFS（深度優先搜索）是一種常見的算法，大部分的題目都可以用 DFS 解決，但是大部分情況下，這都是騙分算法，很少會有爆搜為正解的題目。因為 DFS 的時間複雜度特別高。（沒學過 DFS 的請自行補上這一課）

既然不能成為正解，那就多騙一點分吧。那麼這一篇文章將介紹一些實用的優化算法（俗稱「剪枝」）。

先來一段深搜模板，之後的模板將在此基礎上進行修改。

int ans = 最壞情況, now;  // now 為當前答案

void dfs(傳入數值) {
  if (到達目的地) ans = 從當前解與已有解中選最優;
  for (遍歷所有可能性)
    if (可行) {
      進行操作;
      dfs(縮小規模);
      撤回操作;
    }
}

其中的 ans 可以是解的記錄，那麼從當前解與已有解中選最優就變成了輸出解。

剪枝方法

最常用的剪枝有三種，記憶化搜索、最優性剪枝、可行性剪枝。

記憶化搜索

因為在搜索中，相同的傳入值往往會帶來相同的解，那我們就可以用數組來記憶，詳見記憶化搜索。

模板：

int g[MAXN];  // 定義記憶化數組
int ans = 最壞情況, now;

void dfs f(傳入數值) {
  if (g[規模] != 無效數值) return;  // 或記錄解，視情況而定
  if (到達目的地) ans = 從當前解與已有解中選最優;  // 輸出解，視情況而定
  for (遍歷所有可能性)
    if (可行) {
      進行操作;
      dfs(縮小規模);
      撤回操作;
    }
}

int main() {
  // ...
  memset(g, 無效數值, sizeof(g));  // 初始化記憶化數組
  // ...
}

最優性剪枝

在搜索中導致運行慢的原因還有一種，就是在當前解已經比已有解差時仍然在搜索，那麼我們只需要判斷一下當前解是否已經差於已有解。

模板：

int ans = 最壞情況, now;

void dfs(傳入數值) {
  if (now比ans的答案還要差) return;
  if (到達目的地) ans = 從當前解與已有解中選最優;
  for (遍歷所有可能性)
    if (可行) {
      進行操作;
      dfs(縮小規模);
      撤回操作;
    }
}

可行性剪枝

在搜索過程中當前解已經不可用了還繼續搜索下去也是運行慢的原因。

模板：

int ans = 最壞情況, now;

void dfs(傳入數值) {
  if (當前解已不可用) return;
  if (到達目的地) ans = 從當前解與已有解中選最優;
  for (遍歷所有可能性)
    if (可行) {
      進行操作;
      dfs(縮小規模);
      撤回操作;
    }
}

剪枝思路

剪枝思路有很多種，大多需要對於具體問題來分析，在此簡要介紹幾種常見的剪枝思路。

極端法：考慮極端情況，如果最極端（最理想）的情況都無法滿足，那麼肯定實際情況搜出來的結果不會更優了。
調整法：通過對子樹的比較剪掉重複子樹和明顯不是最有「前途」的子樹。
數學方法：比如在圖論中藉助連通分量，數論中藉助模方程的分析，藉助不等式的放縮來估計下界等等。

例題

工作分配問題

題目描述

有 \(n\) 份工作要分配給 \(n\) 個人來完成，每個人完成一份。第 \(i\) 個人完成第 \(k\) 份工作所用的時間為一個正整數 \(t_{i,k}\)，其中 \(1 \leq i, k \leq n\)。試確定一個分配方案，使得完成這 \(n\) 份工作的時間總和最小。

輸入包含 \(n + 1\) 行。

第 1 行為一個正整數 \(n\)。

第 2 行到第 \(n + 1\) 行中每行都包含 \(n\) 個正整數，形成了一個 \(n \times n\) 的矩陣。在該矩陣中，第 \(i\) 行第 \(k\) 列元素 \(t_{i,k}\) 表示第 \(i\) 個人完成第 \(k\) 件工作所要用的時間。

輸出包含一個正整數，表示所有分配方案中最小的時間總和。

數據範圍

\(1 \leq n \leq 15\)

\(1 \leq t_{i,k} \leq 10^4\)

輸入樣例

輸出樣例

由於每個人都必須分配到工作，在這裏可以建一個二維數組 time[i][j]，用以表示 \(i\) 個人完成 \(j\) 號工作所花費的時間。給定一個循環，從第 1 個人開始循環分配工作，直到所有人都分配到。為第 \(i\) 個人分配工作時，再循環檢查每個工作是否已被分配，沒有則分配給 \(i\) 個人，否則檢查下一個工作。可以用一個一維數組 is_working[j] 來表示第 \(j\) 號工作是否已被分配，未分配則 is_working[j]=0，否則 is_working[j]=1。利用回溯思想，在工人循環結束後回到上一工人，取消此次分配的工作，而去分配下一工作直到可以分配為止。這樣，一直回溯到第 1 個工人後，就能得到所有的可行解。

檢查工作分配，其實就是判斷取得可行解時的二維數組的第一維下標各不相同並且第二維下標各不相同。而我們是要得到完成這 \(n\) 份工作的最小時間總和，即可行解中時間總和最小的一個，故需要再定義一個全局變量 cost_time_total_min 表示目前找到的解中最小的時間總和，初始 cost_time_total_min 為 time[i][i] 之和，即對角線工作時間相加之和。在所有人分配完工作時，比較 count 與 cost_time_total_min 的大小，如果 count 小於 cost_time_total_min，説明找到了一個最優解，此時就把 count 賦給 cost_time_total_min。

但考慮到算法的效率，這裏還有一個剪枝優化的工作可以做。就是在每次計算局部費用變量 count 的值時，如果判斷 count 已經大於 cost_time_total_min，就沒必要再往下分配了，因為這時得到的解必然不是最優解。

參考代碼

#include <cstdio>
#define N 16
int is_working[N] = {0};  // 某项工作是否被分配
int time[N][N];           // 完成某项工作所需的时间
int cost_time_total_min;  // 完成 n 份工作的最小时间总和

// i 表示第几个人，count 表示工作费用总和
void work(int i, int count, int n) {
  // 如果 i 超出了所能分配的最大工作件数，表示分配完成，并且 count 比原来
  // cost_time_total_min 花费少，则更新 cost_time_total_min 的值
  if (i > n && count < cost_time_total_min) {
    cost_time_total_min = count;
    return;
  }
  // 回溯思想
  if (count < cost_time_total_min) {
    // j 表示第几件工作
    for (int j = 1; j <= n; j++) {
      // 如果工作未被分配 is_working = 0
      if (is_working[j] == 0) {
        // 分配工作 is_working = 1
        is_working[j] = 1;
        // 工作交给第 i + 1 个人
        work(i + 1, count + time[i][j], n);
        // 在一轮迭代完成之后，返回到上一个人，要对此次的工作进行重新分配
        // 将 is_working[j] 重设为 0
        is_working[j] = 0;
      }
    }
  }
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      scanf("%d", &time[i][j]);
    }
    cost_time_total_min += time[i][i];
  }
  work(1, 0, n);
  printf("%d\n", cost_time_total_min);
  return 0;
}

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：CBW2007, ChungZH, Marcythm, abc1763613206, Ir1d
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用