phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない！

Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017参加記

概要

AtCoderで開催されたマラソンマッチに参加してみた。終了30分前なので、時系列で振り返ってみる。
システムテスト前のスコア・順位は156,999点で66位/298人。おそらくシステムテスト後は順位下がる・・・

最終順位は720,841点で62位でした。

今回は知り合いと競争してて、知り合い内では3人中3位という感じで効率の悪さと実力不足が明らかになったなぁという感じ。
とはいえ、マラソンマッチはちゃんと参加できたことがなかったのに対し、今回は比較的時間使えていたので、完敗。

問題

重み付き無向グラフGが与えられる。そのグラフの頂点を別のグラフG_embの頂点にマッピングする。
もしG_embにマッピング後、G_embでの頂点で隣接辺だった場合、Gでの辺の重みが適用される。
G_embはKing's Graphというグリッドの斜め方向頂点にも辺をつないだグラフが与えられる。
マッピング後のG_embでの重みの合計が最大になるような頂点のマッピングを求めよ。

最終的に提出したアプローチ

  • まずは山登り
  • その後、グラフが密な場合はちょくだいさんサーチっぽいの、疎な場合は焼きなましのハイブリッド
  • 頂点のマッピングは、G_embの中心から渦巻き状に広げていく形で決め打ちし、何番目にどの頂点を割り当てるかを考えた
  • ちょくだいさんサーチっぽいのは、重複排除がうまくできなかったので、各番目で上位数件で切り捨てる感じで多様性を確保する感じ
  • 焼きなましの方は、2-optっぽく、適当に2点選んで交換するので近傍探索。悪化した場合での採択率を山登り時点でのスコアとかで微妙に変えてる
  • 評価値は生のスコア

時系列での振り返り

初日
  • 問題理解自体は簡単そうな雰囲気だけど、どこらへんが難しいポイントかわからないので、数日は適当に実装しながら考えた
  • 初日は「ビームサーチ」か「n手先読み」を考えてた
  • 実装は適当に1点を決めてそこから8近傍に頂点を増やしていく感じで、先読みを1ターンだけするものを書いた
2日目
  • 状態数が多すぎて試せる分量が少なすぎるので、8近傍に頂点を広げていくビームサーチを実装しようと書いてみた
  • この時点では適当な調整をして148kぐらいだったけど、サイズが大きい場合に探索量が多くTLEしてしまったりスコアに大きな差がでてしまう問題があった
  • というか、ビームサーチの時間のコントロールが難しいというのが身をもってわかった
3日目
  • ビームサーチではなく、他の方法もありそうか考えてた
    • 決定的な手法とか、マッチングとか
    • 焼きなましとか試してみたけど、うまくいかず、ちょくだいさんサーチっぽい感じで何回も最初から最後までを繰り返す感じの探索でやってみたら悪くなさそうだったので、この方向で書きはじめ
  • ここで、ビジュアライザーを作ってないことが気になったので、C#で最終状態を出力する雑なものを作成
4日目～5日目

f:id:phyllo_algo:20171130234710p:plain

  • ビジュアライザー見ると、形がひどいときがあることに気づいた(上みたいなの)
  • ある程度中央付近に固まっていた方が都合がよさそうだろうと思って、距離が離れるほど評価値が下がるように書いた
  • けど、うまくいかなくて、ここで、「どこに何を」割りあてるかだと状態数が多くなりすぎるので、形を決め打ちして「何を」割りあてるかだけにすればよさそうと気づいた
  • 形はいろいろ考えられそうな気がするけど、とりあえず中心からグルグル渦巻き状に増やすようなものを考えることにした

f:id:phyllo_algo:20171130235755p:plain

  • 形の最適解の考察としては探索結果を見る感じだと平行四辺形っぽい形が多いので、辺の数的にもそういう形だろうと考えてた
  • けど、最後そこまで調整たどりつけなかった
6日目～7日目
  • メモリの制約からpriority_queueで保持する状態数に限りがありそうなので、適当に状態を削って探索
  • ただ、サイズが大きい場合は、十分な探索ができてなくて、イマイチスコアがでない
  • 他のアルゴリズムに浮気しつつ手を動かしてたけど、ダメだった
8日目～11日目
  • ここらは、ちょっと細かい考察と実験をしながら、提出の方はパラメータとかちょこちょこ変更して提出する感じで進めてた
  • 多様性確保のための状態の間引き方でうまい方法が思いつかず、ネットで情報調べたり勉強したり、いろいろ試してた
    • いろいろ取り入れようとすると探索量が減ってスコアが下がることを繰り返しててて、つらぽよ
    • あと、n手先読みとかペアを作ってからそれをくっつけてく方法とか別アプローチを試したりしてたけど、どれもイマイチで、つらぽよ
  • この時点での提出の最高点は154kぐらい
12日目
  • いろいろ出力して観察していたところ、どうも焼きなましっぽい動きをしてそうに見えたので、焼きなましでいけないか検討始めた
  • すると、調整が雑でもスコアが結構伸びた(！)
  • しかし、スコアが大きい場合、ちょくだいさんサーチっぽい方がスコアがよかったので、焼きなましとハイブリッドで実装
  • この時点での提出最高点は156kぐらい
13日目～最終日
  • 高速化を試していないことに気付いたので、時間計測とかintをshortにとかを置き換え
    • あと、cinをscanfにしたりしたらなぜかスコア下がったりして最終提出は変えなかった、、、
  • 500点ぐらい増えて最高スコアの156,999
    • ただ、何回か提出してみると、上振れスコアのようで、再提出すると数百点平気で下がってしまう運任せコード
  • 受理率が悪すぎて効率の悪い探索ばかりしていそうだったので、近傍の定義を効率化しようとして、ランダムに任意地点の2点をswapするのではなく、隣同士の2点を交換し続ける感じで書いてみたけどスコア悪化
  • あとは冷却スケジュールと評価関数が何もできていないので、そこを最後に詰めようと実験
  • 冷却スケジュールの方は、診断人さんまとめの焼きなましページを参考に、ちゃんと調整してローカルだと+600点ぐらいになったので、喜々として提出したら下がって絶望
  • 評価関数はいい形悪い形とかで加点減点を追加したらスコアが下がってしまって絶望
    • 頂点の辺の合計とか、何番目に大きい辺を使ってるかとか
  • 最終日で調整する時間がないのに、ローカルとオンラインのスコアの相関がなくなってて、絶望しながらオンラインの提出調整するしかなかった
  • 絶望
  • 絶望
  • 結局点数上がらないので、上の提出最高得点のコードを最終提出して、絶望のうちに終了
最終提出後～寝るまで
  • 振り返ってみてみると、焼きなましの受理率がものすごく悪いし、無駄なスワップとか繰り返しまくっているのでだいぶ改善の余地がある
  • 探索量とかは結構稼げてるから「焼きなまし＋評価関数工夫＋ヒューリスティックルール」が正解だったかなぁとか思う
  • あと、問題の切り分けとして、グラフの密度が「密」「疎」「スコアが大きい」あたりで分けて考えたけど、「疎」と「スコアが大きい」時が重要なのに全然詰められていなかった・・・
  • ビジュアライザーは、最終結果を見るものしか作れてなかったけど、「やりながら見る」や「やってる途中経過(探索しているもの)を確認できる」ようなものを用意しないと厳しいなと思った
  • 他にも試したけどここに書いていないものは、みんなの解答出てから反省時に振り返りたい