Marathon Match 74 - じじいのプログラミング

(2011年10月29日の記事を移行したものです。)

マラソンスタートしました(10/29)

前回の反省を生かして、文章化することにしました。

ファーストインプレッション(10/29)

Anti..巡回セールスマン問題の最長路を求める問題かな？（注：間違いです！）
- 初期の点が何個かあるといえ、これって研究している人がいそうで、めっちゃ不利なネタな気がする…。
- ２次元の巡回セールスマン問題って、ETSP(Euclidean (Euclidian) traveling salesman problem)というんですね。
- 検索してみた。
  - http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/demo/TSP/index.html
    - 最短路は線が交差しないようなので、最長路を目指すなら線が交差するといい？
  - http://maven.smith.edu/~orourke/TOPP/P49.html
    - showed that the maximum TSP can be solved in time O(n) for rectilinear distances in the plane 2次元の最長TSPはO(n)で解ける！なんと論文があるとは… （注：これはrectlinear distanceです。euclid distanceではありませんので、実は全然違う）
    - いや、でも、これぐらいは作題者が気づくんじゃないか。テスターもTCOファイナリストだし。
    - 問題を読み直してみる。
    - 誤読してましたorz

問題
2次元巡回セールスマン問題。2次元平面に都市が何個かある。セールスマンは、スタートの都市から、すべての都市を１回ずつ訪問して、スタートの都市に戻ってきたい。普通の巡回セールスマン問題とは違い、このセールスマンは、まだ訪れていない都市の中でもっとも近い都市を訪れる（最短経路を通るアルゴリズムではない）。あなたは追加で都市をN個置ける。セールスマンの移動距離が最大になるように、都市を置きなさい。

Nはpower(10,X) Xは1.0～4.0まで均等。つまりN=10～100まで1/3,N=100～1000まで1/3,N=1000～10000まで1/3。
元から配置されてる都市は3～min(10,N/3)
- ほとんどのケースで3～10ってこと？かなり少ない印象。大きく影響を与えるんだろうか…
相対スコア。得点は(あなたの距離/1位の人の距離)の4乗！
- これは、ちょっとの距離差でも大きく点差が開きそう。前回の反省を生かして、Nにあわせて、きめ細かくやる。
計算時間は10秒！。今回は間違えない！

要するに、いまいちなアルゴリズムで動くサラリーマンを、わざとたくさん歩かせるように都市をおく問題。
- いや、いまいちか？２次元平面上なら、単に一番近い都市をどんどん訪れるというのは、かなり最適解に近くなりそうだが。このアルゴリズムの弱点を突かねばなるまい。
焼きなまし系のアルゴリズムは使えるんだろうか？計算量的にはいけそうだけど…。というよりは幾何の問題？
1000000000*1000000000のフィールドをそのまま使うのがいいのか、量子化したほうがいい？
点を何個かのグループに分ける。ただ、分けたグループの最適解は、全体の最適解とはぜんぜん近くならなそうな気もする。
長時間計算すればするほど、結果がよくなるタイプの問題なんだろうか？もし、そうであれば長時間計算して求めた解の性質を探したいところ。
問題を勘違いしたものの、ETSP　max ETSPの解放はチェックしたほうがいいかも。ちょっと役に立つこともあるかも。
単に格子点に都市をおいたら結構強い？

アプローチ1 じょじょに移動距離を増やしていく

まずは１次元で考えてみる。図1のように、点はまず端においたほうが距離が伸びる。ただ図3に注目。端に置いた後、真ん中に置くのは正しくない。できるだけいったりきたりするようにさせるためには、図4のように最初に動きすぎてはいけないことが分かる。
これを２次元に応用すると、図5のような形になるのかなぁ…。じょじょに移動距離が長くなっていき、２次元に展開にするには、こんなかんじかと。ただし、図6・図7のように、このうずまきの距離を大きくするために、うずまき間の距離を狭くしてしまうと、セールスマンが最短距離のところに移動してしまうため、うずまきにならない。
図8は結構よさそう。つまり、うずまきを作る多角形の辺の長さと、うずまき間の頂点距離を同じにする。図8だと1,2,3,4が等距離、5,6,7,8が等距離になっている。１辺の長さをxとすると、かなり少ない点の数で8x(=4x+2x+x+0.5x...)ぐらいまでの長さが作れそう。
ただし若干端が無駄な気がするので、図9のような正多角形もあるかもしれない。いろんな形を試そう
また図10のように等間隔でなくても、ある程度いけるのかも…
いろんな幾何図形を考えてみよう。ネットで探したり、街中でものを注意してみたり、画像検索もありかもしれない。

アプローチ2 行き止まりに追い込み交差させる。

線が交差するのは、距離が伸びるので基本的によいこと。また、等間隔に点をおけば、セールスマンの移動方向をコントロールできる（今回の問題で距離が同じ点の場合は、IDの小さいほう優先とあるので、IDはこちらで勝手に決められるので実質コントロール可能）。なのでうまく行き止まりに追い込めば、無駄に移動させることができるはず。
これも等間隔というのさえ守れば、いろんな図形が考えられるかもしれない。四角形・三角形は確かに充填率は高そうだけど。
図11は四角形でおいた場合。思いつく限りでは、この例が行き止まりに持ち込めやすそう。ただ、行き止まり頻度が少なくても、行き止まりの脱出距離が長ければお得になるので、それは検討しないと。
図12は三角形でおいた場合。1.18倍とわずかながら上。あと、こちらのほうが、同じ点の数でも図11より１辺の長さを大きくできそう。ただ、今回整数の座標にしか点がおけないのが、ちょっときついかも。
この思いついた2とおりだけでは、距離がいまいち伸びてない。ここは、BitDPでメモ化探索をして、試すのがよさそう。自分では尾もいつかなそうなので。計算時間がかかりそうなので、早めに仕掛けておく。

終了(11/8)

結局、実装に夢中になっていて、終わってしまった…。
まずは放送用にメモのみ。

10/30 submission 1 単にグリッド上におくだけ15点ぐらい

じっさいに書いてみると、スカスカの部分が多いので、別の形に変更。
うしろからGreedy submission 2 40点。2時間ぐらいなので、意外と高得点。
方針決定

斜め移動の階層

うしろからGreedy

四角移動の階層
- 各エリアをどう通過するか、ハミルトン路を決める
- それぞれのエリア内でビットDPをする

土曜ハミルトン路、どうやってもとめるの?
39$バカ
結局、自力で求められたけど。
日曜
- 実装、難しいとは思ってたけど予想以上に難しい
- 斜め移動→四角移動の階層へ移動するときに、
-
日曜深夜
- 実装なんとかできたが低スコア
- 原因:荒過ぎる。いろいろな階層数をためしたとしても、使用している点の数が、Nと離れていて、その分スコアを失う。
- 対策1:足りない点は、他のメッシュで埋める。
  - 点が増えるが、前提が崩壊して点があまり伸びないケースあり。
  - しかも、座標の扱いに大きく失敗しているので、実装難。
- 対策2:多すぎる点はまびきする。
  - 間引きできるパターンは限られる。あまり点が伸びない
月曜朝わるあがき
- ビューワで点をてきとうにドラッグ。「うしろからGreedy」から点が増えてるんですけど…
- てきとーに山登りしてみる。submission 59点。休み3日以上使ったのに、てきとーな解のほうが圧倒的によい。