首页 / PYTHON / python – 最小集合覆盖
python – 最小集合覆盖
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python – 最小集合覆盖，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2724字，纯文字阅读大概需要4分钟。
内容图文
我想解决以下类型的最小集合覆盖问题.所有列表仅包含1和0.
我说如果你可以通过插入x个符号从A中制作B,那么列表A将覆盖列表B.
考虑长度为n的1和0的所有2 ^ n列表并设置x = n / 3.我想计算一组长度为2n / 3的最小列表,它们涵盖了所有这些列表.
这是我开始的一种天真的方法.对于每个可能的长度为2n / 3的列表,我创建了一组我可以使用此函数创建的所有列表(由DSM编写).
from itertools import product, combinations
def all_fill(source, num):
output_len = len(source) + num
for where in combinations(range(output_len), len(source)):
# start with every possibility
poss = [[0,1]] * output_len
# impose the source list
for w, s in zip(where, source):
poss[w] = [s]
# yield every remaining possibility
for tup in product(*poss):
yield tup
然后我使用n = 6作为示例创建如下的集合集.
n = 6
shortn = 2*n/3
x = n/3
coversets=set()
for seq in product([0,1], repeat = shortn):
coversets.add(frozenset(all_fill(seq,x)))
我想找到一个最小的集合集合,其联合是allset = set(product([0,1],repeat = n)).
在这种情况下,设置(all_fill([1,1,1,1],2)),set(all_fill([0,0,0,0],2)),set(all_fill([1,1,0] ,0],2)),设置(all_fill([0,0,1,1],2))会做.
我的目标是解决n = 12的问题.我很乐意使用外部库,如果这将有所帮助,我希望在最坏的情况下n的指数时间.
解决方法:
我写了一个小程序来编写一个整数程序来解决
CPLEX或其他MIP求解器.下面是n = 12的解决方案.
from collections import defaultdict
from itertools import product, combinations
def all_fill(source, num):
output_len = (len(source) + num)
for where in combinations(range(output_len), len(source)):
poss = ([[0, 1]] * output_len)
for (w, s) in zip(where, source):
poss[w] = [s]
for tup in product(*poss):
(yield tup)
def variable_name(seq):
return ('x' + ''.join((str(s) for s in seq)))
n = 12
shortn = ((2 * n) // 3)
x = (n // 3)
all_seqs = list(product([0, 1], repeat=shortn))
hit_sets = defaultdict(set)
for seq in all_seqs:
for fill in all_fill(seq, x):
hit_sets[fill].add(seq)
print('Minimize')
print(' + '.join((variable_name(seq) for seq in all_seqs)))
print('Subject To')
for (fill, seqs) in hit_sets.items():
print(' + '.join((variable_name(seq) for seq in seqs)), '>=', 1)
print('Binary')
for seq in all_seqs:
print(variable_name(seq))
print('End')
MIP - Integer optimal solution: Objective = 1.0000000000e+01
Solution time = 7.66 sec. Iterations = 47411 Nodes = 337
CPLEX> Incumbent solution
Variable Name Solution Value
x00000000 1.000000
x00000111 1.000000
x00011110 1.000000
x00111011 1.000000
x10110001 1.000000
x11000100 1.000000
x11001110 1.000000
x11100001 1.000000
x11111000 1.000000
x11111111 1.000000
All other variables matching '*' are 0.
CPLEX>
内容总结
以上是互联网集市为您收集整理的python – 最小集合覆盖全部内容，希望文章能够帮你解决python – 最小集合覆盖所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。