アルゴリズムイントロダクション第5.4章発表資料PPT

2010年CS勉強会第3回 2010/06/12
アルゴリズムイントロダクション第５章(5.4.4)
オンライン雇用問題
tniky1
http://www.tniky1.com/
Copyright© 2010 tniky1 All rights reserved.
Page 1
2010年CS勉強会アルゴリズムイントロダクション
前回の雇用問題
雇用代理店
面談
・・・・・
1
2
3
n
候補 i
一番じゃないといけ
ないんですか！？
現在の秘書best
全員と面談をするのは
無駄でしょ！
毎回雇用するのは無駄
でしょ！
Copyright© 2010 tniky1 All rights reserved.
Page 2
2010年CS勉強会アルゴリズムイントロダクション
5.4.4 オンライン雇用問題の目的
一言で言っちゃうとこ
れだけ。特に新しい概
念とか技法はない(^^;)
もう少し実践的な雇用問題にしよう
対応ペー
ジの記載
Copyright© 2010 tniky1 All rights reserved.
Page 3
2010年CS勉強会アルゴリズムイントロダクション
オンライン雇用問題
• 方針
– 採用は一度きり
– 最適に近い候補(なるべく優秀な人)を採用できればよい
– 面談直後に採用の合否を判断
• 今回の戦略
– 最初の一部 k人と面談し、その中で最高点を確認する。
(採用はしない)
– k+1人目以降で今までの最高点を最初に更新した人を採
用
p109
採用しない最初の面談回数は何回がよい？
最良の人を雇用する確率は？
Copyright© 2010 tniky1 All rights reserved.
Page 4
2010年CS勉強会アルゴリズムイントロダクション
オンライン雇用問題アルゴリズム
雇用代理店
・・・
1
2
・・・・・
k
k+1 k+2
面談
面談
候補 I
(i≤k)
候補 I
(i>k)
bestscore
・最高点を確認
面談直後に採用の
合否を判断という
方針のため
n
bestscore
・最高点以上を採用
・採用すれば終了
・1〜kに最高点者が
いた場合nを採用
Copyright© 2010 tniky1 All rights reserved.
・全員と面談しない
ですむ。
・雇用は一回ですむ
最良の雇用者を得る確率は？
kをどのような値にすればよい？
Page 5
2010年CS勉強会アルゴリズムイントロダクション
最良の人を雇用する確率
参考用の人数を何
人にすればよいか
• 最良の人を雇用するという事象をS
• Sの確率を求め(kに依存)、kをどのような値にすべきか(最良
のk)、またその時の確率をみる
• i番目の応募者が最高得点の人であり、その人の雇用に成
功する事象Si
最初のk人の中に最高得点
– i = 1,2,•••,k
者がいる場合、成功しない。
この二つの条件が
成り立てばよい
– i = k+1,•••,n
=
(Bi:最高の応募者がi番目に出現)∩(Oi: k+1からi-1番目の応募者が不採用)
n全員が最高得点
者になる確率を等
分に持っている
=
p109-110
Copyright© 2010 tniky1 All rights reserved.
Page 6
2010年CS勉強会アルゴリズムイントロダクション
最良の人を雇用する確率
不採用
・・・
1
2
・・・・・
・・・・・
k
k+1 k+2
n
i
i-1番目までの応募者で
最高得点者がこの中
1番目
– i = k+1,•••,n
=
＋
＋・・・・・＋
2番目
k番目
(Bi:最高の応募者がi番目に出現)∩(Oi: k+1からi-1番目の応募者が不採用)
n全員が最高得点
者になる確率を等
分に持っている
=
p110
Copyright© 2010 tniky1 All rights reserved.
Page 7
2010年CS勉強会アルゴリズムイントロダクション
最良の人を雇用する確率
i = 1,2,•••,k
i = k+1,•••,n
実際に入れてみる
とわかりやすいです
1/k + 1/(k+1) + 1/(k+2) + ••• + 1/(n-1)
積分での挟み撃ちを利用。
今回は、成功確率（最良の人を雇用する確率）を最大にしたい。
Pr{S}に関するkの値をどのようにするのが最適化かをみる。
計算も楽だし、確率の低い方で考えておけば問題ない。
p110-111
Copyright© 2010 tniky1 All rights reserved.
Page 8
2010年CS勉強会アルゴリズムイントロダクション
の計算
p325
Copyright© 2010 tniky1 All rights reserved.
Page 9
2010年CS勉強会アルゴリズムイントロダクション
最良の人を雇用する確率
i = 1,2,•••,k
i = k+1,•••,n
実際に入れてみる
とわかりやすいです
1/k + 1/(k+1) + 1/(k+2) + ••• + 1/(n-1)
積分での挟み撃ちを利用。
今回は、成功確率（最良の人を雇用する確率）を最大にしたい。
Pr{S}に関するkの値をどのようにするのが最適化かをみる。
計算も楽だし、確率の低い方で考えておけば問題ない。
p111
Copyright© 2010 tniky1 All rights reserved.
Page 10
2010年CS勉強会アルゴリズムイントロダクション
最良の人を雇用する確率
≥
微分
この式の値を最大にするkを知りたい。
グラフがかければ一発。
グラフかけなくても、微分をして、プラス
からマイナスへ入れ替わる所があれば
そこが最大値。（上に凸のグラフ）
0になり、微分した式がプラスからマイナスへ入れ替わる時のk
これが最良のk!!
代入
≥
p111
Pr{Smax} = 1/e
Copyright© 2010 tniky1 All rights reserved.
[結論]
k=n/e を用いるのが最良。
その時、最高の応募者を雇用できる
確率は少なくとも 1/e
Page 11
2010年CS勉強会アルゴリズムイントロダクション
余談(応用) 昨日のTVでの話
• 初めての彼女と結婚するより最良の人と結婚できる
方法は？
– 結婚までに付き合える人数を10人とする
– 付き合っている時に返事をする(よりを戻すことは不可)
初めての彼女と結婚した場合、最良の人を得る確率は1/10 = 0.1
オンライン雇用問題と全く同じ！(n=10)
最初は結婚しないで参考値だけを得て、
それ以上の人が現れたら即結婚!(^^;)
≥
kは整数
k=3
Pr{S} ≒ 0.3611
k=4
Pr{S} ≒ 0.3665
k = n/e = 10/(2.7182・・・) ≒ 3.679
Copyright© 2010 tniky1 All rights reserved.
Page 12
2010年CS勉強会アルゴリズムイントロダクション
参考
雇用問題計算用
n
k
10
10
10
10
10
10
10
10
10
10
k/n
1
2
3
4
5
6
7
8
9
10
lgn
lgk
logn-logk
Pr{S}
0.1 2.302585093
0 2.302585093 0.230258509
0.2 2.302585093 0.693147181 1.609437912 0.321887582
0.3 2.302585093 1.098612289 1.203972804 0.361191841
0.4 2.302585093 1.386294361 0.916290732 0.366516293
0.5 2.302585093 1.609437912 0.693147181 0.34657359
0.6 2.302585093 1.791759469 0.510825624 0.306495374
0.7 2.302585093 1.945910149 0.356674944 0.249672461
0.8 2.302585093 2.079441542 0.223143551 0.178514841
0.9 2.302585093 2.197224577 0.105360516 0.094824464
1 2.302585093 2.302585093
0
0
Copyright© 2010 tniky1 All rights reserved.
Page 13

Download Report