NeFut Logo NeFut
中 Admin Login

Efficient State Space Search and Pruning Strategies

Published at: 2026-05-29 00:44 Last updated: 2026-06-28 10:10
#C++ #Tutorial

Core Logic and Mathematical Principles

The essence of search is traversing the state space tree. Facing an exponentially growing state space, the underlying logic of pruning is to terminate invalid branches early, reducing the theoretical upper bound of search complexity from $O(k^N)$ to a practically executable scale.

State Space Tree

What is a State Space Tree?

A state space tree is a logical and mathematical abstract model.

When solving a problem, all possible "moves" and "states" are drawn as a large tree in chronological order. Through this tree, we can transform an abstract search problem into a concrete maze game of "finding the endpoint on a tree."

Core Components

Relationship Between Algorithms and State Space Trees

All search and optimization algorithms essentially operate on this virtual tree:

State Space Graphs and State Space Trees

The essence of state space is often a graph (possibly with cycles), but when the search algorithm's logical tentacles reach out, it always views it as a tree. Writing pruning and deduplication logic is essentially "shaving" this graph full of cycles, forcibly turning it into a clean, finite tree.

State Design and Algorithm Derivation

Taking the classic problem "Birthday Cake" (NOI1999 / Luogu P1731) as an example. The problem requires building an $M$-layer cake with a total volume of $N$ using cylinders, where both the radius $R$ and height $H$ of each layer are integers and strictly decreasing from bottom to top, minimizing the surface area.

1. State Design

The search state is determined by the current layer number, current volume, current surface area, and the radius and height of the previous layer. Define the DFS function state: dfs(dep, v, s, last_r, last_h), where dep is the current layer being searched (searching from bottom to top, with the bottom as layer $M$ and the top as layer $1$).

2. Derivation of Upper and Lower Bounds

For the $i$-th layer, the volume and height must be greater than or equal to the sum of the minimum volume and height of all layers above it.

$$R_i \le \min\left(\lfloor \sqrt{N - v} \rfloor, \text{last\_r} - 1\right)$$

$$H_i \le \min\left(\lfloor \frac{N - v}{R_i^2} \rfloor, \text{last\_h} - 1\right)$$

3. Derivation of Pruning Strategies

$$\sum_{j=1}^{dep} 2 R_j H_j = 2 \sum_{j=1}^{dep} \frac{R_j^2 H_j}{R_j} > \frac{2}{\text{last\_r}} \sum_{j=1}^{dep} R_j^2 H_j = \frac{2(N - v)}{\text{last\_r}}$$

(Establishes the relationship between remaining lateral surface area and remaining volume)

This yields the powerful optimality pruning inequality:

$$s + \frac{2(N - v)}{\text{last\_r}} \ge \text{ans} \implies \text{backtrack}$$

Feasibility pruning prevents "remaining volume being too small," while Optimality Pruning 2 prevents "remaining volume being too large." Optimality Pruning 1 prevents "the currently accumulated surface area is too large" (prevents "the current area has already exhausted the mandatory minimum overhead of future layers").

If Optimality Pruning 2 is "dynamic feasibility pruning based on volume resources," then Optimality Pruning 1 is "dynamic feasibility pruning based on layer structure."

Minimum Volume

  • Minimum volume of layer 1: $1^2 \times 1 = 1^3$
  • Minimum volume of layer 2: $2^2 \times 2 = 2^3$
  • Minimum volume of layer 3: $3^2 \times 3 = 3^3$

To complete the remaining dep layers of the cake, the minimum volume required in the extreme case is: $$minV[dep] = \sum_{j=1}^{dep} j^3$$

Minimum Surface Area

  • Minimum lateral surface area of layer 1: $2 \times 1 \times 1 = 2 \times 1^2$
  • Minimum lateral surface area of layer 2: $2 \times 2 \times 2 = 2 \times 2^2$
  • Minimum lateral surface area of layer 3: $2 \times 3 \times 3 = 2 \times 3^2$

The sum of the minimum lateral surface areas for the remaining dep layers is: $$minS[dep] = \sum_{j=1}^{dep} 2j^2$$

C++ Core Source Code

// State: dep(current layer), v(accumulated volume), s(accumulated surface area), r(previous layer radius), h(previous layer height)
void dfs(int dep, int v, int s, int r, int h) {
    if (dep == 0) {
        if (v == N) ans = std::min(ans, s);
        return;
    }

    // Feasibility pruning: current volume + minimum volume of remaining layers > target volume
    if (v + min_v[dep] > N) return;

    // Optimality pruning 1: current surface area + minimum lateral surface area of remaining layers >= known optimal solution
    if (s + min_s[dep] >= ans) return;

    // Optimality pruning 2: use mathematical inequality to estimate lower bound of future cost
    if (s + 2 * (N - v) / r >= ans) return;

    // Bound pruning: enumerate from bottom to top, prioritize larger sizes (optimize search order)
    int max_r = std::min(static_cast<int>(std::sqrt(N - v)), r - 1);
    for (int cur_r = max_r; cur_r >= dep; --cur_r) {
        // Avoid state pollution in the loop by using local variables for the bottom surface contribution
        int current_s = s + (dep == M ? cur_r * cur_r : 0);

        int max_h = std::min((N - v) / (cur_r * cur_r), h - 1);
        for (int cur_h = max_h; cur_h >= dep; --cur_h) {
            dfs(dep - 1, v + cur_r * cur_r * cur_h, current_s + 2 * cur_r * cur_h, cur_r, cur_h);
        }
    }
}
// Start from layer M (M is the total number of layers), current volume is 0, current surface area is 0,
// the virtual (M+1)-th layer has radius and height set to a sufficiently large boundary value N
dfs(M, 0, 0, N, N);

The essence of depth-first search optimization is to establish the global optimal solution boundary as early as possible by optimizing the search order, thereby synergistically combining bound constraints, feasibility pruning, and optimality pruning to achieve multi-dimensional dynamic pruning of the state space tree.

NOIP Practical Pitfall Guide

1. Search Order

In the absence of dependencies, decisions with stronger "constraint capabilities" (such as larger size or resource consumption) should be prioritized for enumeration.

The key to adjusting the search order from large to small is twofold: on one hand, large-scale decisions can rapidly consume resources, causing the search space of subsequent subtrees to collapse dramatically; on the other hand, the algorithm can quickly reach leaf nodes early in the process, obtaining a high-quality baseline solution, thus significantly tightening the global upper bound ans of the objective function and activating subsequent high-probability, large-scale pruning.

Conversely, if enumerating from small to large, the slow resource consumption of shallow-level decisions leads to exponential expansion of the state space at shallow levels; simultaneously, the inability to update ans promptly paralyzes the optimality pruning throughout the entire search process.

2. Integer Truncation and Correctness of Evaluation Functions

When performing mathematical scaling for optimality pruning, the integer division operation in the expression s + 2 * (N - v) / r introduces floor truncation errors. Since this arithmetic truncation effect makes the estimated lower bound of future cost conservative, it will not mistakenly prune away a potentially optimal solution; it only slightly relaxes the boundary condition, making it safe in terms of algorithmic correctness.

When performing high-power geometric volume calculations, if the data boundaries are large, intermediate variables must be explicitly cast to high-precision types such as long long. Otherwise, feasibility pruning will fail and cause TLE.

Classic Problems

1. Luogu P1120 Small Sticks

/**
 * @param res_sticks   Number of original sticks left to assemble
 * @param cur_len      Accumulated length of the current original stick being assembled
 * @param last_idx     Starting index for enumeration in the current level (avoid repeated combinations)
 */
bool dfs(int res_sticks, int cur_len, int last_idx) {
    if (res_sticks == 0) return true;

    // Current original stick is perfectly assembled, start assembling a new one
    if (cur_len == target_len) {
        return dfs(res_sticks - 1, 0, 0); 
    }

    for (int i = last_idx; i < n; ++i) {
        if (visited[i] || cur_len + stick[i] > target_len) continue;

        visited[i] = true;
        if (dfs(res_sticks, cur_len + stick[i], i + 1)) return true;
        visited[i] = false;

        // 1. First stick and last stick failure pruning
        if (cur_len == 0 || cur_len + stick[i] == target_len) return false;

        // 2. Redundant value pruning (skip subsequent sticks of the same length)
        while (i + 1 < n && stick[i] == stick[i + 1]) {
            i++; 
        }
    }
    return false;
}
if (cur_len == 0 || cur_len + stick[i] == target_len) return false;

First stick failure means: "Under the most lenient conditions (a completely new empty stick), any combination involving this first stick cannot complete the assembly of all remaining sticks." Last stick failure means: "After this stick perfectly fills the current $L$, the assembly of subsequent sticks still experiences global failure."

2. Luogu P1434 Skiing

int dfs(int x, int y) {
    if (f[x][y] > 0) return f[x][y]; // Memoization pruning, directly return known state

    int max_len = 1;
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && grid[nx][ny] < grid[x][y]) {
            max_len = std::max(max_len, dfs(nx, ny) + 1);
        }
    }
    return f[x][y] = max_len; // Record the optimal solution for the current state
}
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS