N组的最大交集,具有忽略某些集合的能力(设置压缩)

Question

假设您有N组未分类的字符,这些组之间有共同的字符.我想从这些集合中分解出尽可能多的字符以使它们变小.但是将字符分解出来有一个约束:字符必须在你从N中选择的M个集合的交集中.这有点像无损集合压缩算法.以下示例是有序集,但这是为了便于阅读.不要假设将订购套装.

一个简单的例子:

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

答案是只交叉S1和S2并将因子分解出来:ab 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的交集得到:jk l.

abcd不正确的原因是因为当你将这些字符从集合中分解出来时,剩下19个字符,而当你考虑jk和l out时,只剩下18个字符.

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

PS这不是一个紧迫的问题,但我认为这是一个我遇到的有趣问题.

Answer 1

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

将 DP(i, 位掩码) 定义为使用此位掩码对于 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 位），并使用以下转换来填充 DP(i,x)（当 i > 0 时）：

DP(i, x) = DP(i-1,x) + { # of 1-bit of x if (Si & x == x); 0 otherwise} Si is the bitmask of the Set i, & is bitwise and operation

答案是所有 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 技能）

我们得到了一个二分图，与你原来的问题一样，我们现在想要找到最大完全子图——这是一般图中的一个派系，这是一个众所周知的 NP 完全问题。

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

给定一个二分图，测试它是否包含参数 i 的完整二分子图 Ki,i 是一个 NP 完全问题。

总而言之，我认为这是 NP 完全的

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

A3。结合A1，很多NPC问题实际上都有一个伪多项式解，据我所知，O(x * 2^y)是一种很常见的形式，一个例子是哈密顿路径，它可以用O( n^2 * 2^n)。作为额外的一点，如果你问自己，我在思考这个 DP 解决方案时也有类似的背包问题想法......但这与你的问题有点无关......