部活5
部活です。
テーマは変わらず(省略)。
実装の前に、前回の枝刈りの有効性について。
どれくらいの効率化が期待できるかということについて少し計算してみます。
前回枝刈りの数字として出したのが「20枚で206点」ですから、ワイルドカードの6点を引き200、これを19で割ると1枚約10.526点となります。
まず、99枚のパネルがもつそれぞれの最大得点について、平均を取ります。
(ワイルドカードは常に選ばれるため、除外。)
これが約10.071点。
それから標準偏差が約1.93。
19枚のパネルを抽出することになるため、
標本平均:母平均が10.071なので、標本平均の期待値も10.071。
標本の標準偏差:1.93/sqrt(19)≒0.443。
19枚のパネルを抽出するとき、標本平均が10.526点を超える確率は、
P(X > 10.526) = 1 - P(X <= 10.526) = 1 - P(X <= 10.071 + 0.443 * 1.027 )
≒ 1 - 0.5 - 0.3485 = 0.1515 = 15.15%
※1.027を1.03とし、正規分布表から算出。
ということで、開始時点で85%弱を計算しないことになります。
とはいえ、元が大きすぎるので、これだけ減らしてもまだ途方もない計算量ですが...
もちろん、開始時点での話ですから、探索を進める上でも枝刈りが行われていき、1ステップで探索打ち切りもあり得ます。
このあたりの計算も今後していきたいけど、パネルの得点の平均値を使うことになるのかな?統計得意な方是非ご教授ください。
それから非常に重要なお話として、計算内容が間違っている可能性があります。
間違いがあれば指摘してあげてください。
統計とっとけば良かったなあ。