Заполнение бункеров с одинаковым размером
У меня есть 100 групп, и каждая группа имеет несколько элементов внутри. Для перекрестной проверки я хочу сделать пять ячеек, размер которых как можно больше.
Есть ли алгоритм для этой цели.
Пример для 5 групп и 2 корзин:
Group_1: 5
Group_2: 6
Group_3: 2
Group_4: 7
Group_5: 1
Два контейнера будут:
G1 и G2 -> их сумма равна 11.
G3, G4 и G5 -> их сумма равна 10.
3 ответа
Похоже, это связано с проблемой разделения множеств, которая является NP- трудной, но, к счастью, допускает множество хороших алгоритмов аппроксимации и алгоритмов динамического программирования псевдополиномиального времени. Возможно, вы захотите рассмотреть их в качестве отправной точки, поскольку в этой области уже проделана большая работа.
Надеюсь это поможет!
Это не проблема кластерного анализа (я переписал вопрос, чтобы использовать более подходящую для вас формулировку). Кластерный анализ - это задача обнаружения структуры.
Вместо этого взгляните на следующие две проблемы, связанные с информатикой:
- Многопроцессорное планирование - это то, что вам нужно: учитывая n процессоров, распределите задачи так, чтобы наименьшее количество времени не использовалось
- Задача упаковки бинов - это классическая NP-трудная задача, решающая обратную задачу: используйте как можно меньше бинов фиксированного размера для выполнения всех задач.
- Проблема с k-разделением - это, вероятно, то, что вы хотите сделать.
Все они кажутся NP-сложными, поэтому вам нужно использовать только приближение (если у вас большие данные, всего 5 примеров, вы можете легко перебрать все комбинации)
Если вы ищете алгоритм кластеризации (метод разделения) с равным ограничением размера, я бы предложил спектральную кластеризацию. Он удовлетворит ваш спрос на кластеры практически одинакового размера, потому что он решает проблему нормализованного разреза, который пытается найти сбалансированный разрез.