翻訳と辞書
Words near each other
・ ナンバー記号
・ ナンバー銀行
・ ナンバ地下センター
・ ナンバ壱番館
・ ナンバ歩き
・ ナンバ球場
・ ナンバ記号
・ ナンバ走り
・ ナンパ
・ ナンパ (アイダホ州)
ナンパ問題
・ ナンフ
・ ナンブ
・ ナンブアカマツ
・ ナンブアザミ
・ ナンブイヌナズナ
・ ナンブサケ
・ ナンブシシバナヘビ
・ ナンブタカネアザミ
・ ナンブトウウチソウ


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

ナンパ問題 : ウィキペディア日本語版
秘書問題[ひしょもんだい]
秘書問題()は、最適停止問題の一種で、応用確率論統計学決定理論の分野で特に研究されている。結婚問題 (marriage problem)、スルターンの持参金問題 (sultan's dowry problem)、最良選択問題 (best choice problem) などともいう。具体的には、次のような問題である。
# 秘書を1人雇いたいとする。
# n 人が応募してきている。n という人数は既知である。
# 応募者には順位が付けられ、複数の応募者が同じ順位になることはない(1位からn位まで重複無く順位付けできる)。
# 無作為な順序で1人ずつ面接を行う。次に誰を面接するかは常に同じ確率である。
# 毎回の面接後、その応募者を採用するか否かを即座に決定する。
# その応募者を採用するか否かは、それまで面接した応募者の相対的順位にのみ基づいて決定する。
# 不採用にした応募者を後から採用することはできない。
# このような状況で、最良の応募者を選択することが問題の目的である。
応募者がそれまで面接したどの応募者よりもよい場合は「候補者」となる。問題の目的は1人の最良の応募者を選ぶことであるから、採用を考慮するのは候補者だけでよい。秘書問題が注目された理由の1つとして、この問題の最適ポリシーが驚くべき特徴を持っている点が挙げられる。特に n が大きい場合、最適ポリシーでは最初の n/e 人の応募者をスキップし(eネイピア数)、それ以降に面接した応募者がそれまでよりよいと判断したら採用する。n が大きくなると最善の応募者を選択する確率は 1/e すなわち約 37% になる。応募者が100人でも100,000,000人であっても、最適ポリシーに従えば約 37% の確率で最善の応募者を選択できる。
== 最適ポリシーの導出 ==
この問題の最適ポリシーを停止規則 (stopping rule) と呼ぶ。それに従うと、面接者は最初の r-1 人の応募者をスキップし、その次の応募者が候補者(すなわち、それまで面接した中で最もよい応募者)なら採用する。任意の r について最善の応募者を選択する確率は次の通りである。
:
P(r)=\sum_^\left(\frac\right)\left(\frac\right)=\left(\frac\right)\sum_^\left(\frac\right)

n が無限大に近づくとして、r/n の極限を xj/nt1/ndt とすると、上記の総和は次の積分で近似できる。
:
P(r)=x \int_^\frac\,dt = -x \log(x)

P(r)x についての導関数をとり、それを0として x について解くと、最適な x1/e であることがわかる。したがって最適な切捨て(スキップ)は n が増大するにつれて n/e に近づいていき、最善の応募者を選択する確率は 1/e に近づいていく。
n が小さい場合、最適な r は標準的な動的計画法の手法で得られる。最適なしきい値 r と最善例を選択する確率 P を小さい n について以下の表で示す。

最善を選択する確率は非常に急速に 1/e\approx 0.368 に収束する。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「秘書問題」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.