Marathon Match 94 ConnectedComponent 参加記録

問題:

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16958&compid=57152

順位表:

https://community.topcoder.com/longcontest/?module=ViewStandings&rd=16958

 

provisional2位でした。

現在システムテストが行われています。

最終順位も変わらず2位でした

 

問題概要

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次式)×(1-(depth/S))^(定数))

(Sの1次式)=0.4+0.3×(S-50)/(500-50)

(定数)=0.1

ポイントは、合計値より要素数に重みを置いたこと、探索が進むにつれて真のスコアの式に近づくこと。

ただし、真のスコアと同じ式をそのまま使った場合と比べても改善幅は大したことない

状態遷移

答えの順列のn+1番目を、(S-n)通りの候補に対し全探索します。連結成分をUnionFindで持っておき、必要な部分だけ書き換えれば一つの状態を作るのをO(S)でできる。

f:id:ats5515:20170824145053p:plain

↑必要な情報は右図のように圧縮できる。

ビームサーチ全体では、深さO(S)、一つの状態に対する遷移先O(S)個、一つの状態を作るのにO(S)で全体でO(S^3)でできる。

時間管理

 ビーム幅をうまく調整しながら、ちょうど時間を使い切ることに挑戦した。

nターン目では、(S-n)通りの候補に対して、O(n)で状態を更新するので、かかる時間は、(ビーム幅)×(S-n)×nに比例すると考えられる。これまでのかかった時間からこの比例定数を求め、時間ちょうどに終わるためのビーム幅を毎ターン計算した。

考えたこと

最初に問題を見て思ったのは、焼きなましたいが時間がきつそうということ。

一般に時間が十分にあるときは、焼きなましのように文脈無し問題として解くのがいいと思うが、今回は問題サイズが大きく、時間が足りないと感じた。

実際書いてみると、解の要素をランダムにswapするのを近傍とする山登りは、時間内に収束させることができそうにない。

次に他の可能性として、近傍を工夫する、文脈ありとして解くなどを考えた。結局は、どういう方針をとるにせよ、ただの高速化勝負でないとすれば、計算量レベルでの改善が必要だと考えた。解の順列の値を順に定めていくことで、差分計算が利くことに気付きBeamSearchを実装。大きいケースでは山登りを10分続けたときと同じくらいのスコアが出て、方針が間違っていないことを確信した。

その後は時間管理や評価関数の細かいところを調整しただけで本質的な改善はできなかった。

2位になってからローカルで15パーセントくらいスコアを上げたが、1位の順位表の得点は全く削れていなかったので、1位とはかなり差があると思われる

終結果ではかなり僅差となったので、1位まであとちょっとだったらしい。

実行結果

seed=2, score=22740.49

f:id:ats5515:20170824161118p:plain

seed=5, score=203385.38

f:id:ats5515:20170824161431p:plain

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の2次元正方形領域の格子点上に配置し、要求長さとの比の(最小)/(最大)を最大化する。

最終submit概要

2段階焼きなまし(もどき)したあと微調整

1段階目SA

頂点座標をdoubleでもち、要求長さとの差の2乗の和をエネルギーに設定

z方向への自由度を新たに設け、各頂点ごとのz座標の2乗の総和をエネルギーに加えた。こちらは時間の経過とともに重みを増すようにして、最終的にグラフがz=0の平面付近に来るようにした。

遷移は1つの頂点をランダムに動かす。動かし方はだんだん小さくなるようにする。

2段階目SA

2次元上で、エネルギー関数は、各辺に対しその辺の実際の長さをx,要求された長さをLとして、

E(x)=pow(A*abs(1-(x/L)),B)

を計算し、その全辺にわたる和をとったものとした。

この関数E(x)の値は、Bを大きくにしていくとxがある範囲より外側は限りなく大きな値で、内側は0に限りなく近い値という形になる。実際には、Bは100くらいの値に固定した。Aを調節すればこの範囲を狭めたり広げたりできる。Aを調節して現在のmin.maxより少し内側にこの範囲が来るようにした。

遷移は1段階目と同様一つの頂点をランダムに選び、ランダムに動かす。動かし方は1段階目より小さくした。

微調整

頂点を格子点に割り当てる。

辺の比が最も悪いもの(最大、最小の二つ)から1つをランダムに選び、さらにその辺の両端の頂点から1つをランダムに選ぶ。x座標かy座標またはその両方を選び、最大辺なら縮めるように、最小辺なら伸ばすように±1することで解を改善を図る。最良解が見つかるたびに解を保存しながら時間まで繰り返す。

全体的なこと

1段階目は5秒、2段階目は4秒、のこり微調整という時間配分にした。

遷移において700*700の範囲に常に収まるようにした。

最初入力された要求長さに0.95くらいかけたものを使った。

考察

 実際のスコアで焼きなましをやるのは解空間に高い壁ができてしまうので無理があると考えた。テストケースの生成において、最初にグラフを配置し長さを測ってからその値を少しずらすという方法を使っているため、この最初に配置された原型をまず再現しようとおもった。1段階目SAの発想ではそこから来ていて、差の二乗を使えば解空間はなだらかだし、最終的に良い解を得やすい頂点配置になってくれるはず。グラフを3次元空間内で動かしたのは、こうすることで局所解が緩和されるから。ただし正しい方向へ向かう割合は減るのでいいことばかりではない。

 2段階目焼きなましはコンテスト終盤に書いたもので、焼きなましを本来のスコア関数で使えるようにしようとしたものだが、最終的に焼きなましもどきになった。というのも、動かしてみたらエネルギー関数のBの値を大きな値で固定するのが最も良いという結果になったため、悪い方向への遷移はほとんど起きていないように思う。しかしこれでスコアは10K近く上がった。Bが大きな値固定になるくらいならわざわざこんなエネルギー関数用意する意味がなかったと思うが、検証している時間はなかった

 実は焼きなましが12日目くらいまで正しく動いていなかった(エネルギーの上昇がある値以下なら必ず遷移し、その値がだんだん小さくなるというベター山登り)。しかしスコアはそれほど悪くなかった(正しく直してもスコアは微増にとどまった)。焼きなましはあまりちょうどいい方法じゃなかったかもしれない。例えばよくモンテカルロ法の例として円周率の計算が出てくるが区分求積とかしたほうがよっぽど精度は高く出るといったように、確率的シミュレーションはほかの適切な問題固有の発想に基づくヒューリスティックスに比べて効率が悪いという可能性が常にある。

 doubleで管理している間は700*700おさめなくても後で平行、回転、拡大縮小すれば問題ない。しかし焼きなましの精度が悪くなったり、一部の点が外側に行き過ぎて、700*700に当てはめたとき狭い範囲に点が集まり、格子点に割り当てたときのロスが大きくなってしまうなどの問題がおきた。そのため、状態遷移において常に700*700におさめるようにした。代わりに要求長さをあらかじめ0.95倍しておくことで、適度に柔軟に頂点を配置できるようにした。なお焼きなましの精度が悪くなる理由として、テストケースの生成でははじめに原型を作るので、700*700に収まるというのは良いヒントになっているからだと思う。

考えたこと(時系列順)

日記などをつけていないので細かいところは覚えていないですが。

・コンテスト開始直後

なぜか1000K付近の高得点勝負になると思っていた。頂点をdoubleで持つ発想、微調整のアルゴリズムの発想はこの時点であった。

・3日目~6日目くらい

初めてコードを書く。山登りが全然だめと分かったので、焼きなましを書く。微調整パートも書いて720Kくらい。この時点で焼きなましはバグってる。

順位表の1位が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さんを抜いて順位変わらず5位でした。

・パラメータ調整をもっと機械的に、あるいは自動でやってくれるものを作っておくべきだったのかもしれない。

・焼きなましをバグらせているのに12日間程気づかなかった。明らかにパラメータを最適化するとおかしい値になっていたので、原因を探しに行くべきだった。

・コードが汚い。

さいごに

反面教師でもなんでもいいので何かの参考になればと思います。

round2も出ると思うのでよろしくお願いします。