Мне нужен алгоритм построения команды, который принимает во внимание ограничения

Question

Мой сценарий таков:

У нас есть определенный набор позиций, каждый из которых должен заполнять человек. Но Позиция требует определенных c навыков. Итак, пусть позиция будет [], и у нас будут разные навыки, такие как A, B, C, D. Теперь Позиции [A, C] нужен Человек, имеющий навыки A и C. У нас есть пул людей на выбор. Каждый человек имеет свой набор навыков и находится в разных местах. Но мы хотим, чтобы физически самый близкий человек, который также обладает необходимыми навыками, получил эту должность.

Каким был бы способ найти оптимальное решение?

Answer 1

Вам просто нужно решить типичную задачу согласования максимального веса .

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

Определите вес ребра от позиции к человеку как нечто такое же большое, как человек, и местоположения позиций близки к друг с другом - например, 1 / distance(person, position) или some_constant - distance(person, position).

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