部活4

部活です。

テーマは前回と同様最高点についてです。

予告どおり枝刈りについて。

枝刈りは、その名のとおり不要な(通っても無駄な)枝を切る(調査しない)ことで、計算量を減らすものです。

重要なのは不要だという判断はどのように行うかです。

この判断が間違っていると必要な枝まで切ってしまい、最高点が得られない可能性があります。また、切り方が甘ければ当然計算量が減らないことになります。

現在考えているのは、パネルの最高点を用いた以下の枝刈り方法です。

探索中、パネルを選ぶごとに、現在の得点と残りのパネルの最高点の和を取り、それが現在保持している最高点に満たない場合は探索を打ち切る

常に現在の最高点と探索状況を比較し、可能性がなくなり次第、探索しないようにします。

初期最高点が高ければ高いほど根に近い枝から探索を打ち切ることができるため、特に初期の探索回数を大幅に減らすことができます。

とりあえず初期最高点を「206点」とし、高速化を考えます。これについては人力探索によって作成可能であるという事実に基づいています。(全消しボーナスなし)

人力探索の内容について詳しく知りたい方はお気軽にどうぞ。

今日はここまで。

次回は実装の話になるかもしれないし、ならないかもしれない