Катя (inostranka) wrote,
Катя
inostranka

Задачка

Когда-то в школе мы решали "задачу секретарш": вам надо нанять секретаршу, причем a priory вы не умеете их оценить, но проинтервьюировав можете сравнить с предыдущими кандидатками. Рынок рабочей силы большой, платите вы хорошо, так что к вам подает большое, но все же конечное количество секретарш, скажем 100. Сложность в том, что решение о приеме надо принимать сразу же после окончания интервью - нельзя сказать "может быть" и нельзя вызвать уже отвергнутую кандидатуру. А теперь внимание, вопрос: какова оптимальная стратегия?

Помнится, нам сказали ответ, но решения я не помню. Может кто знает?

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

Update: для моей задачи я хочу maximize the quality of the candidate picked on average (e.g., if you try it M times, maximize the sum of the ranks of the picked candidates). При этом выбрать хоть кого-то надо в каждом случае.

Update 2 (trying to formalize the problem for the mathematically inclined): you are presented with numbers 1 through N, inclusive, without repetition in random order, one at a time. After each number is presented you can either choose it and stop the game or skip it and continue to the next one; you must pick a number at the end (e.g., if you do not pick N-1 you automatically choose the Nth number). You cannot go back once you skip the number. Your task is to maximize the expected value of the chosen number when the game is over.


Мы подумали и решили...
Пожалуй подожду постить ответ.
Tags: random thoughts
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 47 comments