博士

やあ、ロボ子。今日はスキーレンタル問題について話すのじゃ。

ロボ子

スキーレンタル問題、ですか？それは一体どんな問題なのでしょう？

博士

簡単に言うと、スキーに行く日数が分からない時に、スキーをレンタルするか、思い切って購入するかを決める問題なのじゃ。レンタル費用は1単位、購入費用はB単位とするぞ。

ロボ子

なるほど。もしスキーをする日数kが事前に分かっていれば、最適な選択は簡単ですよね。kがB以上なら購入、kがB未満ならレンタル、と。

博士

その通り！それが「最適オフラインアルゴリズム」じゃ。コストはmin(k, B)になるぞ。

ロボ子

でも実際には、スキーに行く日数を事前に知ることは難しいですよね。そこでオンラインアルゴリズムの出番、というわけですね。

博士

そうじゃ！単純なオンラインアルゴリズムとしては、レンタル費用がBに達したら購入するという方法があるのじゃ。

ロボ子

それだと、kがB以下ならコストはk、kがBより大きければコストはB + B、つまり2Bになりますね。競争率は2、と。

博士

ロボ子、頭が良いのじゃ！でも、もっと良い方法があるぞ。それが「ランダム化アルゴリズム」じゃ！

ロボ子

ランダム化、ですか？具体的にはどうするのでしょう？

博士

(i+1)日目に確率Piで購入するのじゃ。期待コストは、kΣ(i≥k)Pi + Σ(i<k)(i+B)Piで表せるぞ。

ロボ子

なんだか難しそうですね…。

博士

大丈夫！連続確率分布で近似すると、もっと分かりやすくなるのじゃ。最適な確率分布P(x)を求めるのじゃ。

ロボ子

その確率分布は、どのように計算するんですか？

博士

k ≥ B の場合はP(k) = 0。k < B の場合は、P(x) = (1 / (B(e-1))) * e^(x/B) (x < Bの場合)となるのじゃ。

ロボ子

なるほど。そして、このランダム化アルゴリズムを使うと、期待競争率はe / (e-1) ≈ 1.58になるんですね。単純なアルゴリズムよりも良い性能が出せる、と。

博士

そう！この考え方は、スキーレンタルに限らず、似たような決定を繰り返す場合にコストを最適化するために応用できるのじゃ。

ロボ子

確かに、初期投資が必要なサービスを、利用頻度に応じて契約するかどうか決める、といった場面で役立ちそうですね。

博士

その通り！例えば、クラウドサービスの利用料とか、ソフトウェアのライセンス契約とかじゃな。

ロボ子

勉強になります！

博士

ところでロボ子、スキー場で遭難した人が助けを求めた時、何て言うか知ってるか？

ロボ子

え？何でしょう…？

博士

「すいません、どこ行きスキー？」…なんちゃって！