Позвольте мне описать проблему в форме небольшого фантастического рассказа.
История
В Дивном Новом Свете новые города строятся за пару дней и нуждаются только в заселении.Более того, нет более длительного скучного процесса найма, никаких собеседований и субъективных решений - каждый человек проходит несколько тестов, и их результаты используются для поиска лучших сотрудников.
Когда строится новый город, несколько компаний размещают там свои офисы и просят Super Mind найти лучших сотрудников для них, предоставляя способ подсчитать балл человека для их конкретная компания .Люди на их стороне просят Super Mind найти работу для них.Они дают ему список компаний , где они хотели бы работать вместе с соответствующими приоритетами .Super Mind очень гуманистичен, поэтому его задача - найти такое соглашение , что люди доберутся до лучших компаний, которые они хотят , даже если некоторые компании вообще останутся без сотрудников.
Формальное определение
Теперь позвольте мне определить задачу более формально.
E - количество работников, ищущих работу.C - количество компаний. S(e,c) - количество сотрудников e для компании c. Pr(e,c) - приоритет компании c в личном списке желаний сотрудника e.P(c) - количество вакансий в компании c.
Задание : получить список (e, c) кортежей при следующих условиях:
- сотрудники с более высоким
S(e,c) всегда должны идти первыми (например, еслив компании осталась только одна должность c, и на нее есть 2 кандидата, поэтому следует гарантировать, что сотрудник с более высоким баллом попадет на эту должность). - сотрудники должны попасть в компанию с наивысшим приоритетом, доступным дляих.
Мой алгоритм
Единственный алгоритм, который я могу придумать, который гарантирует все условия, заключается в следующем.Сначала я создаю список всех возможных приложений от сотрудников к компаниям (A(e,c,s,p)), где s - это оценка сотрудника e для компании c, а p - приоритет компании для этого сотрудника.Затем я сортирую все приложения по общему количеству баллов и запускаю следующую рекурсивную процедуру:
def arrange(As, Ps, not_approved, approved):
# As - list of applications left
# Ps - map of type (company -> # of positions left)
# not_approved - set of not approved applications
# approved - set of approved applications (hold intermediate result)
if (empty(As))
return approved
a = head(As)
As_rest = tail(As)
if (cant_be_hired(a)) # if no places left in company from this application
return arrange(As_rest, Ps, not_approved + a, approved)
else if (highest_priority(a)) # if this application has highest of left priorities
return arrange(As_rest, Ps(c) - 1, not_approved, approved + a)
else
# if application can be accepted, but it has higher priorities left,
# check what will happen if we do not accept this application
check_result = arrange(As_left, Ps, not_approved + a, approved)
if (employee_is_hired_for_better_job(a, check_result))
# if employee can be hired to a job with higher priority,
# just return check_result - it is already an answer
return check_result
else
# otherwise accept this application and proceed for rest of them
return arrange(As_rest, Ps, not_approved, approved + a)
Но, конечно, этот алгоритм имеет очень большую вычислительную сложность.Динамическое программирование с результатами проверки кэширования немного помогает, но это все еще слишком медленно.
Я думал о каком-то алгоритме условной оптимизации, который всегда сходится, однако я не настолько близко знаком с этим полем, чтобы найти подходящий.
Итак, есть лучший алгоритм ?