*[[Problem 328:http://projecteuler.net/problem=328]] 「最低コスト探索」 [#e5d6ad48]

整数の集合 {1, 2, ..., n} から選ばれた秘密の数を, 質問により当てようとしている. 数(質問)を尋ねる際は, %%%尋ねた数に等しいコスト%%%がかかり, 次の三つのいずれかの答えを得る:
- 「秘密の数はあなたの推測した数より小さいです」
- 「そう, まさにその数です!」
- 「秘密の数はあなたの推測した数より大きいです」

n の値が与えられたとき, 最適な戦略をとると, %%%起こり得る最悪の場合%%%に対し, 総コスト(尋ねた質問の全ての和)が最小になる. 例えば, 

n=3 の場合, とり得る最良の方法はもちろん "''2''" と尋ねることである. 答えによりたちどころに秘密の数が分かるだろう(総コスト=2).

n=8 の場合, 「二分探索」型の戦略を用いようとするかもしれない:最初の質問は "''4''" となり, もし秘密の数が 4 より大きければ, 追加で1または2回の質問をする必要があるだろう. ~
2番目の質問を "''6''" としよう. 秘密の数がなおも 6 より大きければ, 7 と 8 を見分けるため3番目の質問を必要とするだろう. ~
このようにして3番目の質問は "''7''" となり, この最悪の場合のシナリオに対する総コストは 4+6+7=''&color(red){17};'' となる.

最初の質問として "''5''" を尋ねれば, n=8 に対する最悪の場合のコストを大幅に改善することができる. ~
もし秘密の数は 5 より大きいと告げられた場合は, 2番目の質問を "''7''" とすれば, 秘密の数が何であるか確実に分かる(総コストは 5+7=''&color(blue){12};''). ~
もし秘密の数は 5 より小さいと告げられた場合は, 2番目の質問を "''3''" とすれば, もし秘密の数が 3 より小さければ3番目の質問は "''1''" となり, 総コストは 5+3+1=''&color(blue){9};'' となる. ~
''&color(blue){12};''>''&color(blue){9};'' なので, この戦略に対する最悪の場合のコストは ''&color(red){12};'' となる. これは先ほどの「二分探索」の戦略の結果より優れている;また他のいかなる戦略より優れているか, 同コストである. ~
以上の通り, n=8 に対する最適な戦略を述べた.

上述のように, n に対し最適な戦略をとることで得られる最悪の場合のコストを C(n) とする. ~
C(1) = 0, C(2) = 1, C(3) = 2, C(8) = 12 である. ~
同様に, C(100) = 400, &ref(http://projecteuler.net/project/images/p_328_sum1.gif,nolink);C(n) = 17575 である.

&ref(http://projecteuler.net/project/images/p_328_sum2.gif,nolink);C(n) を求めよ.


トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS