【ざっくり紹介】秘書問題について
Calendar for データ構造とアルゴリズム | Advent Calendar 2021 - Qiitaの14日目の記事です。
秘書問題について
目的
1番いい秘書を雇いたい
条件
* 秘書を1人雇いたい。
* N 人と面接する。
* 無作為な順序で1人ずつ面接を行う。次に誰を面接するかは常に同じ確率である。
* 面接した瞬間に採用するかどうか決めないといけない。(キープはできない)
* 不採用にした応募者を後から採用することはできない。
小ネタ
別名、結婚問題 (marriage problem)と呼ばれます。
最近周りが結婚ラッシュで、どうしたら理想的な結婚相手が見つかるかなと思い調べたのがキッカケです。
最適戦略
Nが十分大きい時、k番目まで見送り、k+1番目から「今までで1番評価が高い人」が現れたら採用する。
この時、最善の応募者を選択する確率は 1/eとなる。
証明はこちら
最近の研究
k秘書問題
上記で、紹介したのは採用する人数が1人の場合である。それを複数にしたver。
k秘書問題は前からあったが、アルゴリズムの厳密性を争点としてる。
www.sciencedirect.com
ロバストに解こう
無作為な順序で1人ずつ面接を行う。次に誰を面接するかは常に同じ確率である。
という条件を意地悪な順番だったらどうするの？というアプローチ
お詫び
本当は研究の論文の方を紹介したかったのですが、力尽きました。すみません...
