Optimization

Preface

DFS (depth-first search) is a common algorithm, and most problems can be solved with DFS. However, in most cases this is a score-gaining algorithm, and it is rare for brute force search to be the intended solution, because DFS has a particularly high time complexity. (If you have not learned DFS, please make up this lesson yourself.)

Since it cannot be the intended solution, let us gain a little more score. This article introduces some practical optimization algorithms (commonly called “pruning”).

Here is a template for depth-first search; the subsequent templates will be modified on this basis.

int ans = WORST_CASE, now;  // now is the current answer

void dfs(input_value) {
  if (reached_goal) ans = best_of(current_solution, ans);
  for (each_possible_choice)
    if (feasible) {
      apply_choice();
      dfs(smaller_problem);
      undo_choice();
    }
}

Here, ans can record the solution, in which case selecting the best of the current solution and existing solutions becomes outputting the solution.

Pruning Methods

The three most commonly used pruning methods are memoized search, optimality pruning, and feasibility pruning.

Memoized Search

Because the same input values in a search often produce the same solution, an array can be used for memorization. See memoized search for details.

Template:

int g[MAXN];  // Define the memoization array
int ans = WORST_CASE, now;

void dfs f(input_value) {
  if (g[problem_size] != INVALID_VALUE) return;  // Or record the solution, as appropriate
  if (reached_goal) ans = best_of(current_solution, ans);  // Output the solution, as appropriate
  for (each_possible_choice)
    if (feasible) {
      apply_choice();
      dfs(smaller_problem);
      undo_choice();
    }
}

int main() {
  // ...
  memset(g, INVALID_VALUE, sizeof(g));  // Initialize the memoization array
  // ...
}

Optimality Pruning

Another reason that a search runs slowly is that it continues searching even when the current solution is already worse than an existing solution. We only need to check whether the current solution is already worse than an existing solution.

Template:

int ans = WORST_CASE, now;

void dfs(input_value) {
  if (now_is_worse_than_ans) return;
  if (reached_goal) ans = best_of(current_solution, ans);
  for (each_possible_choice)
    if (feasible) {
      apply_choice();
      dfs(smaller_problem);
      undo_choice();
    }
}

Feasibility Pruning

Continuing to search when the current solution has already become unusable is also a reason for slow execution.

Template:

int ans = WORST_CASE, now;

void dfs(input_value) {
  if (current_solution_is_invalid) return;
  if (reached_goal) ans = best_of(current_solution, ans);
  for (each_possible_choice)
    if (feasible) {
      apply_choice();
      dfs(smaller_problem);
      undo_choice();
    }
}

Pruning Ideas

There are many pruning ideas. Most require analysis of the specific problem; here we briefly introduce several common ideas.

• Extreme-case method: consider extreme cases. If even the most extreme (most ideal) case cannot satisfy the requirements, then the result found for the actual case certainly cannot be better.

• Adjustment method: prune duplicate subtrees and subtrees that are clearly not the most “promising” by comparing subtrees.

• Mathematical methods: for example, use connected components in graph theory, analyze congruence equations in number theory, and use inequality scaling to estimate lower bounds.

Examples

Since every person must be assigned a job, a two-dimensional array time[i][j] can be created to represent the time spent by person $i$ completing job $j$. Given a loop, assign jobs starting from person 1 until everyone has been assigned. When assigning a job to person $i$, loop through the jobs again to check whether each has been assigned; if not, assign it to person $i$, otherwise check the next job. A one-dimensional array is_working[j] can represent whether job $j$ has been assigned: if it has not been assigned, is_working[j]=0, otherwise is_working[j]=1. Using backtracking, after the worker loop ends, return to the previous worker, cancel the job assigned this time, and assign the next job until one can be assigned. By backtracking to worker 1, all feasible solutions can be obtained.

Checking the job assignment means determining whether the first-dimensional indices and the second-dimensional indices of the two-dimensional array for a feasible solution are all different. We need the minimum total time for completing the $n$ jobs, namely the feasible solution with the smallest total time. Therefore, define a global variable cost_time_total_min to represent the smallest total time among the solutions found so far. Initially, cost_time_total_min is the sum of time[i][i], the sum of the diagonal job times. When all people have been assigned jobs, compare count with cost_time_total_min. If count is smaller than cost_time_total_min, an optimal solution has been found, so assign count to cost_time_total_min.

However, considering the algorithm's efficiency, another pruning optimization can be made. Each time the local cost variable count is calculated, if count is already greater than cost_time_total_min, there is no need to continue assigning jobs, because the resulting solution cannot be optimal.

#include <iostream>
constexpr int N = 16;
int is_working[N] = {0};  // Whether a job has been assigned
int tm[N][N];             // Time required to complete a job
int cost_time_total_min;  // Minimum total time to complete n jobs

// i indicates the person number, and count indicates the total job cost
void work(int i, int count, int n) {
  // If i exceeds the maximum number of jobs that can be assigned, the assignment is complete;
  // if count costs less than the previous cost_time_total_min, update cost_time_total_min
  if (i > n && count < cost_time_total_min) {
    cost_time_total_min = count;
    return;
  }
  // Backtracking
  if (count < cost_time_total_min) {
    // j indicates the job number
    for (int j = 1; j <= n; j++) {
      // If the job is unassigned, is_working = 0
      if (is_working[j] == 0) {
        // Assign the job, is_working = 1
        is_working[j] = 1;
        // Give the job to person i + 1
        work(i + 1, count + tm[i][j], n);
        // After one iteration, 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;
}