Marathon Match 97 PointsOnTheCircle 参加記録
問題文：
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17063&pm=14816
順位表：
https://community.topcoder.com/longcontest/?module=ViewStandings&rd=17063
provisional 1位でした。
最終結果も変わらず1位でした
問題概要
Ｎ頂点の無向グラフが与えられる。各頂点を半径1の円周上に等間隔に配置する。辺を頂点間を結ぶ線分とみなしたときに、辺の長さの総和を最小化せよ。
最終提出の解法
焼きなまし法を使いました。
近傍選択について
2点swapを行いました。swapする点の組の選び方は、
以下の二通りの方法のうちどちらかを50%の確率で実行するようにしました。
１．一点をＮ点の中から一様ランダムに選び、もう一点を選んだ点の近くから選ぶ。
２．辺を一様ランダムに選び、「一方の端点」と、「もう一方の端点の近くの点」の二点を選ぶ。
温度管理について
以下のような温度のスケジューリングを考えました。
縦軸が温度、横軸が時間です。
温度が0になるたびに、それまでに見つかった中で最も良い解へ巻き戻しています。
遷移の条件式について
普通は diff<-T * log(rand())のようにするところを、 diff<T * rand()としています。
考察
問題がいかにも焼きなましだったので焼きなましました。
単純な問題設定の中でいかに差をつけるかを考えると、焼きなましを使うとすれば、工夫するところが近傍選択と温度管理しかないので、この2つについて集中的に考えてました。
近傍選択に関しては、swapする点を上に書いたように二通りの方法で選んでます。一つ目の方法はスコアの差が小さくなるようにという発想に基づき、二つ目の方法は局所的にスコアが改善される可能性が高くなるようにという発想に基づきます。
一つ目の考え方はよく見るのですが、二つ目の考え方はあまり見ないような気がします。swap以外にはinsertベースのものを考えましたがうまくいきませんでした。
温度管理について、最終的に特殊なスケジューリングになったのは、時間を延ばしてもそこまでスコアが改善しないことから複数回同じ焼きなましを行うようになり、さらに初期温度を線形に減少させていくことでスコアが改善されたという経緯をたどります。
焼きなましを繰り返した方が有効なのは、厳密解付近での解の多峰性によるものだと思います。前回までに得た良い解をどうにかして利用したいと考えた結果、解を巻き戻しながら初期温度を減少させていくアイディアを得ました。この方法は、「焼きなましを100回やる。そのうえで初期値を減少させる」という見方のほかに、「1回の焼きなましがある。これを100等分し、それぞれの部分で一旦温度を０へ収束させるようにする」という見方ができると思います。全体としての焼きなましの機能を保ちながら、解の多峰性に対処するというのがこの手法の特徴だと思います。
Marathon Match 94 ConnectedComponent 参加記録
問題：
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16958&compid=57152
順位表：
https://community.topcoder.com/longcontest/?module=ViewStandings&rd=16958
provisional２位でした。
現在システムテストが行われています。
最終順位も変わらず２位でした
問題概要
S×S行列Mが与えられる。行列の各要素は-9から9までの整数である。
0からS-1の順列pに対し、行列MPを、MP(i,j)=M(P_i,P_j)と置く。
MPの、0以外の要素からなる連結成分ごとに、(要素の合計)×(要素数)^(0.5)を求める。その最大値を最大化するようなpを求める問題。
方針
端から決めていくビームサーチ。
評価関数
答えの順列の最初のn個が決まっているとき、行列MPの左上n×nは固定される。
この領域において、ある連結成分の要素の合計や要素数などの量を計算して、評価値を計算する。
具体的には、深さをdepthとして、
(評価値)= (要素の合計)×(要素数)^(0.5+(Sの１次式)×(1-(depth/S))^(定数))
(Sの１次式)＝0.4+0.3×(S-50)/(500-50)
(定数)=0.1
ポイントは、合計値より要素数に重みを置いたこと、探索が進むにつれて真のスコアの式に近づくこと。
ただし、真のスコアと同じ式をそのまま使った場合と比べても改善幅は大したことない
状態遷移
答えの順列のn+1番目を、(S-n)通りの候補に対し全探索します。連結成分をUnionFindで持っておき、必要な部分だけ書き換えれば一つの状態を作るのをO(S)でできる。
↑必要な情報は右図のように圧縮できる。
ビームサーチ全体では、深さO(S)、一つの状態に対する遷移先O(S)個、一つの状態を作るのにO(S)で全体でO(S^3)でできる。
時間管理
ビーム幅をうまく調整しながら、ちょうど時間を使い切ることに挑戦した。
nターン目では、(S-n)通りの候補に対して、O(n)で状態を更新するので、かかる時間は、(ビーム幅)×(S-n)×nに比例すると考えられる。これまでのかかった時間からこの比例定数を求め、時間ちょうどに終わるためのビーム幅を毎ターン計算した。
考えたこと
最初に問題を見て思ったのは、焼きなましたいが時間がきつそうということ。
一般に時間が十分にあるときは、焼きなましのように文脈無し問題として解くのがいいと思うが、今回は問題サイズが大きく、時間が足りないと感じた。
実際書いてみると、解の要素をランダムにswapするのを近傍とする山登りは、時間内に収束させることができそうにない。
次に他の可能性として、近傍を工夫する、文脈ありとして解くなどを考えた。結局は、どういう方針をとるにせよ、ただの高速化勝負でないとすれば、計算量レベルでの改善が必要だと考えた。解の順列の値を順に定めていくことで、差分計算が利くことに気付きBeamSearchを実装。大きいケースでは山登りを10分続けたときと同じくらいのスコアが出て、方針が間違っていないことを確信した。
その後は時間管理や評価関数の細かいところを調整しただけで本質的な改善はできなかった。
２位になってからローカルで１５パーセントくらいスコアを上げたが、１位の順位表の得点は全く削れていなかったので、１位とはかなり差があると思われる
最終結果ではかなり僅差となったので、１位まであとちょっとだったらしい。
実行結果
seed=2, score=22740.49
seed=5, score=203385.38
Tco17 mm r1 GraphDrawingに参加しました
問題：
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16903&compid=55119
順位表：
https://community.topcoder.com/longcontest/?module=ViewStandings&rd=16903
最終順位 5位でした。
問題概要
無向グラフが与えられ、各辺に対し要求長さが設定される。頂点を700*700の２次元正方形領域の格子点上に配置し、要求長さとの比の（最小）/（最大）を最大化する。
最終submit概要
２段階焼きなまし（もどき）したあと微調整
１段階目SA
頂点座標をdoubleでもち、要求長さとの差の２乗の和をエネルギーに設定
z方向への自由度を新たに設け、各頂点ごとのz座標の2乗の総和をエネルギーに加えた。こちらは時間の経過とともに重みを増すようにして、最終的にグラフがz=0の平面付近に来るようにした。
遷移は１つの頂点をランダムに動かす。動かし方はだんだん小さくなるようにする。
２段階目SA
2次元上で、エネルギー関数は、各辺に対しその辺の実際の長さをx,要求された長さをLとして、
E(x)=pow(A*abs(1-(x/L)),B)
を計算し、その全辺にわたる和をとったものとした。
この関数E(x)の値は、Bを大きくにしていくとxがある範囲より外側は限りなく大きな値で、内側は０に限りなく近い値という形になる。実際には、Bは100くらいの値に固定した。Aを調節すればこの範囲を狭めたり広げたりできる。Aを調節して現在のmin.maxより少し内側にこの範囲が来るようにした。
遷移は１段階目と同様一つの頂点をランダムに選び、ランダムに動かす。動かし方は１段階目より小さくした。
微調整
頂点を格子点に割り当てる。
辺の比が最も悪いもの（最大、最小の二つ）から１つをランダムに選び、さらにその辺の両端の頂点から１つをランダムに選ぶ。x座標かy座標またはその両方を選び、最大辺なら縮めるように、最小辺なら伸ばすように±1することで解を改善を図る。最良解が見つかるたびに解を保存しながら時間まで繰り返す。
全体的なこと
１段階目は５秒、２段階目は4秒、のこり微調整という時間配分にした。
遷移において700*700の範囲に常に収まるようにした。
最初入力された要求長さに0.95くらいかけたものを使った。
考察
実際のスコアで焼きなましをやるのは解空間に高い壁ができてしまうので無理があると考えた。テストケースの生成において、最初にグラフを配置し長さを測ってからその値を少しずらすという方法を使っているため、この最初に配置された原型をまず再現しようとおもった。１段階目SAの発想ではそこから来ていて、差の二乗を使えば解空間はなだらかだし、最終的に良い解を得やすい頂点配置になってくれるはず。グラフを3次元空間内で動かしたのは、こうすることで局所解が緩和されるから。ただし正しい方向へ向かう割合は減るのでいいことばかりではない。
２段階目焼きなましはコンテスト終盤に書いたもので、焼きなましを本来のスコア関数で使えるようにしようとしたものだが、最終的に焼きなましもどきになった。というのも、動かしてみたらエネルギー関数のBの値を大きな値で固定するのが最も良いという結果になったため、悪い方向への遷移はほとんど起きていないように思う。しかしこれでスコアは10K近く上がった。Bが大きな値固定になるくらいならわざわざこんなエネルギー関数用意する意味がなかったと思うが、検証している時間はなかった
実は焼きなましが１２日目くらいまで正しく動いていなかった（エネルギーの上昇がある値以下なら必ず遷移し、その値がだんだん小さくなるというベター山登り）。しかしスコアはそれほど悪くなかった（正しく直してもスコアは微増にとどまった）。焼きなましはあまりちょうどいい方法じゃなかったかもしれない。例えばよくモンテカルロ法の例として円周率の計算が出てくるが区分求積とかしたほうがよっぽど精度は高く出るといったように、確率的シミュレーションはほかの適切な問題固有の発想に基づくヒューリスティックスに比べて効率が悪いという可能性が常にある。
doubleで管理している間は700*700おさめなくても後で平行、回転、拡大縮小すれば問題ない。しかし焼きなましの精度が悪くなったり、一部の点が外側に行き過ぎて、700*700に当てはめたとき狭い範囲に点が集まり、格子点に割り当てたときのロスが大きくなってしまうなどの問題がおきた。そのため、状態遷移において常に700*700におさめるようにした。代わりに要求長さをあらかじめ0.95倍しておくことで、適度に柔軟に頂点を配置できるようにした。なお焼きなましの精度が悪くなる理由として、テストケースの生成でははじめに原型を作るので、700*700に収まるというのは良いヒントになっているからだと思う。
考えたこと（時系列順）
日記などをつけていないので細かいところは覚えていないですが。
・コンテスト開始直後
なぜか1000K付近の高得点勝負になると思っていた。頂点をdoubleで持つ発想、微調整のアルゴリズムの発想はこの時点であった。
・3日目～6日目くらい
初めてコードを書く。山登りが全然だめと分かったので、焼きなましを書く。微調整パートも書いて720Kくらい。この時点で焼きなましはバグってる。
順位表の１位が780K強で飽和しているように見え、100K付近の高得点勝負ではないとこの時点で気づく。
要求された長さに1より小さい一定数をかけておくとスコアが上がるのに気付いた。
・7日目～11日目くらい
焼きなましと微調整の間に物理シミュレーションを置く。比が最大、最小付近の辺に特別に大きな力が加わるようにした。それ以外は時間がなかったため流れ作業でできるようなパラメータの調整しかしていない。780Kくらい
・12日目
焼きなましがバグっているのに気づく784K
・13日目
最後の「微調整」パートだが、実はこの時点では全然微調整ではなく、この部分で大幅にスコアが伸びるという感じだった。ただ「微調整」パートの内容的にやはりこれは字義通り微調整であるべきだと思い、物理シミュレーションの上位互換を考え始める。
2段階目SAの発想に至り実装。パラメータの調整、高速化を少々。788K
・14日目
大学のレポート類がやばくて何もできなかった。完全にスケジュール調整ミス。あると思ってたパラメータ調整にかける時間がなかった。最後改善しているかどうか定かでないものをやけくそで提出し終了。791K
反省点
・最後パラメータ調整をしている時間がなく、適当に決め打ったまま最終提出まで行ってるパラメータが結構ある。テストケース数も100ケースだけで判断していたのでシステムテストでは順位が落ちそう。実際終了後ローカルで500ケースだけ実行したところ、794K点くらいでprovisional6位のtomerunさんは796K出ているそうなので少なくともここの順位は入れ替わりそう。しかも、僕の実行環境は（おそらく）topcoder鯖より性能がいいので、もっと低く出そう。いくら時間がなくてもちゃんとケース数をとってテストするべきだと思った。どうせ差が微増にとどまるから、改善しているかどうか判断できないので、パラメータの組み合わせ数を稼げても意味がない。
追記：システムテストが終わり、provisional6位のtomerunさんには抜かれたがprovisional4位のpsyhoさんを抜いて順位変わらず５位でした。
・パラメータ調整をもっと機械的に、あるいは自動でやってくれるものを作っておくべきだったのかもしれない。
・焼きなましをバグらせているのに１２日間程気づかなかった。明らかにパラメータを最適化するとおかしい値になっていたので、原因を探しに行くべきだった。
・コードが汚い。
さいごに
反面教師でもなんでもいいので何かの参考になればと思います。
round2も出ると思うのでよろしくお願いします。
