Группировка произвольных массивов данных в N бинов

Question

Я хочу сгруппировать массив случайных значений произвольного размера в группы n, чтобы сумма значений в любой одной группе / корзине была как можно больше.

Таким образом, для значений [1, 2, 4, 5] и n = 2 выходные сегменты должны быть [sum(5+1), sum(4+2)].

Некоторые возможности, которые происходят со мной:

• Первый полный поиск
• Случайные процессы с жестко запрограммированными условиями остановки
• Начать с одного конца отсортированного массива, группируя до тех пор, пока сумма не станет равна глобальному среднему, и переходить к следующей группе, пока не будет достигнут n

Похоже, что оптимальное решение (где сумма содержимого бинов максимально равна заданному входному массиву), вероятно, нетривиально; так что в данный момент я склоняюсь к последнему варианту, но есть ощущение, что я, возможно, упускаю более элегантные решения?

Answer 1

Это NP-сложная проблема. Другими словами, невозможно найти оптимальное решение без изучения всех комбинаций, и число комбинаций равно n ^ M (где M - размер вашего массива, а n - количество бинов). Эта проблема очень похожа на кластеризацию , которая также является NP-сложной.

Если ваш набор данных достаточно мал, чтобы справиться с ним, лучше использовать алгоритм перебора (изучите все комбинации).

Однако, если ваш набор данных большой, вам понадобится алгоритм полиномиального времени, который не даст вам оптимального решения, но даст хорошее приближение. В этом случае я предлагаю вам использовать что-то похожее на K-Means ...

Шаг 1. Рассчитайте ожидаемую сумму для бина. Пусть A будет вашим массивом, тогда ожидаемая сумма для бина будет SumBin = SUM (A) / n (сумма всех элементов в вашем массиве за количество бинов).

Шаг 2. Поместите все элементы вашего массива в некоторую коллекцию (например, в другой массив), которую мы назовем Сумка (это просто концептуально, поэтому вы понимаете следующие шаги).

Шаг 3. Разделение Мешка на n групп (желательно случайным образом, так что каждый элемент заканчивается в некотором бункере i с вероятностью 1 / п ). В этот момент в ваших корзинах есть все элементы, и Сумка пуста.

Шаг 4. Рассчитайте сумму для каждого бина. Если результат совпадает с последней итерацией, exit . (это ожидание шаг K-средних )

Шаг 5. Для каждого бина i , если его сумма больше SumBin , выберите первый элемент больше SumBin и поместите его обратно в сумка ; если его сумма меньше SumBin , выберите первый элемент меньше SumBin и поместите обратно в The Bag . Это шаг градиентного спуска (он же максимизация * шаг 1060 *) K-Means .

Шаг 6. Перейти к шагу 3.

Этот алгоритм является лишь приблизительным, но он быстрый и гарантированно сходится.

Если вы скептически относитесь к рандомизированному алгоритму, подобному описанному выше, после первой итерации, когда вы вернетесь к шагу 3, вместо случайного назначения элементов, вы можете сделать это оптимально, запустив Венгерский алгоритм , но я не уверен, что это гарантирует лучшие общие результаты.