Gutzwiller のトレース公式 について3
Gutzwiller のトレース公式 について１
い
ponanza さんの思い出。
初めて参加したSDT4一日目の試合開始前に朝ご飯の時間があった。その時に私とほかの開発者さんで楽しく朝ご飯を食べてたのだが、Ponanza さんが入ってきた瞬間、雰囲気が変わった。ponanza の山本さんは、試合前のボクサーのような面持ちで部屋に入ってきた。おっそろしくて、話しかけることができなかった。
しかし、なぜか試合前の練習対局で ponanza に当たってしまった（笑）。そこで ponanza さんに、「今年はどういった改良をされたのですか」と聞いてみたが、そこでは「まあ小さな改良を積み重ねた感じかな」としか答えてもらえなかった。ponanza さんに「君のソフトはどういった改良をしたの？」と聞かれても、「いろいろ試行錯誤してみたけれど強くならなかった」としか答えられなかった。その上、ちょっと会話をした後、山本さんはどこかに行ってしまった。
「小さな改良を積み重ねた」と答えられたとき、「ああ、なんか適当にはぐらかされてしまったんだろうな」と思ったのだけれど、後になってその意味がわかった。大会の打ち上げで ponanza は大会前 1 か月で 600 個のブランチを作って開発したと言っていた。ほんとに小さな改良を積み重ねていたのだ。僕がやっていた 1000 倍の試行錯誤をして少しずつ強くなっていた。自分を恥じましたね。
2018TCO_R1にっき
問題
TopCoder
今回はやる気が全然起こらなかった。
やる気が起こらなかったがとりあえず出ればひどいスコアのままだとレートが下がるのでやる気が出るかもしれないと思ったがもはや抵当に入れるほどのレートもない。
まあ出れば何か勉強になるかなと思いながらとりあえず出る。
初日、進捗発表の準備をした。マラソンのことは何もしてない。
2日目。進捗発表。炎上でしたね。
研究で使う手法について発表したのだけれど、「その方法を使って何がしたいのか」と問われて「担当教官はこの方法を使って僕に何をさせたいのかよく分かってない」と答えたのは面白かったです。
研究なぁ...
ここで問題を読む。またグラフゲーですか。こわれる。
ここ数回焼きなましが出来ず失敗することばかりだったので何とか焼きなましを考える。絶対焼きなましてやる。
とりあえずjunctionを入れずに一筆書きを描いてそれを繋ぎ変える焼きなまし。とりあえず提出。団子順位は超えるのではと思ったけど団子の遥か下にいる。え～
というか奨学金返還誓約書の交付期限は今日までだったらしい。まあ月曜取りに行く。しかし提出締め切りが結構早くて焦る。連絡をなかなか取れないおじに期限内に会えるかどうかだな...
なんというか今回実装するのが怖い。恐怖で手が動かない。自分は何もできないという感情に支配されている。結局私はだめなんだという思いばかりが強くなる。
しかし焼きなましはだめだ.とりあえずアルゴ的に考えよう。
頂点集合kから一番近い頂点を頂点集合kにつなげていく方法でグラフを作る。結構よくなったので提出してみる。
団子に並んだ。（後で知ったが最小全域木と呼ばれる有名方法らしい）一日半かけて団子ですよ諸君。
ここからjuncitonの入れ方を考える。隣接3角形の重心に入れてみる。ランダムに入れてみたほうがよくなった。
良くなったのを一つ見つけたらその周辺にもっと良くなるのがあるはずなので精査する。
あと失敗確率が高い時は近くにもう一つjunctionを打つ。
失敗する確率をちゃんと考慮しようと思って評価を期待値にしたがその分遅くなりスコアは伸びない。
いい感じのjunctionを複数取り出し,8近傍で焼きなます方法もうまくいかなかった。こわれる
風邪をひいてのどいたと微熱と頭痛が止まらない。
やる気がなかったり、恐怖が大きかったのは体の調子が悪かったからかもしれない。のど飴をひたすら舐めないとのどが死ぬ。
熱は37.1度ぐらいだしこの自分で頑張るかどうか選べるぐらいのしんどさというのは非常に酷。
もっと高い熱が出てもう頑張らなくていいよという免罪符を与えてほしかった。
ここで領域を9等分する方法を考える。
領域をわけると一番短いグラフを得るときに隣接する領域だけについてだけ考えて計算すればよくなる。（頂点が領域にいい感じに詰まっている場合）
これでスコア計算は早くなる。
めっちゃ良くなるケースとめっちゃ悪くなるケースが出る。
ここでケースごとに最良の方法を選択する方法を思いつくがそんなせこい真似はあんまりしたくない。
ここで頭痛が激しくなってきて終了。
ーーーーーーーーー感想戦
反省すべきことが多すぎてな....
とりあえず病院行ってくる。
体調が回復したら続きをかく。
MMLightinig2018にっき
問題のリンク
TopCoder
問題を見る。
あれ～なんかアルゴっぽい問題だなぁ...?
いきなり何もわからなくなる(´･ω･｀)
なんか見たことありそうな内容なのでとりあえずググってみる
彩色問題とかいう割と有名な問題らしい。これ初心者には厳しい問題では？
論文を読んでみるとグラフを作ってグラフの次数が大きいところから色を塗っていけばいいらしい(Welsh-Powell)それで実装してみる。
塗り替えマスの最小化は簡単そうなので最終日にやればええやろ。
うまくいったのでこれが第一投。
その論文にはこの方法を改善する方法が書かれていたが書き方が非常に悪く（人のせいにするな）分からなかったのでパス
第二投
色の塗る順番をいろいろ工夫してみる。
適当に2つの順番を入れ替える→全然よくならない
近接する2つを入れ替える→割とよくなる
同じ次数の頂点同志のを入れ替える→割とよくなる
Poolを作って解を複数保持する→よくならない
これらの情報から状態空間を観る。
えー、ちょっと悪くなったところからはいいところに行きつきにくく、状態空間は乱拓でよくなるような感じではない、狭い谷がある感じなんだろうか？
これは焼きなましは厳しいのではという感覚を得る。
しかし私は焼きなまししか知らないんだよ！！！！
以前のコンテストでもなんとかうまく焼きなましに落とし込めている人が強かったので
なんとかうまく焼きなませないか考える。
彩色数をそのままスコアにしてしまうとあまりよくないのではという感覚になる
とりあえずスコア関数というかエネルギー関数を工夫しよう。
ハミルトニアンHを
とする。
ここで
Qは隣合う色に同じ色があればHを大きくしようとする行列で
は色の大きさでindexの大きい色でぬろうとするとHが大きくなる。
つまり小さいindexだけを使って色を塗ろうというわけで
近傍はある場所の色を別の色にして作成する。
近傍も小さく状態に制限がない
これはを焼きなましで最小化すれば彩色は出るはずだが
これがちゃんと隣り合う色は別の色でないといけない制約をみたしてくれるかどうかは分からないがとりあえず楽観的に焼いてみる
しかし制約をみたす解が現れてくれない上に第一投の方法で作った階以上に良い彩色が得られない...
近傍をいろいろ試したが全然ダメ。
というか 状態空間を観ようとしてこれは焼きなましは厳しいのではという感覚を得たのに焼いてるのホントダメ。
これはアルゴ的に考えないといけなさそうだな。
ここで論文を読み漁る。
RLF法というのを試してみるが
遅すぎる。
遅くともスコアが良くなるのなら高速化するがスコアが良くなってないので没
Ant SystemとTabu Search とGAに行き当たる。
何とかこれらの方法でうまくいかないだろうか？
時間がないとりあえずAntSystemを論文を読みながら実装するが
論文では補グラフにフェロモンをつけろと書いてあったが、それではちゃんと順番を得られないと思ったので独自の方法でフェロモンをつけることにする
いいフェロモンのつけ方がわからん.....
バグってたのかもしれないがさっぱりよくならん....
「 塗り替えマスの最小化は簡単そうなので最終日にやればええやろ 」と最初に思ったがもう最終日になってしまっている....
今回あんまりやる気が出なかったのでダラダラしてしまっていた...
塗り替えマスの最小化は色を塗ったグラフのPoolを作ってそこから一つ取り出して山登り
以上。何もできない何もわからなかった。
悔しみが深い
ーーーーーーーーーーーー感想戦ーーーーーーーーーーーーーーー
（毎回終了後にやってる教授と感想戦）
私:ハミルトニアンHをとしてみましたがうまくいかなかったですねぇ。
教授:時間が経つにつれてTを下げるのではなくそのQの値を大きくしていくのは量子アニーリングでよくやられてる方法なんだけどやってみた？
私:なるほど....
電車に乗ったからマラソンツイートをしよう。とりあえず暫定3位。方針は2つあるけどおおよそは焼きなまし。各頂点の色を状態として、1つの頂点の色を変える遷移をするだけ。特徴があるとすれば、「色が被った状態を許容して、ペナルティスコアつけて表現すること」くらい？約2億ループします。
— chokudai(高橋 直大) (@chokudai) 2018年5月8日
ペナルティは徐々に上げると良い感じ。具体的には、Cをoldcolorの色数、tを0~1の温度として、120HWt/(C+1)みたいな感じで、tに対して線形で上げてる。
— chokudai(高橋 直大) (@chokudai) 2018年5月8日
ちょくだいさんが同じことをやっていて笑う。
しかしこれをやってみてうまくいかなかったという人が私のほかにもいてるみたいで
ここの調整はすごく難しいんだろうなぁ
アイディアは似てると思っても実際の実装を見ると「レベル高すぎｗｗ全然似てねぇわｗｗ」ってなるやつですね
TCO18 Marathon Poland Lightning Round おつかれさまでした。必ずしも色数を最小にするのが良いわけではない、というところは引っかけでしたね
— 2018年こそ夏バテにならない (@tomerun) 2018年5月8日
MMお疲れ様でした
— hoshi524 (@hoshi524) 2018年5月8日
やったことは彩色可能な色数が最小の頂点から貪欲に彩色しただけ
反省は
焼きなまし思いつかなかった（前回と同じ・・・）
raw scoreが最終スコアではないケース初めてで無駄にしたから、Scoringの項目はちゃんと読もう
明後日、Round1開始早い！
7色から8色に色増やしてもrepaintを7/8にすればスコア同じだから最小を目指さなくてもいいのかなと思った（思っただけ）
— hirokazu (@hirokazu1020) 2018年5月8日
というかスコアの計算方法ちゃんと把握してなかったの痛いですね...気を付けないと...
焼き鈍しと呼んでいいのは分からないんですが、基本どこかを塗り替えて改善したら採用の山登りをしつつ、遷移しない状況が続いたら徐々に温度を上げて改悪方向にも遷移するようにするやつをやりました
— iwashi31 (@iwashi31) 2018年5月8日
6 色で塗れた後は 6! 通りの permutation を試して塗り替え数最小を探した後全部ぶっ壊して再焼き鈍しへ
— iwashi31 (@iwashi31) 2018年5月8日
iwashiさんマジで頭いい....
色の数は固定して、「色が衝突する領域のペアを常に保持しながら、衝突する領域の色を一つ変える近傍で、そのペアの数を目的関数に焼きなましの条件式に基づいて遷移しvalidな解を見つける 」までを一回の遷移とする焼きなましをしました。
— ATS (@ats5515) 2018年5月8日
色は基本的に6色で、一定時間内に見つからなかったら7色で探すようにした（ほとんどのケースで6色解が見つかった）。領域数が多くもともと使われている色が多いケースでは6色でできても7色でやったほうが良いことがあった。
— ATS (@ats5515) 2018年5月8日
なるほど...
そういえば始まる前に書いたテストケース並列実行のためのスクリプトなぜかエラーが出て動かなかったんだった。
直したいが進捗発表がね...
