Skip to content

Optimization

Introduction

DFS (Depth-First Search) is a common algorithm that can solve most problems, but in most cases, it is a "cheating" algorithm—rarely is brute-force search the intended solution. This is because DFS has a particularly high time complexity. (If you haven't learned DFS, please study it first.)

Since it cannot be the intended solution, let's try to cheat more points. This article will introduce some practical optimization techniques (commonly known as "pruning").

First, here is a DFS template. Subsequent templates will be modified based on this.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int ans = worst_case, now;  // now is the current answer

void dfs(input parameters) {
  if (reached destination) ans = choose the best between current solution and existing solution;
  for (iterate over all possibilities)
    if (feasible) {
      perform operation;
      dfs(reduced scale);
      undo operation;
    }
}

Here, ans can be a record of the solution, so "choose the best between current solution and existing solution" becomes outputting the solution.

Pruning Methods

The most commonly used pruning techniques are three: memoization search, optimality pruning, and feasibility pruning.

In search, the same input values often yield the same solution. Thus, we can use an array to memoize results. For details, see Memoization Search.

Template:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
int g[MAXN];  // define memoization array
int ans = worst_case, now;

void dfs f(input parameters) {
  if (g[scale] != invalid value) return;  // or record solution, depending on the situation
  if (reached destination) ans = choose the best between current solution and existing solution;  // output solution, depending on the situation
  for (iterate over all possibilities)
    if (feasible) {
      perform operation;
      dfs(reduced scale);
      undo operation;
    }
}

int main() {
  // ...
  memset(g, invalid value, sizeof(g));  // initialize memoization array
  // ...
}

Optimality Pruning

Another reason for slow search is continuing to search when the current solution is already worse than the existing solution. We only need to check whether the current solution is worse than the existing one.

Template:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int ans = worst_case, now;

void dfs(input parameters) {
  if (now is worse than ans) return;
  if (reached destination) ans = choose the best between current solution and existing solution;
  for (iterate over all possibilities)
    if (feasible) {
      perform operation;
      dfs(reduced scale);
      undo operation;
    }
}

Feasibility Pruning

During search, continuing to explore when the current solution is already infeasible is another cause of slowness.

Template:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int ans = worst_case, now;

void dfs(input parameters) {
  if (current solution is infeasible) return;
  if (reached destination) ans = choose the best between current solution and existing solution;
  for (iterate over all possibilities)
    if (feasible) {
      perform operation;
      dfs(reduced scale);
      undo operation;
    }
}

Pruning Ideas

There are many pruning ideas, most of which require analysis based on specific problems. Here are a few common ones:

  • Extreme Case Method: Consider extreme cases. If even the most extreme (ideal) case cannot satisfy the conditions, then the actual search results certainly won't be better.

  • Adjustment Method: By comparing subtrees, prune duplicate subtrees and those that are clearly not the most "promising."

  • Mathematical Methods: For example, using connected components in graph theory, modular equations in number theory, inequality scaling to estimate lower bounds, etc.

Example

Job Assignment Problem

There are \(n\) (\(1 \leq n \leq 15\)) jobs to be assigned to \(n\) people, each person completing one job. The time for the \(i\)-th person to complete the \(k\)-th job is a positive integer \(t_{i,k}\) (\(1 \leq t_{i,k} \leq 10^4\)), where \(1 \leq i, k \leq n\). Determine an assignment scheme that minimizes the total time to complete all \(n\) jobs.

Since each person must be assigned a job, we can create a 2D array time[i][j] to represent the time for person \(i\) to complete job \(j\). Use a loop to assign jobs starting from the first person until everyone is assigned. When assigning a job to the \(i\)-th person, loop through each job to check if it has already been assigned. If not, assign it to person \(i\); otherwise, check the next job. Use a 1D array is_working[j] to indicate whether job \(j\) has been assigned: is_working[j]=0 if unassigned, otherwise is_working[j]=1. Using backtracking, after the worker loop ends, return to the previous worker, cancel the assigned job, and assign the next job until a feasible assignment is found. This way, backtracking to the first worker yields all feasible solutions.

Checking job assignments essentially means ensuring that the first dimension subscripts of the 2D array are all different and the second dimension subscripts are all different for a feasible solution. Since we want the minimum total time to complete all \(n\) jobs, i.e., the smallest total time among feasible solutions, define a global variable cost_time_total_min to represent the minimum total time found so far. Initialize cost_time_total_min as the sum of time[i][i], i.e., the sum of diagonal elements. After all people are assigned jobs, compare count with cost_time_total_min. If count is less than cost_time_total_min, an optimal solution is found, and assign count to cost_time_total_min.

Considering algorithm efficiency, a pruning optimization can be applied. When computing the local cost variable count, if count is already greater than cost_time_total_min, there is no need to continue assigning further, because the resulting solution will certainly not be optimal.

Reference Code 
 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
constexpr int N = 16;
int is_working[N] = {0};  // Whether a job is assigned
int tm[N][N];             // Time required to complete a job
int cost_time_total_min;  // Minimum total time to complete n jobs

// i represents the person index, count represents the total cost so far
void work(int i, int count, int n) {
  // If i exceeds the maximum number of jobs to assign, assignment is complete.
  // If count is less than the current cost_time_total_min, update cost_time_total_min.
  if (i > n && count < cost_time_total_min) {
    cost_time_total_min = count;
    return;
  }
  // Backtracking approach
  if (count < cost_time_total_min) {
    // j represents the job index
    for (int j = 1; j <= n; j++) {
      // If the job is not assigned (is_working = 0)
      if (is_working[j] == 0) {
        // Assign the job (is_working = 1)
        is_working[j] = 1;
        // Pass the work to the next person (i + 1)
        work(i + 1, count + tm[i][j], n);
        // After one iteration completes, return to the previous person and reassign this job.
        // Reset is_working[j] to 0.
        is_working[j] = 0;
      }
    }
  }
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> tm[i][j];
    }
    cost_time_total_min += tm[i][i];
  }
  work(1, 0, n);
  cout << cost_time_total_min << '\n';
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用