TCO10 Marathon Round 3

TopCoder

Subgraph Isomorphismする問題
暫定8位だけど、おそらくシステムテストで順位が超入れ替わると思われるので安心出来ない
通過できてるといいなぁ

戦略上重要なこと

スコアが絶対評価なので、点が稼げるところで一気に稼がないといけない
難しいケースは頑張っても20〜40点とかそれくらいの点数しかとれないのに対し、簡単なケースは300点以上取れる
forum情報だと１ケースで2600点とった人までいるとか…
このことに終盤で気づいたので、そっからは点数低いのをあげようとするのをやめて、点数高いやつをさらに高くするために頑張った

基本的な方針

基本的には全探索するだけ
まず最初に、H(小さい方のグラフ)の頂点の順番を固定し、その順に探索を行う
固定せずに、候補数の少ない点からやったほうがよさそうな気がするが、候補数の計算に時間がかかる、ちょっと先の方に難しい場所があってもそっち方法に進むとは限らない、といった問題があってスコアが悪かったので最終的には固定順で行くことにした
Hの順番を決めたら、次はHの1点目に対応するG(大きい方のグラフ)の点を決めて(全頂点回す)、探索を行う
全探索だととても時間がかかってしまうので、まず最初に嘘探索を行った
ある頂点のマッチングに失敗したときに、普通の全探索だとひとつ前の頂点まで戻るところを、マッチングに失敗した原因となる頂点まで一気に全部戻る
あとで気づいたのだが、これをもうちょっと改良すると嘘でなくなるので全探索の改良もできた(終盤で一気に伸びたのはこれの影響が大きい)
また、うまく行くときはたいていすぐに解が見つかって、うまく行かないときはいつまでたっても終了しない感じだったので、いきなり全探索をするのではなくて探索木の分岐数を最初1に制限し(つまり、バックトラックしない)、それで見つからなければ2にし、それでもだめなら嘘探索→全探索を行った

固定順の計算

固定順の計算法は、まず最初に１点を決めて、すでに決めた頂点集合Uに次のような方法で頂点を追加していくことにより行った

  • Uの2点以上と接続している頂点があれば、その中でUとの接続次数がもっとも大きい物を加える
  • そのような頂点がなければ、Uから出発してUに戻ってくる最小無向閉路を探し、その閉路上の点を順番に追加する
  • そのような閉路がなければ、Uから出発して、どこにも進めなくなる最小のパスをさがし、そのパス上の点を順番に追加する

最初の一点の計算は、全ての点に対して、そこを１点目とした場合にその後５回閉路を辿るのに何頂点必要かを計算し、もっとも小さいのを採用した
こんな感じで序盤に難しい場所(基本的に辺の数が多いほど難しい)を探索すれば、できるだけ早い段階で解がないと判定できて実行時間が短くなるはず

探索の方法

f(v)=v2をv∈V(H)に対応する点がv2∈V(G)であることを意味するとする
探索はf(v)の値をv=0から順に決めていくことにより行う
最初の点は|V(G)|個の可能性があるので全通り回すことによって決めるとして、1番から先の点vに対しては次のように行う

  • vに隣接する点u(<v)を探してくる
  • f(u)に隣接する点v2を探してくる
  • f(v)=v2としたときに、v2の隣接関係が大丈夫かチェックする
  • 大丈夫ならf(v)=v2としてv+1のマッチングを行う
  • v+1のマッチングに失敗したらv2の他の候補を調べる

よく考えると、v+1のマッチングに失敗した原因がf(v)=v2とは無関係であった場合、v2を他の点に変えてもやはり失敗することが確定しているのでさらに前の頂点まで一気にもどることができる
そこで、マッチングに失敗した原因となる頂点のリストretを用意し、次のように改良した

  • vのマッチングにおける失敗の原因リストret_vを別に用意する
  • vに隣接する点u(<v)を探してきて、ret_vにuを追加(f(u)が変化すれば、f(v)の候補点が変化するので可能性が生じる)
  • f(u)に隣接する点v2を探してきて、f(v)=v2としたとき、v2の隣接関係が大丈夫かチェック。駄目だった場合にはその原因のうちで最も番号の小さいものをret_vに追加する(一番小さいの以外が変化しても、結局一番小さいやつのせいでf(v)=v2のマッチングは失敗する)
  • 大丈夫ならf(v)=v2としてv+1のマッチングを行う(この時点でretとret_vは別物のまま)
  • v+1のマッチングに失敗したとき、retにvが含まれているかを調べ、含まれていなければ他の候補を調べる必要はなく、そのままリターン(retもそのまま)
  • 含まれている場合は、v2を変化させればうまく行くかもしれないので他の候補を調べる
  • 全ての候補で駄目だった場合は、ret_vの要素を全部retに加えてリターン

この改良によりローカルでは1000点以上上がった(TC鯖上では500点くらいしか上がらなかった)

高速化

簡単なケースでは、ほとんど詰まることなく単に時間との勝負だったので、高速化が必要だった
Javaでも高速化を結構がんばっていたが、やはりC++にしたほうが良いのは明らか
でも、C++に移行するとアルゴリズム的な改良が出来ない自信があったので、終盤ギリギリまでJavaでやってからC++に移行してひたすら高速化祭りをした
結局C++移行によりローカルでは800点くらい上がった(TC鯖上では400点くらい)

反省点

ローカルテスターとビジュアライザの仕様上、インタラクティブにするのがめんどかったので、どうせ300点くらいまでしか取れないだろうと思って入力は300点分あらかじめファイルに吐いておき、リダイレクトで起動するということを行っていたが、終盤になって300点なんて軽ーく超えるという状況になってしまった
実はこいつらの中には1000点近く取れてるのがいたみたいで、そうなるとおそらく探索だけでなく固定順の計算とかもボトルネックになっていると思われ、そこら辺もちゃんと最適化すべきだったorz
あと、ほぼ全部解けるのなら、Gに含まれるクリークの位置をあらかじめ調べておくっていうのも有効だったかもしれない
Gにクリークが少ししかない(多くのケースで3クリークは大量に含まれているが、簡単なケースだと4クリークが一桁個ということがある)場合に一気に候補が絞れるのだが、Gに少ししかないということはHに含まれている可能性も少ししかなくて役に立たないだろうと思っていた
しかし、簡単な問題ではかなり大きいグラフまで解けることを考えると、Hにも結構含まれていそうだった

おまけ

デバッグなどの目的でグラフビジュアライザを作成した
大量の頂点を平面に描画すると辺が重なってワケが分からなくなるので、三次元で配置して、くるくる回せるようにした
頂点数が多くなっても全体の構造も細かい部分の接続関係もちゃんとわかっていい感じ

せっかくなので公開
http://ow.ly/2ll3X
ぱすわーどはてきと
使い方
ダブルクリックで起動
始点 終点 (辺のラベル)
を一行に1辺ずつ入力
まともな配置になるまでShowボタンを連打
ドラッグで回転
頂点を右クリックでその点に接続する辺のみを表示