一组中最大可能数量的不相交子集

Question

我给了一组列表,例如:

[[0, 1, 3], [0, 2, 12], [6, 9, 10], [2, 4, 11], [2, 7, 13], [3, 5, 11], [3, 7, 10], [4, 10, 14], [5, 13, 14]]

我需要找到此列表包含的最大不相交子集数.在这种情况下,答案是4.

另一个例子是列表: [[0, 1, 12], [0, 4, 11], [0, 7, 19], [0, 15, 17], [0, 16, 18], [1, 4, 16], [1, 13, 25], [2, 4, 23], [2, 10, 27], [2, 12, 19], [2, 14, 22], [2, 16, 20], [3, 6, 13], [3, 7, 22], [3, 10, 14], [3, 20, 26], [4, 7, 13], [4, 17, 22], [5, 7, 25], [5, 9, 22], [5, 10, 21], [5, 11, 23], [5, 12, 20], [5, 13, 16], [5, 14, 15], [6, 7, 17], [6, 10, 23], [7, 11, 20], [7, 14, 27], [7, 18, 23], [8, 12, 26], [8, 14, 17], [8, 22, 23], [11, 12, 18], [12, 17, 21], [12, 23, 25], [13, 19, 20], [13, 21, 24], [18, 20, 25], [18, 24, 26], [19, 24, 27]] 这里的答案是8.

我知道这个问题是NP难的,所以我想出了一个半蛮力的方法来做到这一点.

我首先通过将子集添加到不相交的子集列表中来获得近似答案.因此,每当我遍历一个集合时,我都会检查它是否已存在于不相交的子集列表中.如果不是,我将其添加到列表中.这给了我一个大概数字,可能是也可能不是最大可能的子集数.

def is_disjoint(disjoints, i, j, k):
    disjoints_flat = list(chain.from_iterable(disjoints))
    if (i in disjoints_flat) or (j in disjoints_flat) or (k in disjoints_flat):
        return False
    return True

.... other code 

# disjoint determination
n_disjoints = 0
disjoints = []

# sets is the input
for set in sets:
    if is_disjoint(disjoints, set[0], set[1], set[2]):
    if is_dis:
        n_disjoints += 1
        disjoints.append(set)

在获得球场后,我迭代地检查更高的可能值.为此,我尝试k从给定的一组值生成所有可能大小的子集(k初始化为上面获得的数字),然后我尝试检查是否可以找到不相交的子集.如果我这样做,那么我检查k+1大小的子集.但是,在生成k可能的子集时,我的代码运行速度非常慢.我希望有人能提出任何方法来加速解决方案.这是蛮力搜索部分的代码.

def is_subset_disjoint(subset):
    disjoints = []
    n_disjoints = 0
    for set in subset:
        if is_disjoint(disjoints, set[0], set[1], set[2]):
            disjoints.append(set)
            n_disjoints += 1

    if n_disjoints == len(subset):
        return True
    return False

..... other code 

curr = n_disjoints+1
while n_disjoints <= n_sets:
    all_possible_subsets = [list(i) for i in combinations(sets, curr)] # This runs really really slowly (makes sense since exponential for large values)
    for subset in all_possible_subsets:
        if is_subset_disjoint(subset):
            n_disjoints += 1
            curr += 1
            continue
    break

Answer 1

如前所述，您应该将问题简化为寻找最大独立集，然后可以将其简化为最大团问题。

我刚刚实现了相当快的算法，我很高兴与您分享它，但我没有任何力量来解释它，因为它足够复杂和精密。您可以在这里查看核心思想。

请随意使用此代码：https://gist.github.com/mingaleg/e1872483d0d0618fe1acacccbf741050

在您提供的大列表中作为示例，它适用于6 sec（0.5 sec如果您正在使用pypy）。