最適停止問題
1. ルール
結婚相手を決める問題を考える
全部で$ n人と交際することができる。
$ nという人数は既知である。
候補者には、あなたの視点から順位が付けられ、複数の応募者が同じ順位になることはない。
無作為な順序で交際相手が登場する。
交際の時点で、その人と結婚するかそれとも別れるかを決める。
一度、別れた相手は、その後になってから再び交際を申し込んだり結婚を申し込んだりはできない。
このような状況で、最良の応募者を選択することが問題の目的である。
2.$ n=3のケース(6パターンある)
123
132
213
231
312
321
このとき、例えば「最初に交際した相手と結婚する」というルールや、「3人目と結婚する」などの場合には、
最も良い人(1)と結婚できる確率は$ 1/3
(2)と結婚する確率も$ 1/3
(3)と結婚する確率も$ 1/3
ここで、できるだけ良い相手と結婚する確率を上げたい。
どうすれば良いか?
改善案
「まず1人目は選ばない。そして2人目を見てから、1人目よりもよければその人を選ぶ。悪ければ、3人目を選ぶ。」
このルールの下での結婚相手をBoldで書くと次のようになる。
123
132
213
231
312
321
この場合は、最も良い人(1)と結婚できる確率は$ 3/6= 1/2
(2)と結婚する確率も$ 1/3
(3)と結婚する確率も$ 1/6
ランダムに選ぶケースよりも改善している。
3.$ n=4のケース(24パターンある)
順列を求めると、$ 4 \times 3 \times 2 \times 1より24パターンある。
1234、1243、1324、1342、1423、1432
2134、2143、2314、2341、2413、2431
3124、3142、3214、3241、3412、3421
4123、4132、4213、4231、4312、4321
ちなみに最初の人と結婚するとか、ランダムに決めるような場合には、1位の人と結婚できる確率は$ 1/4であり、2位以降もすべて$ 1/4になる。
これをできるだけ1位と結婚する確率を上げたい。
どうすれば良いのか?
改善案1
「まず1人目は選ばない。そして2人目を見てから、1人目よりもよければその人を選ぶ。悪ければ、3人目に進む(このときまででは1がベスト)。そして3人目が1人目よりもよければその人を選ぶ。悪ければ4人目を選ぶ」
改善案2
「まず1人目と2人目は選ばない。3人目を見て、これまでのベストよりもよければこの人と結婚する。そうでなければ4人目と結婚する」
改善案1
1234、1243、1324、1342、1423、1432
2134、2143、2314、2341、2413、2431
3124、3142、3214、324 1、3412、3421
4123、4132、4213、4231、4312、4321
改善案2
1234、1243、1324、1342、1423、1432
2134、2143、2314、2341、2413、2431
3124、3142、3214、3241、3412、3421
4123、4132、4213、4231、4312、4321
table:<比較>
ランダム 確率 改善案1 確率 改善案2 確率
1位と結婚 6 0.25 11 0.45 10 0.41
2位 6 0.25 7 0.29 6 0.25
3位 6 0.25 4 0.21 4 0.17
4位 6 0.25 2 0.04 4 0.17
他にもっと性能が良い改善案はないのか?
4.$ n=5のケース(120パターンある)
順列を求めると、$ 5 \times 4 \times 3 \times 2 \times 1より120パターンある。
$ n=5のケース(120パターン)
{1, 2, 3, 4, 5}, {1, 2, 3, 5, 4}, {1, 2, 4, 3, 5}, {1, 2, 4, 5, 3}, {1, 2, 5, 3, 4}, {1, 2, 5, 4, 3}, {1, 3, 2, 4, 5}, {1, 3, 2, 5, 4}, {1, 3, 4, 2, 5}, {1, 3, 4, 5, 2}, {1, 3, 5, 2, 4}, {1, 3, 5, 4, 2}, {1, 4, 2, 3, 5}, {1, 4, 2, 5, 3}, {1, 4, 3, 2, 5}, {1, 4, 3, 5, 2}, {1, 4, 5, 2, 3}, {1, 4, 5, 3, 2}, {1, 5, 2, 3, 4}, {1, 5, 2, 4, 3}, {1, 5, 3, 2, 4}, {1, 5, 3, 4, 2}, {1, 5, 4, 2, 3}, {1, 5, 4, 3, 2},
{2, 1, 3, 4, 5}, {2, 1, 3, 5, 4}, {2, 1, 4, 3, 5}, {2, 1, 4, 5, 3}, {2, 1, 5, 3, 4}, {2, 1, 5, 4, 3}, {2, 3, 1, 4, 5}, {2, 3, 1, 5, 4}, {2, 3, 4, 1, 5}, {2, 3, 4, 5, 1}, {2, 3, 5, 1, 4}, {2, 3, 5, 4, 1}, {2, 4, 1, 3, 5}, {2, 4, 1, 5, 3}, {2, 4, 3, 1, 5}, {2, 4, 3, 5, 1}, {2, 4, 5, 1, 3}, {2, 4, 5, 3, 1}, {2, 5, 1, 3, 4}, {2, 5, 1, 4, 3}, {2, 5, 3, 1, 4}, {2, 5, 3, 4, 1}, {2, 5, 4, 1, 3}, {2, 5, 4, 3, 1},
{3, 1, 2, 4, 5}, {3, 1, 2, 5, 4}, {3, 1, 4, 2, 5}, {3, 1, 4, 5, 2}, {3, 1, 5, 2, 4}, {3, 1, 5, 4, 2}, {3, 2, 1, 4, 5}, {3, 2, 1, 5, 4}, {3, 2, 4, 1, 5}, {3, 2, 4, 5, 1}, {3, 2, 5, 1, 4}, {3, 2, 5, 4, 1}, {3, 4, 1, 2, 5}, {3, 4, 1, 5, 2}, {3, 4, 2, 1, 5}, {3, 4, 2, 5, 1}, {3, 4, 5, 1, 2}, {3, 4, 5, 2, 1}, {3, 5, 1, 2, 4}, {3, 5, 1, 4, 2}, {3, 5, 2, 1, 4}, {3, 5, 2, 4, 1}, {3, 5, 4, 1, 2}, {3, 5, 4, 2, 1},
{4, 1, 2, 3, 5}, {4, 1, 2, 5, 3}, {4, 1, 3, 2, 5}, {4, 1, 3, 5, 2}, {4, 1, 5, 2, 3}, {4, 1, 5, 3, 2}, {4, 2, 1, 3, 5}, {4, 2, 1, 5, 3}, {4, 2, 3, 1, 5}, {4, 2, 3, 5, 1}, {4, 2, 5, 1, 3}, {4, 2, 5, 3, 1}, {4, 3, 1, 2, 5}, {4, 3, 1, 5, 2}, {4, 3, 2, 1, 5}, {4, 3, 2, 5, 1}, {4, 3, 5, 1, 2}, {4, 3, 5, 2, 1}, {4, 5, 1, 2, 3}, {4, 5, 1, 3, 2}, {4, 5, 2, 1, 3}, {4, 5, 2, 3, 1}, {4, 5, 3, 1, 2}, {4, 5, 3, 2, 1},
{5, 1, 2, 3, 4}, {5, 1, 2, 4, 3}, {5, 1, 3, 2, 4}, {5, 1, 3, 4, 2}, {5, 1, 4, 2, 3}, {5, 1, 4, 3, 2}, {5, 2, 1, 3, 4}, {5, 2, 1, 4, 3}, {5, 2, 3, 1, 4}, {5, 2, 3, 4, 1}, {5, 2, 4, 1, 3}, {5, 2, 4, 3, 1}, {5, 3, 1, 2, 4}, {5, 3, 1, 4, 2}, {5, 3, 2, 1, 4}, {5, 3, 2, 4, 1}, {5, 3, 4, 1, 2}, {5, 3, 4, 2, 1}, {5, 4, 1, 2, 3}, {5, 4, 1, 3, 2}, {5, 4, 2, 1, 3}, {5, 4, 2, 3, 1}, {5, 4, 3, 1, 2}, {5, 4, 3, 2, 1}}
一般的なケースで、最適なルールを探すのは難しい。どうすれば良いのか?