专访小W

· · 生活·游记

特别鸣谢:灵感来自 interesting_soul_zjy 的 CCF:造干净的地铁。

记者:听说你打算在D国挑城市建研发基地,有个要求是选出来的基地最多只能连成两大片,不少人觉得很奇怪,能说说吗?

小W:这是基础可行条件。我们选取的城市构成集合 S,必须满足 |S|=k,且 S 在树 T 上导出子图的连通块数目 \le 2。连通块数取1的时候,整个集群强耦合,单点故障很容易沿着树边扩散,引发全域瘫痪;连通块数 \ge 3 时,跨集群的数据同步、资源调度带来的通信开销会非线性上涨。连通块上限设为2,是协同成本与故障鲁棒性之间的平衡点。一般人只能想到分散避险,识别不出多集群带来的隐性代价,理解不了也正常。

记者:原来是这样,这个权衡思路还挺有意思的。那还有别的硬性要求吗?

小W:当然,预算给出了硬性约束,要求 |S|=k,基地数量必须恰好为 k,不能多、不能少。预算边界是固定的,所有候选方案都被卡在这个等式约束里。普通人总想着灵活增减点位,但顶层规划的第一步,就是承认硬约束,在给定范围内求解,不是所有人都有这个思维习惯。

记者:哦,预算卡死数量,这点我明白了。我还听到有人问,评判好坏的时候为什么连那些偏僻小城都要算进去,那些地方本来就不做实验啊?

小W:我们定义每个节点 i 的通勤距离 d(i)=\min\limits_{j\in S}\operatorname{dist}(i,j),其中 \operatorname{dist}(i,j) 代表树上 i,j 两点最短路经过的边数。本次优化目标是最小化通勤半径 \displaystyle \max_{i=1}^{n}d(i),属于典型的极小极大问题。我优化的是最坏情况的通勤上界,而不是平均距离 \dfrac{1}{n}\sum_{i=1}^{n}d(i)。平均距离好看毫无意义,极端点位才是整套网络的短板。

记者:嗯,最坏情况优先考虑。那如果不限制只能两大片,拆成三四堆基地,是不是能让这个最远距离变得更小?

小W:确实存在这种样例,但这类方案不在我们的可行域之内。优化永远是在约束划定的集合内部寻找极值,很多人混淆无约束最优解和带约束最优解,拿不受限制的选址方案来对比,自然会质疑这套框架。

记者:好,我大概清楚这个区别了。那我们是不是差不多可以收尾了?

小W:整套问题写完整就是 \displaystyle \min\Big(\max_{i=1}^{n}\big(\min_{j\in S}\operatorname{dist}(i,j)\big)\Big),约束为 |S|=k,S 的导出子图连通块数 \le 2,底层载体是树 T。这是一个自洽完备的树上离散选址模型,逻辑链条没有缺口。只是大部分人只有生活直觉,没有离散优化的基础,体会不到这个模型的精巧之处。

记者:是,听起来逻辑很完整。就是公式有点多,脑子慢慢转不动了。

小W:而且载体是树这个前提也很关键,树任意两点路径唯一,\operatorname{dist}(i,j) 的定义是良定的,没有环带来的多路径干扰,这也给整个问题的求解奠定了基础,换做一般图,难度会完全不一样。很多人忽略树结构带来的简化,只会笼统地讨论选址,抓不住核心。

记者:嗯,了解了。

小W:更进一步,这个极小极大目标天然适合二分框架判定可行性,给定一个阈值 mid,我们只需要检验是否存在满足约束的集合 S,使得对所有 i 都有 d(i)\le mid,这也是这个模型好求解的重要原因。

记者:行。

小W:二分的核心判定子问题同样可以拆成两种情况。第一种,S 本身是单个连通块,也就是连通块数目等于1,等价于在树上选出大小为 k 的连通点集,使得树上所有点到这个连通块的距离不超过 mid。第二种,S 由两个互不相交的连通块组成,两块合起来一共 k 个点,树上所有点到这两块中更近一块的距离同样不能超过 mid。两种情形分开核验,就覆盖了全部可行域。

记者:这样啊,要分开查两种情况,听着就麻烦。

小W:很多人会误以为两种情况的判定难度相近,实际上双连通块的情况复杂得多。我们要找一对互不连通的连通子集 S_1,S_2,满足 |S_1|+|S_2|=k,同时 \forall i,\ \min\big(\operatorname{dist}(i,S_1),\operatorname{dist}(i,S_2)\big)\le mid。它不能简单套用单连通块的贪心策略,需要考虑两块之间的位置关系,两块不能靠得太近,也不能分得太远,否则会出现覆盖盲区。

记者:我懂了,这块要考虑的东西更多。

小W:不止如此。当我们固定二分阈值 mid 之后,每个基地能覆盖的区域就是它在树上距离不超过 mid 的闭邻域。单块方案就是用一个连通的、大小为 k 的点集,它的邻域吞并整棵树;双块方案是两个连通点集的邻域的并覆盖整棵树,总点数之和等于 k。这个覆盖视角,能把选址问题等价转化为覆盖问题,很多人看不到这个转化。

记者:确实,换个角度看就不一样。不过这么绕,普通人哪里想得过来。

小W:还有一个容易被忽略的边界。当 k=n 的时候,S 就是全部节点,此时通勤半径必然是0,不管连通块限制如何,\max\limits_{i=1}^{n}d(i)=0 恒成立。这个边界条件可以直接作为特判,避免算法做无用的遍历。还有 k=2 的特例,对应选两个点,恰好就是双连通块最简单的版本,是这个一般模型的退化情况。

记者:还有这些特殊情况啊,细节真不少。

小W:对。而且因为原图是树,我们预处理直径、BFS分层、子树大小这些基础信息的时候,都可以线性完成,保证整体复杂度能够承载 n 到 10^6 规模的数据。如果没有树这个特殊结构,想要在线性或者线性对数的时间内完成判定几乎不现实。这套模型从目标、约束到底层结构,层层咬合在一起,不是随手拼凑出来的想法。

记者:好。

小W:大多数普通人评判方案的时候,只会拿几组小例子凭感觉比较,看不到这个模型可以统一囊括所有输入规模。他们纠结为什么不能三块四块,本质上是拒绝接受预设的约束集合,分不清“我想要什么布局”和“在这套体系下什么布局是合法可行的”。约束不是缺陷,是整个规划框架的一部分。

记者:嗯,我记下了。说实话,光听这些,我已经快忘了一开始想问什么了。

小W:最后再总结一遍。我们求解

\min_{S}\ \max_{i=1}^{n}\left(\min_{j\in S}\operatorname{dist}(i,j)\right) |S|=k,\quad \text{连通块数}(S)\le 2

在树 T 上。整个问题是自洽的,最优解一定存在,二分+树上可行性判定是成熟的求解路径。能看懂这套框架的人不多,这也是很正常的事情。

记者:根本没有这样的研究基地。

小W:你只是怕了。你们凡人触碰不到罢了,这可是CCF的基地!

记者:奥奥奥奥,这样一切都说得通了。