Problem 328 「最低コスト探索」

整数の集合 {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=17 となる.

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

上述のように, n に対し最適な戦略をとることで得られる最悪の場合のコストを C(n) とする.
C(1) = 0, C(2) = 1, C(3) = 2, C(8) = 12 である.
同様に, C(100) = 400, p_328_sum1.gifC(n) = 17575 である.

p_328_sum2.gifC(n) を求めよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2011-03-24 (木) 00:13:37 (2403d)