集封面：生成测试实例

Question

我期待使用遗传算法解决 Set Cover Problem。我一直在到处寻找一些好的测试实例，但没有取得任何大的成功。

我正在寻找的是以下形式的一些实例：集合 U = {1,2,...,n} 及其子集 S={{1,2}, { 4}, {3,4,5}},其中S的并集是U.

当然这是一个小例子，因为我想找一些更大的例子。

那么，有没有人知道此类实例的良好来源，或者可能知道生成它们的方法？

稍后编辑：所以我看到这个问题被搁置了。那我不好，我会添加更多细节。

首先，我用谷歌搜索了一些场景覆盖问题的测试实例。我期望找到的是一些像我上面描述的例子。真倒霉，我找到了类似于 this 的东西。我必须说 link 中没有那么多细节可以借给我这些实例。

所以我开始思考生成它们的方法。伪代码解决方案：

given set G=[1,2....,n]
no_of_subsets  = random integer
subsets = []
for i in k: 
    subset = random.sample(G, random(0, len(G))
    subsets.add(subset)

虽然我不确定 union(subsets) 是否 = G，所以我的疑虑就在这里，所以这就是为什么我需要一些已经生成的测试实例。

Answer 1

您可以生成一个集合，从可能的数字列表中获取随机样本。他们还通过获取随机大小的随机样本来生成其子集的列表（具有预定大小），对于最后一个子集，您只需完成缺少的内容，因此子集的总和将是整个集合。

示例：

import random

n = 100
m = 10 #size of set
l = 5 #size of list of subsets
possible_numbers = range(n)

U = set(random.sample(possible_numbers, m))

subsets = []
control = set()
for i in range(l - 1):
    sub_size = random.randrange(m)
    sub = set(random.sample(U, sub_size))
    subsets += [sub]
    control |= sub

rest = U - control     
if rest:
    subsets += [rest]

print(U)
--> {97, 99, 69, 9, 15, 52, 53, 55, 28, 30}

print(subsets)
--> [{28, 52, 69, 55}, {69}, {99, 28, 52, 55}, {69, 9, 15, 52, 53, 55}, {97, 30}]

集封面：生成测试实例

Set cover: Generating test instances

python

set

genetic-algorithm

set-cover