State Compression Dynamic Programming: Efficient Solution to the Traveling Salesman Problem

Core Logic and Mathematical Principles

The essence of State Compression Dynamic Programming (State Compression DP) is to losslessly map a one-dimensional combinatorial set with strong discrete characteristics into a low-dimensional integer scalar through numeral system conversion (usually binary). This dimensionality reduction allows us to physically transfer states and check conflicts in $O(1)$ time using bitwise operations.

The Traveling Salesman Problem (TSP) is a textbook model for State Compression DP: given a graph and the distances between pairs of nodes, the goal is to find a circuit that visits all vertices exactly once with the minimum total weight (this section discusses its variant: finding the minimum weight path from the starting point 0, visiting all vertices exactly once, to the endpoint $N-1$).

1. Discrete Mapping of State Space

In the TSP problem, we need to know not only which city we are currently in, but also which cities have already been visited and which cities remain unvisited.

• Collapse of Exponential Space: If traditional sets are used to store visited cities, state determination becomes extremely inefficient. Since each city has only two mutually exclusive marginal states, "visited" and "not visited", we can precisely reproduce this state using a binary string of length $N$.
  For example, when $N=5$, the binary state $S = (10110)_2$:
• Counting from right to left (from bit 0 to bit 4), bits 1, 2, and 4 are 1, while bits 0 and 3 are 0.
• This indicates that cities 1, 2, and 4 have been visited, while cities 0 and 3 have not.
  At this point, this set state is perfectly compressed into a decimal integer: $S = 2^1 + 2^2 + 2^4 = 2 + 4 + 16 = 22$.

2. Bitwise Operations Control Matrix and Operator-based State Transition

Using the underlying bitwise operations of computers, operations such as intersection, union, complement, and membership of sets can be highly abstracted into the following operators:

State Design and Algorithm Derivation

1. State Space Definition

Let state $f[S][i]$ represent: the current visited city set is $S$ (the corresponding decimal integer of its binary mask), and currently standing at city $i$, the minimum total distance incurred.

• Legitimacy Constraints: The physical meaning of state $f[S][i]$ has a prerequisite condition: city $i$ must be included in set $S$, i.e., it must satisfy (S >> i) & 1 == 1.

2. Derivation of State Transition Equation

We implement decisions by looking back to find the predecessors of the current state. When we are at city $i$ with set $S$, we must have been at a different city $j$ in the previous step.
Since we stepped from $j$ to $i$, city $i$ must have been in the unvisited state in the previous step. Therefore, the predecessor state’s city set must be $S - \{i\}$, expressed in bitwise operations as S ^ (1 << i).

$$\forall j \in S \setminus \{i\}, \quad f[S][i] = \min \left( f[S][i], f[S \setminus \{i\}][j] + \text{weight}(j, i) \right)$$

Substituting in the bitwise operation operator:

f[S][i] = min(f[S][i], f[S ^ (1 << i)][j] + weight[j][i]);

3. Control of Topological Order

Since the states of large sets are always derived from the states of small sets (sets with one fewer element), in the underlying double loop, the outer loop must strictly enumerate state numbers $S$ from small to large (from 1 to $(1<

NOIP Practical Pitfall Guide

1. Confusion in Bitwise Operation Precedence Leading to Logical Breakdown

• Phenomenon: Writing conditions like if (s >> i & 1 == 1). In C++ operator precedence, arithmetic and relational operators (like ==) have a precedence that is strictly higher than that of shift operators (>>) and bitwise AND (&). The above line of code will be interpreted as if (s >> (i & (1 == 1))) during compilation, leading to absurd out-of-bounds checks or always-false conditions in state validation.
• Avoidance Method: When writing any bitwise operation expression in the exam, unconditionally add independent parentheses around the core unit of the bitwise operation. For example, enforce writing as: if (((s >> i) & 1) == 1).

2. Incorrect Space Dimension Allocation Leading to Memory Overflow (MLE)

• Phenomenon: Misdefining the state compression array as f[MAXN][1 << MAXN]. When accessing the state, if the first and second dimensions are reversed, it may not be problematic during memory allocation when processing $N=20$, but when running the table f[s][i], since $s$ reaches $10^6$, it directly causes segmentation faults (illegal memory reads out of bounds). Alternatively, mistakenly defining dimensions as f[1<<25][25] can directly lead to memory limit exceeded (MLE) at compile time.
• Avoidance Method: Generally, state compression DP is limited to $N \le 20$. When defining space, always place the large dimension representing $2^N$ in the first dimension of the array, i.e., f[1 << 20][20], to ensure memory locality and read/write speed.

Classic NOIP/Luogu Problems

1. Luogu P1433 Cheese Eating

• Problem Description: There are $N$ pieces of cheese in the room. A mouse starts from coordinate $(0,0)$ and must eat all the cheese. It can move in a straight line between any two pieces of cheese. Find the shortest total distance to eat all the cheese. $N \le 15$.
• Essence of the Problem and Solution Approach: A standard TSP problem specialized with geometric Euclidean distances.
  • Core Idea: Since $N \le 15$, $2^{15} = 32768$, the state compression space is very small. First, preprocess the distances between pairs of cheese points dist[i][j]. The state design is f[S][i], indicating the shortest distance while currently at piece $i$ with the set of eaten cheese being $S$. Fully apply the TSP recurrence template, and finally globally scan for $\min_{1 \le i \le N} \{ f[(1<

2. Luogu P1879 [USACO06NOV] Corn Fields G

• Problem Description: A farmer has a $M \times N$ plot of land, and certain cells cannot be grazed due to infertility. Now he needs to select some cells for grazing, ensuring that no two grazed cells share a common edge (i.e., are not adjacent). Find the total number of valid grazing schemes. $M, N \le 12$.
• Essence of the Problem and Solution Approach: Row-scanning chessboard-style state compression DP. Unlike point set states, this compresses the grazing patterns of "entire rows" into binary.
  • State Design: Let f[i][S] represent the total number of schemes when the first $i$ rows have been decided, and the grazing state of the $i$-th row corresponds to the binary mask $S$.
  • Core Pruning and Conflict Check:
    1. Row Internal Conflict: State $S$ cannot contain consecutive 1s, i.e., it must satisfy (S & (S << 1)) == 0.
    2. Terrain Conflict: State $S$ cannot graze on infertile cells, checked via bitwise AND with the current row's terrain mask.
    3. Row Inter-Conflict: The state $S$ of the $i$-th row and the state $S_{pre}$ of the $(i-1)$-th row cannot be adjacent in the same column, i.e., it must satisfy (S & S_pre) == 0. Through dynamic rolling interleaving between rows, the exponential combinations of the chessboard can be optimized to linear recurrences.