TCO17 Marathon Round 1 (GraphDrawing) の反省 - じじいのプログラミング

問題と1位の方（chokudaiさん）の解法

TCO2017R1

結果

力学モデル（バネ）で、長さ比に応じて力を加える。その後、貪欲法（一番悪い辺の点を、最も高得点になる場所へ移動）で解を改善。
45位/146位 652,515.28点。30位ぐらいの人ともかなりの点差が開いていて、敗北感ある…。

敗北までの流れ

ファーストインプレッション

方針
- 力学モデル
- 焼きなまし
- よさげな頂点同士をマージしながら構築

問題の穴
- 木の足の部分はどうでもよい。
- 距離が近くになる点どうしは、まとめて動かしてもいいかも。
- 三角形などサイクルの形で、辺が絶対につながらず満点が取れないケースもあるので、こういうケースでは理論上最高得点を求めて、最高得点にあわせて、目標長さの条件も緩めたほうがいいのでは。
- MAX_RATIO / MIN_RATIOなのに注意。全部言われた長さにせよとは言ってない。全部スケールしても得点は変わらない？
- 三角形って何個あるんでしょう。位置関係が確定する気がする。
- 長さが整数値になることを使ったHackはなさそう。

ざっくり焼きなまし

近傍
- ランダム移動、だんだん移動量を少なく
評価値
- 最小値だと、差分を使いづらく、雑に書くとO(E)、良くてO(logE)ぐらいな気がしたので、とりあえず重み付きの和で対応

Submission 2 得点 248563.14
上位の得点が、70万点近くなので、恐らくハズレ方針だと思い、あきらめる。

力学モデル（バネ）

メモ

微分せよ。
ズレ0のやつで、位置があうか比較する。
インラインアセンブラがききやすい
論文（良い初期位置とか）
Logをつけてみては？
引っ張る力を比ベース
たぶんランダムな力とかは筋がわるそう。

試したこと

普通のバネで引っ張る
- バネモデル、意外とバネ定数により、発散しやすい。
- 枠外でも力を加えて、枠に入れたほうが高得点になる。
- 今回は目標の長さとの比が得点にかかわるので、長さ比に比例した力を加える（普通のバネは差に比例した力を加えるので、）
- バネの力により簡単に発散するので、バネ定数の調整と、pow()をつけた調整を試す。
  - powやlogを付けた調整は発散しやすかった。
- 距離の短い辺が、強い力でずっと動き続けて足をひっぱる。
序盤は遊びを入れて、自由に動けるようにする。目標得点を0からスタートし、目標票得点内に収まるのであれば力は加えない。そして徐々に目標得点を増やしていく（拘束も強まる）
- →これは極値にハマる可能性を大幅に減らせる有力な方針だと思ったけど、そうでもなかった。結局同じような場所でハマる。
エネルギー最小化
- https://cs.brown.edu/~rt/gdhandbook/chapters/force-directed.pdf のKamada and Kawaiのアルゴリズム。
- バネエネルギーは積分すればいいので、

差ベース
// energy = integrate k*(x-a) dx from x=a to b ====> k * (a-b)^2 / 2
比ベース
// energy = integrate k*(x/a-1) dx from x=a to b ====> k * (a-b)^2 / (2*a)
// energy = integrate k*(a/x-1) dx from x=b to a ====> k * (a * log(a/b) + (b-a) )

- 本当だったら、高速化のためKamada and Kawai多変数のニュートン法で = 0系の連立方程式を解くのだけど、まずは遅くてもいいので、エネルギー最小になる点を全探索で試すことにした。バネより結果が悪いのであきらめる。
このタイミングでビジュアライザも作成。正しくは動いているっぽい。
ズレなしで満点を取れるテストケースを試す
- それでも満点がとれない。
- どうやら初期位置が悪いと簡単なケースでは、ダメなことが分かる。
- 逆にチートして、初期位置を知っているものとしてやると、バネでも高得点が取れる。
簡単なわりには低得点になるケースを探す
- 変な三角形とか、田んぼの田とか、いろいろと手作業でいろいろと作るも見つからず。

Submission 3 得点 475556.16

恐らくバネ方針も良くないのだと思い、あきらめる。

強引な貪欲法

もう一番得点が低い辺の頂点の片方を、700*700の移動先を全部試して一番良いところに移動させる。というか、なぜこれを最初に試さない。

高速化する。得点ハイトマップを作成して、関数形を見る限り、そんなに山の数が多いかんじではないので、焼きなましで探していいのでは？（ドーナツを重ねてくり）

f:id:shindannin:20170511103243p:plain

- 250回ぐらいの焼きなましループで、最適解（=700*700）を90%ぐらいの正解率
得点は伸びたが、上位の70万点には程遠い。
貪欲→バネ→貪欲→バネを繰り返せば、極大値にハマらないのではないか？
- ハマる

Submission 4 得点 606403.67

焼きなまし

貪欲でいいのなら、焼きなましもやっぱり行けるでしょうと思い、焼きなましの戻る

メモ

評価値

最小値（問題のスコアと一緒）
足し算
重み付き足し算（ペナルティはV倍とかにしないとダメ）
分散

近傍

頂点どうしの位置交換
悪い頂点のとなり
辺対称
大ランダム移動（たぶん大きい移動が入った時点で負け）・小近傍移動
速度つき近傍（慣性）
粗いグリッド⇒細かいグリッド

実際にやったこと

評価値

最小値
足し算
重み付き足し算（に比が1から離れていれば離れるほど、さらに悪くなる）
分散
- O(1)で計算できるし、２番目に悪い点、３番目に悪い点も実質考慮できるので、よいかなと思ったけど、だめだった。

近傍

粗いグリッドに分けて、ざっくりした位置を決めたのち、徐々に細かいグリッドにしていく。2*2→4*4→8*8→…
- 32*32を最高にスコアが落ち始めるので、あきらめる。←これはもったいなかった。32以降は別方針にするとか、2段階の解法で高得点いけた

Submission 2と同レベルの得点しかとれないので、やめる。

Beam search系

迷走する。書くほどでもないか…

反省点

部分最適（極値にハマる）理由を考察するのを第一に考える。

シンプルで統一的な解法にこだわりがち。

シンプルで統一的な解法でないと高得点が取れないと、その後複雑な解法にした際も、最終的には点が伸ばせないと考える癖がある気がする。
それ自体はいいのだけど、どうもシンプルな解法をいろいろ試すものの、それぞれの解法への考察が雑になり、点が伸ばせる解法を、謝って枝刈りしてしまっている気がする。
悪いところを考察したうえであれば、例外的な対処も入れて良い。部分的対応をどんどん入れていってよい。
- 力学解法でも、焼きなましでも、高得点は取れてたっぽい。
- 悪そうな解法でも、部分的にでも良いところを探すようにする。
- ちゃんとした物理に従う必要はないですよ。
  - バネモデルで、たまにワープさせたって構わない
  - バネモデルで、全部のやつに同時に力を加えなくたって構わない。（一番悪いやつだけとか）

評価関数を状況に応じて変える

（分かってるつもりなのですが…）

例えば、焼きなましのグリッド解法は、高得点を取ってる人はいるので、良い方針だったはずなのだけど、2*2のときも、700*700のときも、似たような評価関数を使っているのは、大変良くない。
そもそも、段階ごとの目的に意識がいってない気がする。粗いグリッドのときは、「正しいセルに振り分ける」のが目的、細かいグリッドのときは「高得点取れるようにする」なのに、評価関数が1つというのは良くない。それぞれの段階での目的をはっきりさせて、評価関数をつくろう。
これは焼きなましに限らない。Beam Searchの前半と後半で評価値を変えたりもするし、目的ベースで、柔軟にかえる