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位でした

問題概要

N頂点の無向グラフが与えられる。各頂点を半径1の円周上に等間隔に配置する。辺を頂点間を結ぶ線分とみなしたときに、辺の長さの総和を最小化せよ。

最終提出の解法

焼きなまし法を使いました。

近傍選択について

 2点swapを行いました。swapする点の組の選び方は、

以下の二通りの方法のうちどちらかを50%の確率で実行するようにしました。

1.一点をN点の中から一様ランダムに選び、もう一点を選んだ点の近くから選ぶ。

2.辺を一様ランダムに選び、「一方の端点」と、「もう一方の端点の近くの点」の二点を選ぶ。

温度管理について

以下のような温度のスケジューリングを考えました。

縦軸が温度、横軸が時間です。

温度が0になるたびに、それまでに見つかった中で最も良い解へ巻き戻しています。

f:id:ats5515:20180201065134p:plain

遷移の条件式について

普通は diff<-T * log(rand())のようにするところを、 diff<T * rand()としています。

考察

問題がいかにも焼きなましだったので焼きなましました。

単純な問題設定の中でいかに差をつけるかを考えると、焼きなましを使うとすれば、工夫するところが近傍選択と温度管理しかないので、この2つについて集中的に考えてました。

近傍選択に関しては、swapする点を上に書いたように二通りの方法で選んでます。一つ目の方法はスコアの差が小さくなるようにという発想に基づき、二つ目の方法は局所的にスコアが改善される可能性が高くなるようにという発想に基づきます。

一つ目の考え方はよく見るのですが、二つ目の考え方はあまり見ないような気がします。swap以外にはinsertベースのものを考えましたがうまくいきませんでした。

温度管理について、最終的に特殊なスケジューリングになったのは、時間を延ばしてもそこまでスコアが改善しないことから複数回同じ焼きなましを行うようになり、さらに初期温度を線形に減少させていくことでスコアが改善されたという経緯をたどります。

 焼きなましを繰り返した方が有効なのは、厳密解付近での解の多峰性によるものだと思います。前回までに得た良い解をどうにかして利用したいと考えた結果、解を巻き戻しながら初期温度を減少させていくアイディアを得ました。この方法は、「焼きなましを100回やる。そのうえで初期値を減少させる」という見方のほかに、「1回の焼きなましがある。これを100等分し、それぞれの部分で一旦温度を0へ収束させるようにする」という見方ができると思います。全体としての焼きなましの機能を保ちながら、解の多峰性に対処するというのがこの手法の特徴だと思います。