*[[Problem 328:http://projecteuler.net/problem=328]] 「最低コスト探索」 [#e5d6ad48]
整数の集合 {1, 2, ..., n} から選ばれた秘密の数を, 質問により当てようとしている. 数（質問）を尋ねる際は, %%%尋ねた数に等しいコスト%%%がかかり, 次の三つのいずれかの答えを得る：
- 「秘密の数はあなたの推測した数より小さいです」
- 「そう, まさにその数です！」
- 「秘密の数はあなたの推測した数より大きいです」
n の値が与えられたとき, 最適な戦略をとると, %%%起こり得る最悪の場合%%%に対し, 総コスト（尋ねた質問の全ての和）が最小になる. 例えば,
n=3 の場合, とり得る最良の方法はもちろん "''2''" と尋ねることである. 答えによりたちどころに秘密の数が分かるだろう（総コスト=2）.
n=8 の場合, 「二分探索」型の戦略を用いようとするかもしれない：最初の質問は "''4''" となり, もし秘密の数が 4 より大きければ, 追加で１または２回の質問をする必要があるだろう. ~
２番目の質問を "''6''" としよう. 秘密の数がなおも 6 より大きければ, 7 と 8 を見分けるため３番目の質問を必要とするだろう. ~
このようにして３番目の質問は "''7''" となり, この最悪の場合のシナリオに対する総コストは 4+6+7=''&color(red){17};'' となる.
最初の質問として "''5''" を尋ねれば, n=8 に対する最悪の場合のコストを大幅に改善することができる. ~
もし秘密の数は 5 より大きいと告げられた場合は, ２番目の質問を "''7''" とすれば, 秘密の数が何であるか確実に分かる（総コストは 5+7=''&color(blue){12};''）. ~
もし秘密の数は 5 より小さいと告げられた場合は, ２番目の質問を "''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) を求めよ.
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
