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も出ると思うのでよろしくお願いします。
