一类约化解空间法在组合问题中的应用
约化解空间法（Reducing Solution Space）是一类通过减小枚举量从而有效降低时间复杂度的算法。在算法竞赛中，这种算法通常被冠以贪心（Greedy）的名字。本文旨在形式化地探讨这种方法以及其具体应用。而约化解空间的名字来源于泛函分析中不变子空间[1]的概念。
注意本文中所有关于解空间的名词命名均为本文新定义，若有更好的命名方式请联系笔者。
1 Introduction
在泛函分析中不变子空间问题是一个著名的悬而未决的问题，它有时也被乐观地称为不变子空间猜想[1]：
给定一个维度大于 \(1\) 的复希尔伯特空间[2] \(H\)，以及一个有界算子 \(f:H\rightarrow H\)，问是否存在一个 \(H\) 的非平凡子空间 \(W\)(\(W\neq H\) 且 \(W \neq \{0\}\)) 使得 \(f(W)\subseteq W\)。
满足上述条件的子空间 \(W\) 被称为 \(H\) 关于 \(f\) 的不变子空间。
将不变子空间的概念推广到解空间上则有：
Remark 1.1 设组合问题 \(P\) 的解空间为 \(S\)，设存在一个有界算子 \(f:S\rightarrow S\)，若 \(T \subseteq S\)，且 \(f(T)\subseteq T\)，则称 \(T\) 是 \(S\) 关于 \(f\) 的一个不变子解空间。
考虑一种特殊的不变子解空间：
Remark 1.2 设组合问题 \(P\) 的解空间为 \(S\)，设存在一个有界算子 \(f:S\rightarrow S\)，若 \(T \subseteq S\)，且 \(f(T)=T\)，则称 \(T\) 是 \(S\) 关于 \(f\) 的一个最简不变子解空间。
注意到若 \(T_1\)，\(T_2\) 是 \(S\) 关于 \(f\) 的最简不变子解空间，则 \(T_1\cup T_2\) 也是 \(S\) 关于 \(f\) 的最简不变子解空间，于是有：
Theorem 1.1 对于解空间 \(S\) 与有界算子 \(f:S\rightarrow S\)，存在唯一的 \(S\) 关于 \(f\) 的最简不变子解空间 \(T_m\)，对于 \(\forall T\) 是 \(S\) 关于 \(f\) 的最简不变子解空间有 \(T\subseteq T_m\)。
Remark 1.3 我们称 \(T_m\) 为 \(S\) 关于 \(f\) 的最大最简子解空间，或约化子解空间，记作 \(T_m=f_m(S)\)。
为了让约化子解空间在组合问题中得到应用，我们需要对算子 \(f\) 做出一定的限制。
Remark 1.4 对于组合问题 \(P\)，在其解空间 \(S\) 上有一个代价函数 \(g:S\rightarrow K\)，其中 \(K\) 是一个全序集，若有界算子 \(f:S\rightarrow S\) 满足对 \(\forall x \in S\) \(g(f(x))\le g(x)\) 或 \(\forall x \in S\) \(g(f(x))\ge g(x)\)，则称 \(f\) 是关于组合问题 \(P\) 的一个约化算子。其中，若 \(g(f(x))\le g(x)\) 则称 \(f\) 为最小化约化算子，反之则称为最大化约化算子。
于是我们获得了解决组合问题的一个有力工具：
Theorem 1.2 若组合问题 \(P\) 的解空间为 \(S\)，代价函数为 \(g:S\rightarrow K\)，\(K\) 为全序集。若 \(f\) 为 \(P\) 的一个最小化约化算子，则有 \(\min\limits_{x\in S}\{g(x)\}=\min\limits_{x\in f_m(S)}\{g(x)\}\)；若 \(f\) 为 \(P\) 的一个最大化约化算子，则有 \(\max\limits_{x\in S}\{g(x)\}=\max\limits_{x\in f_m(S)}\{g(x)\}\)。
由此，我们通过约化算子 \(f\) 将组合问题的解空间 \(S\) 约化到了 \(f_m(S)\)。只要恰当地选取算子，\(f_m(S)\) 通常可以获得比 \(S\) 更小的空间或者更优的结构，方便进一步枚举、贪心或 DP。
2 Application
2.1 约化解空间法在组合最优化问题中的应用实例
Example 2.1.1 来源 Luogu6832：给定一个字符串 \(\texttt{S}\)，求其出现次数最多的子串的出现次数。
本题解空间可以描述为 \(S=\Sigma *\)，代价函数 \(g:S\rightarrow \mathbb{N}\)，表示串在 \(s\) 中的出现次数。
设 \(f:S\rightarrow S\)，\(f(x)\) 表示 \(x\) 的任一非平凡子串，显然有 \(g(f(x))\ge f(x)\)。所以 \(f\) 为 \(S\) 最大化约化算子。
又 \(f_m(\Sigma *)=\Sigma\)，所以该问题答案为 \(\max\limits_{x\in \Sigma}(g(x))\)。
可以很简单地 \(\mathcal{O}(|\texttt{S}|)\) 求解。
Emample 2.1.2 来源 ICPC 2021 Jiangxi：
Example 2.1.3 来源 Cnoi2021 Cirno's Easy Round II
2.2 约化解空间法在组合存在性问题中的应用实例
Example 2.2.1 来源 XXI Open Cup. Grand Prix of Korea Problem.B：给定数组 \(\{a_n\}\)，\(\{b_m\}\)，矩形平面网格的权值为 \(C_{i,j}=A_i+B_j\)。运动员每次只能向右或向下走一格，不能经过 \(C_{i,j}<0\) 的格子。问存在多少对 \((i,j)\) 使得存在至少一条路径可以从 \((i,1)\) 走到 \((j,m)\)。
考虑每一对 \((i,j)\) 是否存在路径，问题可以转化为是否存在一个能阻隔所有路径的位置集合，其上权值均小于 \(0\)。所以解空间是 \(S=\{p能阻断路径|p\in 2^{\{(x,y)|i\le x\le j,1\le y\le m\}}\}\)。而代价函数 \(g:S\rightarrow \{0,1\}\) 为 \(g(x)=\prod\limits_{(p,q)\in x}[c_{p,q}<0]\)。
构造算子 \(f_1\)。若阻隔点集合为 \(x\)，令 \((m_x,p_m)=\min\limits_{(p,q)\in x}\{(A_p,p)\}\)，\(y\) 为 \(\bigcup\limits_{(p,q)\in x}(p_m,q)\cup x\)。\(f_1(x)=y\)。若 \(g(x)=1\) 则 \(\forall (p,q) \in x\) 有 \(A_p+B_q<0\) 所以 \(\forall (p,q) \in x\) 有 \(m_x+B_q<0\)，所以 \(g(y)=1\)，所以 \(f_1\) 是最大化约化算子。
构造算子 \(f_2\)。若阻隔点集合为 \(x\)，令 \((m_y,q_m)=\min\limits_{(p,q)\in x}\{(B_q,q)\}\)，\(y\) 为 \(\bigcup\limits_{(p,q)\in x}(p,q_m)\cup x\)。\(f_2(x)=y\)。同理可证 \(f_2\) 是最大化约化算子。
构造算子 \(f_3\)。若阻隔点集合为 \(x\)，\(y=x-\bigcup\limits_{(p,q)\in x,p\neq p_m,q \neq q_m}(p,q)\)。\(f_3(x)=y\)。由于 \(y\subseteq x\)，所以 \(g(y)\ge g(x)\)，\(f_3\) 是最大化约化算子。
然后构造 \(f_4,f_5,f_6,f_7\) 分别表示删除 \(x\) 最上，最下，最左，最右的一个点，显然均是最大化约化算子。
所以最终 \((S)f_1f_2f_3f_4f_5 f_6f_7=\{矩形(i,1)-(j,m)中所有的行和列以及包住起点或终点的 L 形\}\)。
于是枚举量大大减小，最后结合一些二分优化可以做到 \(\mathcal{O}(n\log n)\)。
Example 2.2.2 来源 Cnoi2021 Cirno's Easy Round II
References
- 不变子空间问题，维基百科
https://zh.wikipedia.org/wiki/不变子空间问题 - 希尔伯特空间，维基百科
https://zh.wikipedia.org/wiki/希尔伯特空间