Алгоритм эффективного распределения «навыков» по ​​«предприятиям» - проблема стабильного брака

Question

Игра Крошечная Башня имеет различные «Битизены», которые имеют квалификацию 0-9 в различных атрибутах:

Michael:  
 a) retail: 9
 b) creative: 2
 c) service: 7
 d) recreational: 4
 e) food: 6

И затем есть бизнес, в котором могут работать три Битизена.Каждый бизнес попадает в одну из категорий: розничная торговля, креатив, сервис, отдых и питание.Никогда не существует никакого совпадения между количеством предприятий или Bitizens, но чтобы упростить ситуацию, мы можем предположить, что количество позиций соответствует количеству Bitizens.

Например, может быть Hat Shop, который является розничнойбизнес, поэтому Bitizens с высокими значениями retail являются благоприятными.В приведенном выше примере Micheal отлично подходит для работы в розничной торговле.

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

Answer 1

Давайте предположим, что дополнительная «точка» одинаково ценна, независимо от того, где вы ее положили.Например, если у вас есть два предприятия: креативное и продовольственное, мы предполагаем, что всегда лучше иметь в общей сложности 20 креативных и 3 продовольственных, чем иметь 11 в каждом.

В этом случае ваша проблемапример проблемы Назначение .Известно, что это «легко», поскольку ее можно решить за полиномиальное время, в частности, за время O (n ^ 3). Венгерский алгоритм является стандартным методом решения этой проблемы.Я не могу объяснить это лучше, чем страница википедии, которая довольно подробная, но если вы застряли там с чем-то, просто спросите.

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

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

Answer 2

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

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