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

假设您有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.

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

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

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

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

定义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,位掩码)时遍历所有掩码

现在用DP(0,x)初始化(即简单地填充x的1位的#)
并且使用跟随转换来填充用于i的DP(i,x)> 0:

DP(i,x)= DP(i-1,x){x的1位的#,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状态的输出等于取消的最大数量时,其位掩码就是相应的解决方案,您可以轻松转换回英文字符,即上例中的{c,e}或{a,e}

编辑:
要回复下面的评论,我尝试在此处按部分回复:

Q1.它还是指数吗?只有从指数到#字母#的集合转移?

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

Q2.这个问题NP完整吗?

A2.好的,这是有趣的部分,这是我的想法,如果我错了请纠正我,我认为是NP完全.我的想法是将这个问题模型化为图形问题,请参见下图(裸露我糟糕的mspaint技能)

我们得到了一个二分图,并且与原始问题的意义相同,我们现在想要找到最大完整子图 – 这是一个常见图中的Clique,这是一个众所周知的NP完全问题.

然后我想,这是一个二分图!也许二分图中的Clique不是NP Complete,但是感谢Google,我发现另一个问题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解决方案时也有类似的背包问题的想法……但这与你的问题有点无关……

相关文章
相关标签/搜索