algorithm - 具有忽略某些集合的能力的 N 集合的最大交集(集合压缩)

Question

假设你有 N 组未排序的字符，这些组之间有共同的字符。我想从这些集合中提取出尽可能多的字符，使它们更小。但是将字符分解出来有一个限制条件:字符必须位于您从 N 中选择的 M 个集合的交集中。这有点像无损集合压缩算法。下面的示例是有序集，但这是为了便于阅读。不要假设集合是有序的。

一个简单的例子:

S1 = a b c d
S2 = a b c e f
S3 = a f g

答案是仅将 S1 和 S2 相交并分解出:a b c。这将删除 6 个字符，而任何其他集的交集组合将删除更少。

一个棘手的例子:

S1 = a b c d e f g h i
S2 = j k l m n
S3 = j k l o p q
S4 = j k l
S5 = a b c d

答案是忽略集合 S1 和 S5，取其余集合 S2、S3 和 S4 的交集得到:j k l。

a b c d 不正确的原因是，当你将这些字符从集合中分解出来时，剩下 19 个字符，而当你分解 j k 和 l 时，只剩下 18 个字符。

有没有一种算法可以比指数时间更快地解决这类问题？似乎您必须测试集合的幂集中每个集合的交集 ({}, {S1}, {S2}, {S3}, {S1, S2}, {S1, S3}, {S2 , S3}, {S1, S2, S3}) - 如果只有 3 个集合，则要计算 8 个交点。

附言这不是一个紧迫的问题，但我认为这是我遇到的一个有趣的问题。

Answer 1

如果字母表的大小不是太大...我会使用动态规划来解决这个问题...运行时间应该是 O(S*2^n), S = # of sets, n = # of字母表

定义 DP(i, bitmask) 为 set-0 到 set-i 中的任何子集可以取消的最大字符数，使用此位掩码

比如我们现在有3组5个字母{a,b,c,d,e}

S0 = {a,d,e}, S1 = {b,c,e}, S2 = {a,c,e}

尝试使用0-1位来屏蔽每组:

S0 = 11001 = 25，S1 = 10110 = 22，S2 = 10101 = 21

总共有 2^5 种不同的可能掩码，我们将在计算 DP(i, bitmask) 时遍历所有掩码

现在用 DP(0, x) 初始化(即简单地填充 x 的 1 位的#)并使用以下转换为 i > 0 填充 DP(i,x):

DP(i, x) = DP(i-1,x) + { # of 1-bit of x if (Si & x == x); 0否则}
si是Set i的位掩码，&是按位与运算

答案是所有x的DP(S-1, x)的最大值

如果有很多可能的解决方案，这种方法可以找到所有可能的解决方案，下面是解决上述示例的 C++ 示例代码:

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

int s[3] = {25,22,21};
int dp[5][1<<5] = {0};

int bits(int x){
    int cnt = 0;
    while(x){ cnt += (x&1); x>>=1;}
    return cnt;
}

int main() {
    for(int i=0; i< (1<<5); i++) if((s[0]&i) == i){ dp[0][i] = bits(i); }

    for(int i=1; i<3;i++)
        for(int j=0; j< (1<<5); j++){
            dp[i][j] = dp[i-1][j];
            if((s[i]&j) == j) {dp[i][j] = max(bits(j), dp[i-1][j]+ bits(j));      }
        }


    int x = -1;
    for(int i=0; i< (1<<5); i++){
        x = max(x, dp[2][i]);
        printf("Maximum cancelled: %d,  current DP: %d, bitmask: %d\n", x, dp[2][i], i);
    }
    return 0;
}

每当 DP State 的输出等于最大取消数时，它的位掩码就是对应的解决方案，你可以很容易地转换回英文字符，即上例中的 {c,e} 或 {a,e}

已编辑:为了回复下面的评论，我试着在这里逐个部分地回复:

Q1。它仍然是指数级的吗？仅从指数到集合的数量转移到字母的数量？

A1。是的。我有这个想法，因为我认为实际上字母表的大小不会太大......但理论上是的，它仍然是指数时间

Q2。这个问题是 NP 完全的吗？

A2。好的，这是有趣的部分，这是我的想法，如果我错了请纠正我，我认为是的，它是 NP Complete。我的想法是将这个问题建模为图形问题，请参见下图(裸露我可怜的 mspaint 技能)

我们得到了一个二分图，在与您的原始问题相同的意义上，我们现在想要找到最大完整子图 -- 那是一个Clique在一般图中，这是一个著名的 NP 完全问题。

然后我想，这是一个二分图!也许二分图中的Clique不是NP完全的，但感谢谷歌，我发现了另一个问题Complete Bipartite Graph并关注页面中的第一个属性:

Given a bipartite graph, testing whether it contains a complete bipartite subgraph Ki,i for a parameter i is an NP-complete problem.

总而言之，我认为这是 NP-Complete

Q3。如何想出这样的 DP 解决方案？

A3。结合 A1.，许多 NPC 问题实际上有一个伪多项式解，据我所知，O(x * 2^y) 是很常见的形式，一个例子是 Hamiltonian Path ，可以在 O(n^2 * 2^n) 中解决。另外，如果你问我自己，在考虑这个 DP 解决方案时，我对背包问题也有类似的想法......但这与你的问题有点无关......