問題F Power Calculus を枝刈り

おお，この問題って全探索＋枝刈りで解けたんだ。びっくり。

http://d.hatena.ne.jp/tanakh/20061107

私はDFSで解いてみた。

かなりアグレッシブに枝刈を入れると、

ようやく現実的な時間で解けるようになった。

・現在までの最短を越えたとき

・後一手で解けるとき

・後一手で解かなきゃいけないのに解けないとき

・残りを全て倍倍にしていっても目標に到達できないとき

このあたりで、1から1000まで全て計算して90秒ぐらいになった。

さらに、最長が13であると仮定して、

11手の時点で計算を打ち切ると一分を切るぐらいになった。

なるほどー。確かにadhocに枝刈りルールを追加していく解き方だと

うまい方法がありそうで実は無い問題。

解いたチームの片方はDFSで、もう片方はBFSで解いたらしい。

どうやったら計算量の推定が出来るのか知りたいところだが、

分からないけど突撃したとのこと。

うまい解法が無いという自身があればそういけるのか？

最初から探索で解けると聞けばそりゃ解けるけど、

そうじゃなけりゃ解法を探してしまうような気がする。

というのもよく分かるなぁ。他のチームが手を出さなかった理由も。僕もadhocな枝刈りで解き始める勇気はないです。僕は探索問題であれば動的計画法(DP)の解法で計算量が問題になることはないだろうという直感で能天気に解き始めたわけですが。

僕はBFS＋ダイクストラ法(SPF)で枝刈りしました。DPなので途中のノードまでの最短経路も全て求まって，計算時間がステップ数に依存するだけで入力ファイル中の問題数には依存しないのが安心できる点かなぁ。メモリを使って計算時間が短くなるのでメモリ量の心配が増えるわけですが，実際にメモリ量が問題になるのはそんなにないような。