Минимизация стоимости использования проблемы найма

Question

Я прошел одну из книг алгоритма и нашел проблему под названием «Проблема найма». Вот ситуация:

Я должен провести собеседование для найма кандидатов в мою компанию. Я лично не в состоянии провести интервью, поскольку я не смог этого сделать. Поэтому я нанял агентство по трудоустройству, чтобы помочь с наймом кандидата. Каждый день агентство будет присылать мне кандидата из числа n кандидатов. Алгоритм для этого будет:

**Algo Hiring Candidate(n)**  
best=0 // The candidate with the least quality  
for i=1 to n  
If the candidate is better than the best valued candidate we should hire him  
Best=candidate[i]  
return i;  

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

Общая стоимость будет O (стоимость интервью и найма)

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

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

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

Answer 1

Я думаю, что это пример Секретаря Задачи .

Answer 2

Ваша проблема действительно (вариант) проблемы с наймом, которая сама по себе является многоцелевой версией секретарской проблемы .

В последнем случае, есть группа из n кандидатов, поступающих в произвольном порядке качества, и она должна принять мгновенное решение (принять кандидата или отклонить без второго шанса).По мере того как каждый видит все больше и больше кандидатов, он получает лучшее представление об общем качестве кандидатов, но увеличивается вероятность того, что лучшие из них принадлежат прошлому (на самом деле эту проблему следует называть «игрой на свиданиях» или «пикантным»).Сингл ", если вы спросите меня ...).Цель состоит в том, чтобы найти стратегию, которая максимизирует вероятность получения лучшей.Эта цель может быть достигнута путем просмотра n / e из n кандидатов, а затем выбора следующего кандидата, качество которого превышает качество n / e «обучающего набора» (первых кандидатов).

Слегка контрастирующий,проблема найма направлена ​​на выбор многих хороших кандидатов.Как хорошо описано во введении (стр. 3) докторской диссертации доктора Ахмеда Мохамеда Хельми Мохамеда Эльсадека , в основе проблемы найма лежат две противоречивые цели:

1. Оптимизация качества наймаКандидаты
2. Максимальное количество нанятых кандидатов

Обратите внимание, что если рассматривать только 1., то наилучшая стратегия, скорее всего, такая же, как и для задачи секретаря.Если только 2. считается, то просто принять всех, не беспокоясь об их навыках.Когда оба учитываются, нужно объединить эти две цели в своего рода оптимальные компромиссы, и существует более одной оптимальной стратегии.В вышеупомянутом тезисе есть несколько хорошо объясненных стратегий (см. «Превосходящее правило» правило Преатера, «правила p-процентиля» Кригера, Поллака и Самюэля-Кана ...).

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