Алгоритм поиска наилучшего назначения групп и объектов с предпочтительной группой

Question

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

Теперь я ищу комбинацию, в которой большинство объектов находятся в группе, которую предпочитал объект. Поскольку количество групп рассчитывается по формуле, которая дает наименьшее возможное число, существуют комбинации, где не все объекты входят в предпочтительный тип группы. Это нормально, потому что я ищу комбинации, в которых большинство объектов входят в предпочтительную группу.

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

Тип группы можно свободно выбирать из запрошенных типов групп.

Есть ли алгоритм, который может решить эту проблему?

Пример

Есть пять объектов. Первым двум не важно, находятся ли они в группе типа A или B . Третий хочет быть в группе типа A , четвертый в группе типа C , а последний хочет быть в типе B .

Размер группы - два. Количество групп рассчитывается по формуле ниже.

Каждый тип группы может быть свободно выбран из запрошенных типов ( A, B или C ).

Редактировать

Подумайте о группах размером 6 и 12 объектов. Одиннадцать из них с предпочтительной группой типа А и один из них с предпочтительной группой типа В. Для 12 объектов и размера группы 6 есть 2 группы. Лучшим решением было бы создать две группы с типом А. Тогда одиннадцать объектов находятся в предпочтительной группе, а один - в группе, которую он не предпочитал. Просто чтобы уточнить, каждый объект должен быть в группе.

Как найти лучшую комбинацию групповых типов? В этом примере, как я могу подключить объект с предпочтительным типом группы B к группе (на графике)? Насколько я понял, Форд Фулкерсон требует, чтобы типы групп уже были известны.

Answer 1

Эту проблему можно решить, используя максимальный поток . В разделе комментариев @ sascha предлагает минимальная стоимость max-flow . Но я думаю, что нет необходимости добавлять стоимость в сеть потока для этой проблемы. Также сложность min-cost max flow больше, чем сложность max flow. Есть несколько алгоритмов для max flow (см. https://en.wikipedia.org/wiki/Maximum_flow_problem#Solutions) с различной сложностью.

Проблема с максимальным расходом: Вы получили сеть потока с пропускной способностью. Теперь вы должны найти максимальный поток от исходного узла к конечному узлу. Например, см. Рисунок ниже:

Преобразование вашей проблемы в проблему максимального потока :

Ваша проблема: вам даны объекты. Каждый объект имеет предпочтительный тип группы (они могут иметь несколько типов групп). Каждая группа имеет емкость, сколько объектов они могут держать. Теперь вы ищете комбинацию, в которой большинство объектов находятся в группе, которую предпочитал объект.

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

Для приведенных вами примеров сеть потоков показана на следующем рисунке:

Вы можете выяснить, какой объект назначен какой группе из пути потока после запуска алгоритма.