Параллельный алгоритм разбиения множеств

Я думаю, что вы пытаетесь сделать что-то более сложное, чем необходимо - вам действительно нужно точное решение (глобальный оптимум)? Что касается эвристического решения, я должен был сделать что-то подобное в прошлом, поэтому вот мое мнение:

Переформулируйте задачу следующим образом: у вас есть вектор с заданным средним (' глобальное среднее », и вы хотите разбить его на куски так, чтобы означало, что каждого отдельного фрагмента будет как можно ближе к« глобальному среднему ».

Просто разбейте его на куски случайным образом, а затем итеративно меняйте элементы между кусками, пока не получите приемлемые результаты. Вы можете поэкспериментировать с разными способами, как это сделать, здесь я просто перетасовываю элементы чанков с минимальным максимальным «средним значением чанка».

В общем, чем больше размер фрагмента, тем легче он становится, потому что первое случайное разбиение уже даст вам неплохое решение (подумайте, например, «образец»).

Насколько велик ваш список ввода? Я проверил это на входе 100000 элементов (равномерное распределение целых чисел). С 50 кусками по 2000 элементов вы получите результат мгновенно, а с 2000 кусками по 50 элементов вам нужно подождать < 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