当前位置：首页 > article >正文

【圣明先森】SPP集合划分问题（第二集）

article 2024/11/28 10:56:14

东北师范大学研一学生 jinxi20111 2024.11.27

普通人奋斗半辈子的意义，可能就在于为天才节省一个下午茶的时间。

自从上次更新，正好半年过去了。现在不怕组会了，也不怕找导师汇报了。
但是更恐怖的全英文讲座要来了。
加上就快要写论文了，回到CSDN把这一段时间自己的研究总结一下。

题目

SPP问题——集合划分问题

该问题中，有N个子集和M个约束。每个子集拥有一个代价P。问题要求，选择任意个元素，使得这些子集的并集为全集，并且交集为空集的条件下，代价和最小。

样例数据：
4 5
8 {1 3 5}
6 {2 4}
4 {2 4 5}
2 {2}

该样例中，只有第一个和第二个自己能够构成一个SPP解。1、3组合会导致约束5重复，1、4组合会导致4未出现。
所以答案是 1 2 代价为14

思路

这个问题属于NP-COMPLETE问题，简单描述就是，验证解可行很简单，验证有可行解很难，验证某个解是否最优更难。

摆在面前的有两条路：启发式、遍历

其实在我眼里，启发式是一个时代的中间产物，必然是不能长久的。就像上一章说的，我仍旧认为单位价格的算力水涨船高的情况下，启发式终究会成为一段历史，如马拉火车一般真实而可笑。

并且，我带着以前竞赛的习惯，总是喜欢先有一个稳定而正确的求解器。可以效率不高，但一定要正确。所以我第一个真正小项目：精确求SPP解，就定下来了。

DP

精确求SPP的事情，总会让我想到完全背包。毕竟实在是太像了。

每一个物品都可以拿，但是拿完，会显性的影响一些物品能否选择
在样例中，某些物品组合（A）选择后，可能已经隐性的否决了一些物品（C、D），即，明面上在可选择的集合中，但是一旦选择了，不可能产生可行解或最优解。

可惜，不是单一约束，不能用DP。

深度优先搜索

一种普适的遍历方法。深度搜索作为一个竞赛的一个稳定而正确的求解器，个人实在太熟悉了。
基本当你需要N选M的时候，这玩意就能用。SPP也不例外，当你决定选择A的时候，后续的所有可能如树般展开，这就是DFS深度有限搜索的开始。

但是，众所周知，深搜作为一种遍历方法，其时间复杂度是非常炸裂的。此时，我们需要考虑如何加速这个程序。

加速

先来分析一下时间都去哪儿了。
SPP作为一个组合问题，本质上就是在一堆东西中找组合。那么一个N个物品的组合数量

对于 $N$ 个物体，任选 $0$ 到 $N$ 个的所有可能性数目为：
$2^N$

根据二项式定理，这也可以表示为所有可能子集数量的总和：
$\sum_{k=0}^{N} \binom{N}{k} = 2^N$

非常好理解，每个物品都有选和不选两种可能，互相独立。所以是 $2^N$ 。随手找一个数据集，N的大小都是50往上的，这就代表遍历所有可能性是不能接受的。

那么剩下的就是，如何去掉一些可能性。

PART 1

最先被干掉的就是这颗搜索树上的所有非叶子节点。即：如果仍然有子集可加入，则必然有约束未被选择，必然不是SPP解

所以这颗搜索树有了深搜的模样。

PART 2

组合问题中，如果你选择了X进入组合，则1到X-1之间的所有元素都不再需要考虑。因为任何 X --》 Y（小于X）的搜索路径，都和Y --》X的路径重复。我们只保留其中一种即可。即：这颗树上的任意节点，其子节点都必然大于自身。

其实深搜部分能够给出的优化真的不多，大概就这些了。能够看出来，虽然这两个优化都是数量级级别的，但是对于一个指数膨胀的问题，这些优化还是蚊子腿。当我已经打算放弃的时候，转机出现了。

学姐的研究方向主要是图上的一些启发式算法，图着色、最大团这些。其中一次发言，讲了最大团的一个启发式算法。我一边听，突然就对上思路了。

最大团指的是一个无向连通图中，互相全连接的最大的诱导子图。本身和我这个问题没什么联系。

BUT！如果我将SPP的每个子集当作图中的一个节点，如果两个子集交集为空（也就是可以一起选），则这两个节点相连，否则则不连，那么SPP解一定在图的极大团中。

举个例子：对于样例来说，A和B相连，A和D相连，并且这个图中的极大团，一共就AB，AD和C三个，则SPP解只有可能是AB，AD，C。这就排除了大量的不可行解。

这个构思并不冲撞我的深搜思路，反而因为上了图，有了图这个基础，整个深搜的逻辑变得有迹可循。找SPP解的过程变为了在图上找最大团。并且，找最大团的过程中，只需要计算加法（每个节点所含的约束数），而不再需要反复执行集合操作。这个最大团描述了SPP解在图上的本质，由此又产生了新的优化。

PART 3

其实到这里，这个思路仍然是浮萍一片。因为即使将SPP问题改成最大团去做，并没有将这个问题简单化，反而引入了新的约束。比如说建模成最大团问题后，空间占用简直爆炸。邻接表要存，邻接矩阵也要存。没太多的办法，我把邻接矩阵压缩为了一维，这样读写时间×2，空间占用减半。如果还是不行，可能就得用位运算压缩了，这样还能少8倍。

但是我仍然 ~~敏锐而天才地~~ 发现了其中的优秀之处。

这时候，导师发给我了几篇论文，让我选方向。
Parallelizing Maximal Clique Enumeration on GPUs

导师让我看这篇，其实主要是看看人家的并行咋整的。我这研究方向快大半个学期了还没搞出来，很尴尬的。

我盯着这篇论文，突然意识到了一个问题：我把SPP建模成了最大团问题，为啥不用人家搞好的成熟的算法去做呢？

……

撸起袖子开干。

这是一篇求最大团的遍历算法。由于是求精确解，所以性能不是特别香。但是其中有几个关键思路。Bron-Kerbosch algorithm，求最大团的经典算法
图片来源：上述论文
看起来是个回溯，但就是地地道道的深搜。倒腾来倒腾去，全是性能爆炸的集合操作。你别说反复求交集了，就下面的从集合中移除v，都是个时间开销不小的操作。这玩意可不比p++，p–啊，正经的堆操作。