python - 集合 split 的并行算法

Question

我正在尝试解决子部分集的问题。

输入数据是列表和整数。 案例是将一个集合划分为N个元素的子集，这些子集的元素之和几乎相等。由于这是一个 NP-hard 问题，我尝试了两种方法: a) 迭代所有可能性并使用 mpi4py 将其分发到许多机器(100 个元素和 20 个元素子集以上的列表工作时间过长) b) 使用 mpi4py 将列表发送到不同的种子，但在这种情况下，我可能会多次计算相同的集合。例如，在 60 秒内有 100 个数字和 5 个子集，每个子​​集有 20 个元素，我的结果很容易通过人类简单地查找表格来更好。

最后我正在寻找启发式算法，它可以在分布式系统中计算并从更大的集合中创建 N 元素子集，其总和几乎相等。

a = [range(12)]
k = 3

一种可能的解决方案:

[1,2,11,12] [3,4,9,10] [5,6,7,8] 

因为总和是 26, 26, 26

并非总是可以创建完全相等的总和或数量 元素。中最大元素数和最小元素数的区别 集合可以是 0(如果 len(a)/k 是整数)或 1。

编辑 1:

我研究了两个选项:1. 父级生成所有迭代，然后发送到并行算法(但这对我来说很慢)。 2. 父节点发送一个列表，每个节点生成自己的子集，并在限定时间内计算子集和。然后将最好的结果发送给 parent 。 parent 收到了这个结果，并选择了最好的一个，使子集中的总和之间的差异最小化。我认为第二种选择有可能更快。

最好的问候， 什切潘

Answer 1

我认为您正在尝试做一些比必要的更复杂的事情 - 您真的需要一个精确的解决方案(全局最优解)吗？关于启发式解决方案，我过去不得不按照这些思路做一些事情，所以这是我的看法:

将问题重述如下:您有一个具有给定均值(“全局均值”)的向量，您希望将其分解成多个 block ，使得每个个体的均值 block 将尽可能接近“全局平均值”。

只需将其随机分成 block ，然后在 block 之间迭代交换元素，直到获得可接受的结果。您可以尝试不同的方法来做到这一点，这里我只是用最小值和最大值 'chunk-mean' 重新洗牌元素。

一般来说， block 越大，它变得越容易，因为第一个随机分割已经给你一个不那么糟糕的解决方案(想想样本均值)。

您的输入列表有多大？ 我用 100000 个元素输入(均匀分布整数)对此进行了测试。对于 50 个 2000 元素的 block ，您可以立即获得结果，对于 2000 个 50 元素的 block ，您需要等待 <1 分钟。

import numpy as np

my_numbers = np.random.randint(10000, size=100000)
chunks = 50
iter_limit = 10000
desired_mean = my_numbers.mean()
accepatable_range = 0.1

split = np.array_split(my_numbers, chunks)

for i in range(iter_limit):
    split_means = np.array([array.mean() for array in split]) # this can be optimized, some of the means are known
    current_min = split_means.min()
    current_max = split_means.max()
    mean_diff = split_means.ptp()
    if(i % 100 == 0 or mean_diff <= accepatable_range):
        print("Iter: {}, Desired: {}, Min {}, Max {}, Range {}".format(i, desired_mean, current_min, current_max, mean_diff))
    if mean_diff <= accepatable_range:
        print('Acceptable solution found')
        break
    min_index = split_means.argmin()
    max_index = split_means.argmax()
    if max_index < min_index:
        merged = np.hstack((split.pop(min_index), split.pop(max_index)))
    else:
        merged = np.hstack((split.pop(max_index), split.pop(min_index)))
    reshuffle_range = mean_diff+1
    while reshuffle_range > mean_diff:
        # this while just ensures that you're not getting worse split, either the same or better
        np.random.shuffle(merged)
        modified_arrays = np.array_split(merged, 2)
        reshuffle_range = np.array([array.mean() for array in modified_arrays]).ptp()
    split += modified_arrays