Marathon Match 74 AntiTravelingSalesperson

備忘録．

問題

2次元平面に，3〜10の都市が固定されている．その内1つは開始都市である．
この平面にN（10≦N≦10000）都市を新たに設定する．
開始都市から，未訪問かつ一番近い都市を次々に選んでいき，巡回路を生成する．
巡回経路長を最大化するようなN都市を計算せよ．

思考

Nが小さい時は，追加都市数と固定都市数の比が小さいので，固定都市に依存した都市配置になりそう．Nが大きい時は，比が大きいのであまり固定都市に影響されなさそう．
また，AntiTSPVis（ビジュアライザ）を見ると，最短距離が同じノードが複数ある場合は，一番インデックスが小さいものが選ばれることが分かった．つまり，配列上の都市のインデックスがスコアに影響を及ぼす可能性がある．

ヒューリスティクス

nearest neighbor，tsp，worst tour等のキーワードで調べたところ，三角形状に都市を配置していた例があったので，それを応用した配置にしてみた（下図）．

1つの三角形に注目する（下図）と， $x > \sqrt{\frac{x^{2}}{4}+y^{2}}$ となるので， $y < \frac{\sqrt{3}}{2}x$ となる．

$\frac{\sqrt{3}}{2}$ が無理数なため，xを決めてしまえば，
y=(int)sqrt(3)/2*x
でyの値を計算できる．

N個の都市を間隔xで横にm個，縦にn個並べるとする．
$M=10^{9}$
$\alpha=\frac{\sqrt{3}}{2}$
とおくと，
$mn=N$
$mx=M$
$n\alpha x=M$
となるため，
$x=\frac{M}{\sqrt{N\alpha}}$
$m=\frac{M}{x}$
$n=\frac{N}{m}$

気付いたこと

全体的には上図の通りにギザギザに通っているが，固定都市があるせいで，最終的に残った点を遠回りしているケースがある．
最後に遠回りして戻ってくるような入力を与えられたら強いのかも．

悪あがき

上で書いたような遠回りする（良い）パターンが思いつかなかったため，最後に悪あがきとして，ある割合の都市を乱数で設定することを思いついた．実験的に，追加都市の8%を乱数で設定するとスコアが一番高くなることが分かったので，それを採用した．

その他考えたヒューリスティクス

ヒルベルト曲線
- 遠回りが無いので，三角形よりはスコアが上がらなかった．
下のような再帰曲線
- 正方形の平面に上手く並べることが出来ないので低スコアとなり不採用．

焼きなまし法

Nが小さい時には，焼きなまし法が利用可能だと考えた．しかし最終的には，（Nの値に関わらず）上のヒューリスティクス解に焼きなまし法を適用する形になった．

スコア計算

スコア計算のオーダーは，Visualizerでは $O(N^{2})$ だったが，それでは試行回数が極端に小さくなってしまう． $O(N\log{N})$ で出来ないかと考えていたが出来なさそうだったので結局諦めた．

隣接状態

隣接状態は，ある追加都市を選び上下左右の何れかの方向に乱数距離だけ動かす，という方針にしたが，最後まで自信がないままだった．

工夫

出来るだけ無駄が無くなるようにするため，以下のようにして各パラメータを設定した．

まず，スコア計算が $O(n^{2})$ であるため，1[trial]にかかる時間を
$time(N)=cN^{2}+b$ [ms/trial]
と仮定する．
t[trial]で10000[ms]かかるとすれば，
$t=\frac{10000}{cN^{2}+b}$ [trial]
となる．
マシン依存の定数c，bは，TopCoderに送ったexample submissionの結果から最小自乗近似を使って計算した．

温度Tの設定は，実験的に
$T_{0}=1$ ， $T_{final}=10^{-20}$
と定めた．従って，冷却パラメータσを，
$\sigma=10^{-20/t}$
で計算した．

埋め込み

Nが大きい時について，解の埋め込みを考えてみた．
あるケースについてローカルで長時間焼きなまして得られた解を，
他のケースに適用してみた．
しかし，全く良いスコアが得られなかったので諦めた．

反省点

ヒューリスティクスについてもう少し考えるべきだっった．
後半に遠回りするような都市配置を計算するという方針はそれ程間違っていなかったので，様々な方法を試せばもっとスコア・ランクを上げられた．
他の方法として，逆順に都市の座標を決定していく方法も考えたが，実装の時間が取れなかった．
結局，三角形状以外を試さなかったので，一つの方法にこだわらないで，色々な方法を試したり考察をするべき．