AHC049振り返り
はじめに
トヨタ自動車プログラミングコンテスト(AtCoder Heuristic Contest 049)に参加した。順位は最終結果として300番台だった。
問題
問題は、荷物を出口まで運ぶ問題。
荷物は上に載せることができるが、下の荷物は上の荷物の重さ
ヒューリスティックな解法
遠くにある耐久力の高いものから運んでいく
耐久力が高いものを下にして出口まで運んでいく途中で、上に載せれる荷物を拾っていくことを考えてみた。寄り道をするメリットはなさそうなので、最短経路で目的の荷物まで移動し、最短経路で出口に持っていくとした。そうすると、座標
最短経路しか考えないので、帰路は上に行くか左に行くかである。どちらに行くかは、「重い荷物を上に載せれるかどうか」で決めた。こんな単純でいいのかな？とは思ったが、それなりな答えがでてくるので、この方法で進んだ。
途中まで運ぶ
問題にあるように、「手に持っているダンボール箱の山の一番上を現在位置に置く」という手順も可能である。なんとなく、これを使った方が良さそうな気はする。つまり、出口までは運べないけど、途中まで運んでおくと良いのではないか。
ただ、途中に荷物がないマスに来たら、これまでの経路でここまで持って来れる荷物がないかチェックして、あれば持ってくることとした。荷物の順番は入れ替えられないので、探索範囲としてはそんなに広くない。
ヒューリスティックな解法の解の例
BeamSearchを使う
重さと移動距離の積を最大化する
上記は右に行くか左に行くか1手先だけを見ていたので、候補を広くするようにBeamSearchをやってみた。評価値は、盤上のダメージをどれだけ減らせるか？とイメージして、重さと移動距離の積を合計した。途中まで運んだ箱もこれにより評価できる。
Beam Searchを使った解の例
結果としてはスコアは下がった。最初の解法は、上向きの移動を優先するので、端っこも含めてうまく回収できているが、Beam Searchだと端っこが残ってしまっているから...かも知れない。
ここで時間切れで終了。結局Beam Search版は提出しなかった。
おわりに
それなりにはできたとは思うのだが、まだ試行が足りないのか、カンが悪いのか、いまいち最適化しきれていないという感じであった。
Beam Searchの評価式がよくないのか、一番下の荷物を運ぶ順番の方でBeam Searchか焼きなましをすべきだったのか、などいくつか思うところはあるので、そのうち再挑戦してみたい。
延長戦
追加として以下のように修正した。
たくさんの箱を運ぶことを優先する
箱の重さと運んだ距離の積を評価値としていたが、できるだけたくさんの箱を運んだ方がその後の移動距離は少なくなりそうなので、運んだ箱の数を第一評価値として、同じであれば重い箱を長距離運んだ方を高く評価するようにした。
最初の箱を持った後、上に載せられる箱を探す
箱の上に何も載っていない時はダメージを受けないので、最初の箱から距離
耐久度の高い箱から優先して運ぶ
上記の処理を行ったことで、左下からスタートする必要は無くなったので、耐久度を重視して最初持つ荷物を決定するようにした。
少し距離の影響を小さくした方がいいかな？と思ったが、ほぼ耐久度で決めた方がスコアは良かった。
結果
TLEをおこさないようにビーム幅などを調整して、100番台相当のスコアをだすことができた。最後に小さい箱が残ってしまっている。遠くの小さい箱は、その後に荷物を載せることができないので、どうしても後回しになってしまうのが課題かも知れない。
上位の人の解法を見ると荷物を運ぶ順番やグループで焼きなましをしているようだった。ここらへんのセンスがまだ掴めていないかも...
Discussion