megumishの日記

今日の2時にTCOMM16Round1が終わったということで、自分の戦略をここにまとめておきます。

最終的な戦略

まず貪欲で初期解を作り、それをもとに遺伝的アルゴリズムでランダムで線を入れ替えて（なぜ削除ではなく入れ替えるなのかというとそれは、NP-1本必ず線を引かなければいけないと勘違いしていたからです。）得点を上げていく手法を使いました。

貪欲にも遺伝的アルゴリズムにもそれを評価するためのスコアが必要ですが、それには(分割できた植物のある領域の数）＋（残った根の長さ）/（全体の根の長さ）という評価式を用いました。

（分割できた植物のある領域の数）は一本ずつ線を引くと考えて、それから線の上にあるか下にあるかで二分割するのを繰り返して分けました。

根の長さについては深さ優先探索を使い求めました。まずvector<int>rootsから木を構成します。（全体の根の長さ）を求めるにはこの次に、深さ優先探索を使って葉のスコアは0として、親は子のスコアと親と子の間の距離をそのスコアとするというのをすべての植物に対して行います。そしてすべての植物のスコアを足すと全体の長さがわかります。

（残った根の長さ）は深さ優先探索を使って各線について子と親の間に線が通っていたときに、元の子の座標を交点の座標に書きかえて子の子はすべて消すというのを繰り返します。そうすると、根の状態は切り取られた後の状態になるのでさっき全体の根の長さを求めた方法と同じことをやると残った根の長さがわかります。

この評価方法をそのまま使うと、深さ優先探索の再帰のコストが大きくなってしまうため、NPが多いときには探索する深さを制限して使うようにしていました。NPが多いときに使う理由は、NPが多いときには深さを制限してもある程度本当の得点に相関性のあるスコアが得られるからです。またNPが多いときはとくに再帰のコストが多くかかるからです。

その他に考えた戦略

評価式はそのままで山登り法を使った方法

正直これでもある程度うまくいったのですが、途中で遺伝的アルゴリズムを使ってみたくなり使うのをやめました。

評価式はそのままで焼きなまし法と遺伝的アルゴリズムを使った方法

遺伝的アルゴリズムの本に焼きなましと遺伝的アルゴリズムを合わせたハイブリッド手法には様々な利点があると書いてあったため使いました。しかし本をまともに読まず我流で書いたためか確かな効果は得られませんでした。この手法はコンテスト終了直前に書いていたのでパラメーターの調整が間に合わず提出できませんでした。

評価式に円の半径を使って貪欲法を使った方法

植物の根を植物の中心点から四象限に分けて、根の長さから四つの円を書いてそれがどれぐらい削られたかで判定する方法を使いました。これは得点との相関性がないことから最終的には使いませんでした。

反省

序盤にも書いた通りルールを勘違いしていたとというのが本当に悲しいです。次からは問題文をちゃんと読んでおきたいですね。

Exampleの結果だけ見ていて他のテストケースでのTLEを気にしていなかったのも終了後に気づいた反省点です。あと次は時間内にビジュアライザ作りたいと思いました。