daruma3940の日記

理解や文章に間違い等あればどんなことでもご指摘お願いします

MMLightinig2018にっき

問題のリンク
TopCoder

問題を見る。
あれ~なんかアルゴっぽい問題だなぁ...?
いきなり何もわからなくなる(´・ω・`)
なんか見たことありそうな内容なのでとりあえずググってみる
彩色問題とかいう割と有名な問題らしい。これ初心者には厳しい問題では?
論文を読んでみるとグラフを作ってグラフの次数が大きいところから色を塗っていけばいいらしい(Welsh-Powell)それで実装してみる。
塗り替えマスの最小化は簡単そうなので最終日にやればええやろ。
うまくいったのでこれが第一投。
その論文にはこの方法を改善する方法が書かれていたが書き方が非常に悪く(人のせいにするな)分からなかったのでパス

第二投
色の塗る順番をいろいろ工夫してみる。
適当に2つの順番を入れ替える→全然よくならない
近接する2つを入れ替える→割とよくなる
同じ次数の頂点同志のを入れ替える→割とよくなる
Poolを作って解を複数保持する→よくならない

これらの情報から状態空間を観る。
えー、ちょっと悪くなったところからはいいところに行きつきにくく、状態空間は乱拓でよくなるような感じではない、狭い谷がある感じなんだろうか?
これは焼きなましは厳しいのではという感覚を得る。
しかし私は焼きなまししか知らないんだよ!!!!

以前のコンテストでもなんとかうまく焼きなましに落とし込めている人が強かったので
なんとかうまく焼きなませないか考える。
彩色数をそのままスコアにしてしまうとあまりよくないのではという感覚になる
とりあえずスコア関数というかエネルギー関数を工夫しよう。
ハミルトニアンHを

H=\sum_{ < i,j  > } Q_{ij}x_i x_j +\lambda \sum_{i} |x_i|

とする。
ここで
Qは隣合う色に同じ色があればHを大きくしようとする行列で
|x_i|は色の大きさでindexの大きい色でぬろうとするとHが大きくなる。
つまり小さいindexだけを使って色を塗ろうというわけで
近傍はある場所の色を別の色にして作成する。
近傍も小さく状態に制限がない
これはを焼きなましで最小化すれば彩色は出るはずだが
これがちゃんと隣り合う色は別の色でないといけない制約をみたしてくれるかどうかは分からないがとりあえず楽観的に焼いてみる
しかし制約をみたす解が現れてくれない上に第一投の方法で作った階以上に良い彩色が得られない...
近傍をいろいろ試したが全然ダメ。
というか 状態空間を観ようとしてこれは焼きなましは厳しいのではという感覚を得たのに焼いてるのホントダメ。

これはアルゴ的に考えないといけなさそうだな。

ここで論文を読み漁る。

RLF法というのを試してみるが
遅すぎる。
遅くともスコアが良くなるのなら高速化するがスコアが良くなってないので没

Ant SystemとTabu Search とGAに行き当たる。
何とかこれらの方法でうまくいかないだろうか?
時間がないとりあえずAntSystemを論文を読みながら実装するが
論文では補グラフにフェロモンをつけろと書いてあったが、それではちゃんと順番を得られないと思ったので独自の方法でフェロモンをつけることにする
いいフェロモンのつけ方がわからん.....
バグってたのかもしれないがさっぱりよくならん....
「 塗り替えマスの最小化は簡単そうなので最終日にやればええやろ 」と最初に思ったがもう最終日になってしまっている....
今回あんまりやる気が出なかったのでダラダラしてしまっていた...
塗り替えマスの最小化は色を塗ったグラフのPoolを作ってそこから一つ取り出して山登り
以上。何もできない何もわからなかった。
悔しみが深い


ーーーーーーーーーーーー感想戦ーーーーーーーーーーーーーーー
(毎回終了後にやってる教授と感想戦
私:ハミルトニアンHを H=\sum_{ < i,j  > } Q_{ij}x_i x_j +\lambda \sum_{i} |x_i| としてみましたがうまくいかなかったですねぇ。
教授:時間が経つにつれてTを下げるのではなくそのQの値を大きくしていくのは量子アニーリングでよくやられてる方法なんだけどやってみた?
私:なるほど....


ちょくだいさんが同じことをやっていて笑う。
しかしこれをやってみてうまくいかなかったという人が私のほかにもいてるみたいで
ここの調整はすごく難しいんだろうなぁ
アイディアは似てると思っても実際の実装を見ると「レベル高すぎww全然似てねぇわww」ってなるやつですね



というかスコアの計算方法ちゃんと把握してなかったの痛いですね...気を付けないと...



iwashiさんマジで頭いい....

なるほど...

そういえば始まる前に書いたテストケース並列実行のためのスクリプトなぜかエラーが出て動かなかったんだった。
直したいが進捗発表がね...