字符串的不相交集合-最小化问题

Question

有两个集合，s1和s2，每个集合都包含字母对。如果一对字母按相同的顺序排列，则它们等效于另一对字母，因此它们本质上是字符串（长度为2）。集合s1和s2是不相交的，没有一个集合是空的，并且每一对字母只出现一次。

以下是这两个集合可能看起来像的示例：

s1 = { ax, bx, cy, dy }
s2 = { ay, by, cx, dx }

在(s1 ∪ s2)中的所有字母的集合称为sl。集合sr是您选择的字母集，但必须是sl的子集。您的目标是定义一个映射m，将sl中的字母映射到sr中的字母，当应用于s1和s2时，将生成包含字母对的集合s1'和s2'，这些集合也必须是不相交的。

最明显的m只是将每个字母映射到它本身。在此示例中（如下所示），s1等同于s1'，s2等同于s2'（但在给定任何其他m的情况下，情况都不是这样）。

a -> a
b -> b
c -> c
d -> d
x -> x
y -> y

目标是构建一个 m，使得 sr（映射右侧的字母集合）中的字母数量最少。为了实现这一点，可以将 sl 中的多个字母映射到 sr 中的同一个字母。请注意，取决于 s1 和 s2，以及取决于 m，你可能会违反 s1' 和 s2' 必须不相交的规则。例如，将 sl 中的每个字母映射到 sr 中的单个字母，显然会违反该规则。

因此，给定 s1 和 s2，如何构建一个 m，使得 sr 最小化，同时确保 s1' 和 s2' 不相交？

以下是问题的简化可视化：

- Joshua Wise

---

根据您当前的公式，没有必要单独处理s1和s2，因为如果您只考虑一个单一集合s = s1 ∪ s2，问题不会改变（即，对于这个新问题的每个解决方案都是原始问题的解决方案，反之亦然）。这是否符合您的意图？ - j_random_hacker

问题的关键在于确保s1'和s2'是不相交的。如果我们假设只有一个输入集合s = s1 ∪ s2，那么对s应用m只会生成一个输出集合s'。问题的关键部分消失了，因为我们不再需要检查两个输出集合是否相交。所以，我认为它们不是同一个问题。 - Joshua Wise

总会有一种解决方案，其中每个字符都映射到一个字符<=它本身。要检查的非同构候选解的数量是集合的划分数（贝尔数），在字符数n的指数超级指数级别。这样慢的算法有趣吗？我认为这个问题可能是NP难问题，但还没有看到缩减。 - j_random_hacker

我正在寻找的解决方案是最小化sr的方案。因此，将每个字符映射到其本身确实是一种解决方案，但不是理想的解决方案。尽管我用字母表字母（英语中有26个字母）来陈述问题，但我正在处理的实际问题使用了256个字母的字母表。因此，存在256 ^ 256种可能的m排列方式。我需要一个可以在真正的计算机上运行的算法，因此蛮力方法行不通。 - Joshua Wise

啊，好的，抱歉我看错了。该应用程序是在优化解析器生成器。实际上，s1和s2是一组字符串，它们是UTF-8编码的Unicode代码点（因此在实际问题中，它们的长度可以为1-4，而不总是长度为2，但我认为这不是重要细节）。如果我能最小化m，那么我就可以生成一个更小（因此更快；缓存未命中更少）的解析器。 - Joshua Wise

Answer 1

这个问题是NP难问题，为了证明这一点，考虑将图着色问题归约到这个问题上。

证明： 设G=(V,E)为我们想要计算最小图着色问题的图形。形式化地说，我们想要计算图的色数，即使得G可用最少的k种颜色进行染色的最小k值。

为了将图着色问题归约到这里所描述的问题，定义：

 s1 = { zu : (u,v) \in E }
 s2 = { zv : (u,v) \in E }

其中z是一个魔术值，仅在构建s1和s2时使用。

通过上述集合的构造，对于任何映射m和任何边(u,v)，我们必须有m(u) != m(v)，否则将违反s1'和s2'的不相交性。因此，任何最优的sr都是用于给图G着色的最优颜色集（除了z），而m是定义哪个节点分配哪种颜色的映射。证毕。

---

上面的证明可能让人产生猜想，认为研究图着色近似可能是一个不错的开始，实际上也很可能是这样，但涉及到一个混淆因素。这个混淆因素是，对于两个元素ab∈s1和cd∈s2，如果m(a)=m(c)，则m(b)≠m(d)。从逻辑上讲，这等同于语句m(a)≠m(c)或m(b)≠m(d)。这种类型的约束条件，在孤立状态下不会自然地映射到类似的图问题（因为存在或语句）。

有方法将此问题制成（二进制）ILP，并以此解决。这可能会给你（略微）劣质结果，相较于定制设计和调整的分支界限实现（假设你想找到最优解），但会与即插即用的求解器一起使用。

如果您更感兴趣于近似（可能具有保证的最佳比率），那么我建议您研究SDP松弛到问题和适当的舍入方案。这种工作水平很可能是一个中小型研究论文所需的。

- ldog

---

感谢您清晰而详尽的回答！ - Joshua Wise