Минимизация цветов: вариация алгоритма ранца?

Question

Работая над проектом, я столкнулся с этой проблемой, которую я перефразирую здесь в терминах, выходящих за пределы реальной области проблемы (я полагаю, я мог бы поговорить о калибрах фейерверков и форм, но это усложнит понимание). Я ищу (возможно, приблизительный) алгоритм для его решения.

У меня есть n контейнеров разных размеров и m объектов разного размера и разных цветов (объекты могут быть разноцветными, поэтому цвет объекта действительно является набором).

Моя цель - поместить все объекты в контейнеры (я уже знаю, что это возможно) так, чтобы разнообразие цветов было минимизировано для каждого контейнера. Под "разнообразием цветов минимизируется" я подразумеваю, что сумма количества разных цветов в контейнере минимальна.

Пример. У меня есть два контейнера размером 2 и четыре объекта, цвета которых: {красный}, {красный, зеленый}, {синий}, {синий, зеленый}, каждый из которых имеет размер 1. Оптимальным решением будет [{красный}, {красный, зеленый}], [{синий}, {синий, зеленый}], где общее разнообразие составляет 2+2=4. Наихудшим решением было бы [{red}, {blue}], [{red, green}, {blue, green}]], где общее разнообразие составляет 2+3=5.

Я предполагаю, что проблема NP трудна, так как она звучит сложнее, чем проблема ранца: значение объектов преобразуется в отрицательное значение, которое, кроме того, зависит от других объектов в том же контейнере. Но я не имею ни малейшего представления о том, как решить проблему для приблизительного решения, которое в любом случае будет более чем приветствоваться.

Answer 1

Бин-упаковка или рюкзак?

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

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

В вашем случае вы также пытаетесь свести к минимуму количество корзин, только они не могут поместиться менее чем в два. И вы также хотите использовать все объекты. Вы не много говорили об ограничении пропускной способности, но я полагаю, что вы также должны уважать это. Пока что это похоже на проблему с упаковкой в ​​мусорное ведро. У вас также есть одно дополнительное ограничение: минимизировать количество цветов в каждом контейнере.

NP-трудной?

Теперь я начинаю рассказывать вам о том, что это NP-хард - в нем есть все элементы бинарной упаковки и одно дополнительное ограничение. Скажем, сокращение от упаковки в мусорное ведро должно быть легко показать, если использовать экземпляр с объектами, окрашенными в красный цвет. Нам нужно только показать, что проблема в NP - то есть, что мы можем проверить результат за полиномиальное время. Вот, пожалуйста, у нас есть неофициальное доказательство!

Жадный Эвристический Я

Вот жадная эвристика, которая может помочь.

Представление: вместо использования наборов рассмотрим битовую последовательность длины k, где k - это количество различных цветов, которые у вас есть. Итак, скажем, что у вас есть 3 цвета - красный, зеленый, синий. Вы бы представляли [синий] 001, [зеленый, синий] как 011, [красный] как 100 и т. Д.

1. Сортируйте элементы по цветным битовым последовательностям, используя функцию сравнения, которая приводит к упорядочению, например, 001, 010, 100, 011, 110, 111. Вы можете разработать такую ​​функцию сравнения как взвешенную функцию веса Хэмминга битовой последовательности. и его фактическое числовое значение.

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

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

4. Вы продолжаете в том же духе, пока не исчерпаете емкость каждой корзины.

Жадный Эвристик II

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

Заключение

Ни один из этих двух подходов не будет оптимальным, но разве мы не знали об этом? Мы только что набросали неофициальное доказательство того, что проблема NP трудна.

Удачи!