Нужен какой-то стабильный алгоритм сопоставления

Я даже не уверен, что это стабильная проблема соответствия.

Проблема в том, что у меня 10 человек в группе. Группа должна быть разделена на 2 группы с минимальным размером группы 4. Таким образом, группы 4-6 или 5-5 для размера задачи 10.

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

Я могу попросить группу либо поставить остальных 9 человек в последовательном порядке того, насколько они хотят быть с этим человеком, либо дать им оценку, скажем, от 1 до 10 того, насколько они хотят быть с этим человеком.

Как решить эту проблему?


matching algorithm
person Cheetah    schedule 04.02.2011    source источник
comment
Всегда ли размер ввода равен 10, а минимальный размер группы всегда равен 4?   -  person R. Martinho Fernandes    schedule 04.02.2011
comment
Всегда ли предпочтения людей постоянны или они как-то взвешены, т.е. предпочтения некоторых людей имеют большее значение, чем предпочтения других?   -  person Matti Lyra    schedule 04.02.2011
comment
Возможных конфигураций 462... грубая сила. В общем случае существуют биномиальные [1 + n, n/2]   -  person Dr. belisarius    schedule 04.02.2011
comment
Ну, размер ввода равен 10 или 12, но минимальный размер группы всегда равен 4. Итак, когда у меня есть все возможные конфигурации, как мне выбрать, какая из них лучшая/самая справедливая? Предпочтения у всех одинаковые, ни один человек не важнее другого.   -  person Cheetah    schedule 04.02.2011

Ответы (1)


arrow_upward
2
arrow_downward

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

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

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

person R. Martinho Fernandes    schedule 04.02.2011