Lagmental Vicfred

Subset DP Makes the Chosen Set an Explicit Coordinate by Vicfred

Last updated: Fri 18 October 2019

tags: mathematics, dynamic programming, semirings, state spaces

A bitmask state records exactly which elements have been used before the next transition. I want the notation, the mechanism, and the failure mode visible at the same time.

Notation

A full dynamic-programming state \(dp[i][s]\) states exactly which prefix \(i\) and mathematical state \(s\) have been processed. The recurrence is a theorem about transitions between these states.

$$ dp[S][v]=\min\{\text{cost of a path using exactly }S\text{ and ending at }v\} $$

The definition determines which expressions are legal; only then does the identity become meaningful. An equality in \(\mathcal A\) may change ambient meaning, so I keep \(\mathsf D\) separate from \(\mathsf C\).

$$ dp[S\cup\{u\}][u]=\min_{v\in S}\{dp[S][v]+w(v,u)\} $$

Stress the formula

The computation below is not a second theorem. It is a checksum for the definitions and a place to inspect the difficult LaTeX at full size.

$$ dp[\{s\}][s]=0,\qquad\operatorname{TSP}=\min_{v\ne s}\bigl(dp[V][v]+w(v,s)\bigr) $$

Interpretation

The compact alignment is a local map of the argument: assumptions on the first row, consequence on the second. Any generalisation must preserve that dependency.

$$ \begin{aligned} \mathsf{D}\;&:\quad dp[S][v]=\min\{\text{cost of a path using exactly }S\text{ and ending at }v\},\\[5pt] \mathsf{C}\;&:\quad dp[S\cup\{u\}][u]=\min_{v\in S}\{dp[S][v]+w(v,u)\}. \end{aligned} $$

Limit of the argument

State compression is an implementation change, not the definition. Loop order is safe only after the uncompressed dependency graph is understood.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] dp[S\cup\{u\}][u]=\min_{v\in S}\{dp[S][v]+w(v,u)\} \end{gathered}} $$

With the dependency made explicit, the same pattern can be recognised safely in nearby problems. A changed hypothesis should now be easy to spot.

This article was posted on Wed 03 October 2018. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.