2

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

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

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

那么，是否有人对此类实例的良好来源有任何想法，或者可能对生成它们的方式有任何想法？

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

首先，我搜索了一些测试实例来解决设置覆盖问题。我期望找到的是一些像我上面描述的例子。运气不好，我发现了类似的东西。我必须说，链接中没有太多细节可以让我了解这些情况。

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

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，所以我的疑虑就在哪里，所以这就是为什么我需要一些已经生成的测试实例。

4

1 回答 1

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}]
于 2017-05-27T15:00:53.300 回答