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

Question

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

Значения [1, 2, 4, 5] и n = 2, выходные ковши должны быть [sum(5+1), sum(4+2)].

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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

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

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