2

考虑到powerset操作（生成给定集合的所有可能子集）及其庞大性（时间复杂度 O(n*2^n) ），我试图水平扩展它（分布式解决方案）。不知道这是否容易实现（因此提出了问题），但我会尝试分解问题并尽可能清楚地说明问题。

考虑以下使用 python 的示例：

import itertools

s = [1, 2, 3, 4, 5]

for l in range(1, len(s)+1):   # this can be distributed

    for subset in itertools.combinations(s, l):
        print(subset)

根据子集长度分配工作负载是可能的（也很容易）。例如，如果我们有一个长度为 5 的集合，我们可以让每个工作人员计算长度为 N 的所有子集——在这种情况下，我们将有 5 个工作人员。为什么这对我没有吸引力很明显 - 工作负载分配根本不平衡。一组长度为 20 将生成 184756 个长度为 10 的子集，并且只有 20 个长度为 1 的子集（这意味着中间工作人员总是有更多的处理工作要做）。

问题

在这种情况下，有没有办法线性分配工作量，如何？重新表述问题 - 对于一组长度 L，我可以分配工作以使用 N 个平衡良好的工作人员计算 powerset 吗？

4

2 回答 2

2

首先，这不是解决问题的好方法。指数增长意味着所需机器的数量也将呈指数增长。几乎在每种情况下，正确的答案都是“弄清楚如何不计算幂集”。

也就是说，这是分解事物的最简单方法。取第一个“x”元素，并计算这些东西的所有子集。这为您提供了 '2^x' 个工作。将这些作业y相对均匀地分配给机器。每台机器完成每个作业的计算子集并产生输出。

作为进一步的优化，在工人完成时分配工作。这样，如果一些工人跑得很慢，你会让每个人都工作直到你完成。

（还有更平衡的方法，但它们涉及担心你的 powerset 算法是什么。）

于 2015-11-23T18:21:24.833 回答
2

如果您使用整数的 n 位来表示 n 项子集中的项，则可以从 0 开始变量，然后将其递增以到达下一个子集。因此，要在 k 个处理器之间平均分配工作，您可以简单地让处理器 #i 从 i 开始其整数变量，并在每一步将 k 添加到它。每个子集将由一个处理器处理。

请记住，这对帮助您解决大问题没有多大帮助。如果您可以在一台计算机上解决大小为 x 的问题（我估计在今天的计算机上大概有 20 <= x <= 30），那么即使购买 1024 台计算机，您也只能解决大小问题x+10。

于 2015-11-23T18:30:11.197 回答