質問: 最適停止問題に秘書選び問題というものがありますが、見送る数はどのように決めるべきなのでしょう。 Wikipediaの説明は、私には難しいです。 --- 追記 回答いただいた方法で最適な値を得ることが出来ました しかし、時々良い値でない場合もあったためもう一度調べ直したところ 同様の問題で期待値を最大化する方法があるそうです。 数式を見たのですが、結局のところ具体的な計算の方法が理解できず検算が出来ません 少ない数で構わないので具体的な計算方法を教えて下さい。 --- 計算方法がわからなかった式 > > i番目に面接したものの相対順位が!r_i以上であればこれを採用しそうでなければ見送る。 > > > !計算方法がわからなかった式 > > アルゴリズム辞典 共立出版 (1994/08)P.646 > > >
回答: 応募者の数が n 人で十分大きな数の場合 * 見送る人数を (n / e) にすると最善の秘書を雇える確率が最大となる。 * その確率は 1 / e である。 というのが、秘書選び問題(秘書問題)の解です。 ここで使われている e は、ネイピア数、オイラー数、自然対数の底などと呼ばれていて、その値は 2.718281828459045...(以下略)です。 e は、円周率と同様、無理数なので、小数点以下の数は無限に続きます。 何故このような結果になるのかは Wikipedia などで解説されていますが、確率の知識と、微積分の知識がないと理解するのが難しいと思います。でも、何人見送れば良いかは、簡単に電卓で計算できます。 例えば、応募者が 100 人だとすると、見送る数は、100 / 2.71824 = 36.7885... ですから、 37 人(割り切れないので、四捨五入してください)。 そして、残った人の中から見送った 37 人の誰よりも優れた人を選べば良い訳です。 「だいたい、応募者の3分の1を見送って、見送った中で最良だった人を超える人が表れたら、その人を選ぶ」ぐらいで実用になります。