Marathon Match 74

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

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

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

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

  • Anti..巡回セールスマン問題の最長路を求める問題かな?(注:間違いです!
    • 初期の点が何個かあるといえ、これって研究している人がいそうで、めっちゃ不利なネタな気がする…。
    • 2次元の巡回セールスマン問題って、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次元平面に都市が何個かある。セールスマンは、スタートの都市から、すべての都市を1回ずつ訪問して、スタートの都市に戻ってきたい。普通の巡回セールスマン問題とは違い、このセールスマンは、まだ訪れていない都市の中でもっとも近い都市を訪れる(最短経路を通るアルゴリズムではない)。あなたは追加で都市を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秒!。今回は間違えない!
  • 要するに、いまいちなアルゴリズムで動くサラリーマンを、わざとたくさん歩かせるように都市をおく問題。
    • いや、いまいちか?2次元平面上なら、単に一番近い都市をどんどん訪れるというのは、かなり最適解に近くなりそうだが。このアルゴリズムの弱点を突かねばなるまい。
  • 焼きなまし系のアルゴリズムは使えるんだろうか?計算量的にはいけそうだけど…。というよりは幾何の問題?
  • 1000000000*1000000000のフィールドをそのまま使うのがいいのか、量子化したほうがいい?
  • 点を何個かのグループに分ける。ただ、分けたグループの最適解は、全体の最適解とはぜんぜん近くならなそうな気もする。
  • 長時間計算すればするほど、結果がよくなるタイプの問題なんだろうか?もし、そうであれば長時間計算して求めた解の性質を探したいところ。
  • 問題を勘違いしたものの、ETSP max ETSPの解放はチェックしたほうがいいかも。ちょっと役に立つこともあるかも。
  • 単に格子点に都市をおいたら結構強い?

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

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

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

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

終了(11/8)

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

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

-

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

反省点

  • 最初は、広く浅く!
  • 座標の扱い方。
    • 2,3,4,5でたくさん割り切れる数字でやっとけば。27000の倍数とか。
    • 最初から決めうちは、あとで間違いにきづくときつい。
  • 長時間焼きなまししておいて、解を予想するという方法もあったのでは?特に、自分の頭だけで考えている時間、コンピューターにも考えさせよう。

他の方の解法

  • 後ろから、うそDP
  • ある点からもっとも近い点の判定。四分木・x軸のみソートとか