北大日立マラソン2ndに参加しました


このエントリーをはてなブックマークに追加

1stに引き続きHokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017に参加しました。1stより十分な時間をとって臨んだおかげで、最終提出時18位、最終テスト後19位。目標としていた上位25%に滑り込めました。

考え方

序盤は迷走しましたが、中盤から以下の3つのフェーズに分けると考えやすいことに気付きました。

  • フェーズ1. GemvをV個のグループに分割
  • フェーズ2. GemvのV個のグループと、グラフGのV個の頂点との最適なマッピングを探索
  • フェーズ3. Gemvのグループ分割を微妙に変えてスコア向上

自分の感覚では、フェーズ1 > フェーズ2 > フェーズ3の順にスコアに影響がある感じがしました。

フェーズ1. GemvをV個のグループに分割

なるべく各グループが他のグループと多く接するように分割するほどスコアが向上する傾向にあることに気付いたので、このフェーズにもっとも力を入れました。

例えば各グループをサイズ1として以下のように並べると、各グループは最大でも他の8グループとしか隣接できません。

ABCD
EFGH
IJKL
MNOP

しかし各グループをサイズ2として以下のように並べると、各グループは最大で他の11グループと隣接できるようになります。

ABCD
BADC
IJKL
JKLK

今回は、「異なるグループ同士の隣接数の総和」をポテンシャルという名前で呼び、このポテンシャルが大きくなる分割方法を検討しました。

各グループを斜めで配置して互いに交差させると隣接数が多くなりそうだということには気づきましたが、これをうまくルール化するのが困難でした。大雑把に書くと、以下のように何通りかグループ分割法を試し、実際にポテンシャルを計算(これはすぐできる)し、もっともよいグループ分割法を採用するという方法を取りました。

for i = 1, 3, ... 
  左上から右下まで、長さiの直線をとれるだけとる
  右上から左下まで、長さiの直線をとれるだけとる
  もしまだ十分な数のグループが分割できていなければ、できるだけ直線になるように適当にグループをとっていく

そして最後に、各頂点をあるグループから他のグループに変えることでポテンシャルが上がるかどうかを山登り的にチェックして、若干ポテンシャルの値を追い込みました。頂点が所属するグループを変えても連結性が保たれるかどうかは、その頂点の近傍8ブロックを見てチェックしました。例えば

* A *
* A *
* * A

という3x3グラフの中央に着目したとき、このAを他のグループに変えると、少なくともこの3x3領域内ではAの連結性が破られてしまうので、Aの所属は変えません。次に

* A *
* AA
* * A

という3x3グラフの中央に着目したとき、このAを他のグループに変えると、Aの連結性は保たれるので、Aの所属は変更可能だと判断できます。

フェーズ1の心残りとしては以下があります。

  • どのグループにも属さないままとなった頂点をうまく他のグループに属させて、全体のポテンシャルを底上げする方法を追求できなかった。
  • 極端に隣接数の小さいグループが存在してしまいがちだった。場合によってはパーフェクトボーナスを取る妨げになった可能性がある。
  • パーフェクトを狙うのであれば、入力グラフの各頂点の次数のヒストグラムを考慮して、グループ分割方法を考える必要があったかもしれない。

フェーズ2. GemvのV個のグループと、グラフGのV個の頂点との最適なマッピングを探索

フェーズ2は焼きなましのようなもので探索しました。

まず、フェーズ1のグループ分割は完全に固定して、各グループをノード、グループ間の隣接関係をエッジとする新たなグラフGemv'を作ります。 そして、グラフGの頂点と、グラフGemv'との頂点とのマッチングをあれこれ試し、スコアの最適化を狙いました。

操作は頂点のスワップです。5回に4回はランダムにスワップ(ただし、確実に何らかのスコアが発生する頂点を選ぶ)、5回に1回はもっともスコアが上がりそうな頂点を選んでスワップ、という戦略を取りました。

このフェーズは25秒程度実行しました。それなりに高速化したつもりですが1億回程度しか試行できず、上位陣に遠く及びません。上位陣との差分が何なのか研究が必要です。

また、多分初めて焼きなましをしましたが、最後までコツがよく分かりませんでした。以下のようルールに落ち着いたのですが、スコアが大きく下がるのをまったく許容できていないところに改善の余地があります。

  • スコアが向上すれば100%遷移
  • スコアが-1のみ低下するときは、確率th1 (序盤100% -> 中盤0.01% -> 最終盤0%)で遷移
  • スコアが-2か-3低下するときは、確率th2(序盤から中盤まで0.001%, 最終盤0%) で遷移

フェーズ3. Gemvのグループ分割を微妙に変えてスコア向上

以下のアルゴリズムでグループ分割方法を山登りで変えました。

  1. 頂点を一つランダムに選択
  2. もしその頂点のグループを変えて連結性が保たれる保証がなければ1.に戻る
  3. 頂点の周囲8箇所のうちどれかをランダムに選び、そのグループに属させる。
  4. もしスコアが上がれば採用
    1. に戻る

上記3.で周囲8箇所全通りやっていたつもりが、1箇所しかできていませんでした…。ここでもっと頑張ればスコアが上がることは盤面から分かっていましたが、時間の関係で切り捨てました。

また、除去してもスコアに影響がない点を除去するのも、面倒で省略しました。

感想

イデアを一つずつ実装して着実にスコアを改善できた達成感と、上位との非常に大きなスコア差からくる敗北感とが8:2くらいな気持ちです。特にフェーズ1のグループ分割に関してはもう少しアイデアを出す余地があったのではないかと思います。例えば hakomo さんの

などは実装量も軽そうで、自分でも思いつきたかったアイデアでした。

コード

汚くて恥ずかしいんですが貼っておきます。最終提出版を少しだけ手直しして力尽きたものです。

https://gist.github.com/minus9d/177b1031aee831a4a0d9e7b77a94aaa5