AtCoder Heuristic Contest 027 参加記
AtCoder Heuristic Contest 027に参加し、273位でした。
サンプルのdfsと同じものを実装する。 スコアの計算を実装する。
以下、特に明記しない場合はシードが1~100のときの平均
Average = 21991473.54
RDLUの順番を変える
Section titled “RDLUの順番を変える”24通りを試し、最良を選択する
Average = 19521742.3
もっとランダム
Section titled “もっとランダム”各マスでランダムに優先順位を決める。 20000回程シミュレーションできた。
Average = 21251525.91
あんまりよくなっていない
現在の解からランダムに派生
Section titled “現在の解からランダムに派生”ちょっと寄り道したり、省略したりしてみて改善するなら採用を繰り返す。変化が小さいのですぐに局所解になったり、広い盤面だと計算に時間がかかって十分に派生させられないので、いろいろ残念。大きい変化を頑張って採用できるようにする案もあるが、次の手に。
Average = 18365379.48
15000000くらいなら提出する気になるかな…
DFSから変更
Section titled “DFSから変更”DFSは実装が簡単だが、無駄な移動が多い。
なるべく少ない移動ですべてのマスを少なくとも一回通る方法について考える。
これは巡回セールスマン問題（TSP）なので、条件つきでの近似解法について調べる。
三角不等式が成り立つときの問題をMetric TSPというらしい。
この条件下ではDFSのルートから既に行ったことのある場所をとばしてルートを決定していくというのがあるらしい。
クリストフィードのアルゴリズムはよくわからなかった。O(n3)らしいので今回の条件だと使えない？
RDLUの順に評価するDFSを変形する形で実装してみる。
Average = 16936320.88
思ったより改善した
24通り試す
Section titled “24通り試す”Average = 16144839.97
まだTSPが不完全…。 グリッド上のTSP解法は確実に論文があるはずだが、検索能力がないので見つけられない。 Bing AIにきいてみるとFutureの記事を提案されるがこれは一般的なグラフの解法。 食い下がると、次数5以下の場合の多項式時間アルゴリズムを出してくれる。そんなものが存在するのか…。英語論文を読む気にならない
2-optを使ってみる
Section titled “2-optを使ってみる”Average = 15892483.36
とりあえずTSPは十分と思って、ここから適当に遷移させる。
適当に山登り
Section titled “適当に山登り”Average = 14025677.55
結構改善した
遷移先をいい感じに評価
Section titled “遷移先をいい感じに評価”汚れが大きいところを通るものを選ぶようにする
Average = 13801249.45
局所最適解に陥ることが多い
探索幅を広げる
Section titled “探索幅を広げる”TSPの後、改善する手順を繰り返す。 改善する段階は重みをつけているので一意だが、TSP解がランダムなのでいろいろな解がえられる。
Average = 13567886.96
TSPがいまいち
Section titled “TSPがいまいち”そもそもTSPが最適でないし、多様性もない
TSPの最善でないものもいろいろ採用してみる
Average = 13178283.81
遷移先を増やす
Section titled “遷移先を増やす”Average = 13213827.0
収束の速いケースでは改善したが全体としては悪化
汚れやすい場所を探す
Section titled “汚れやすい場所を探す”入力生成方法を読むと、1~20の汚れやすいゾーンがある。汚れやすい場所でないところは10以下で汚れやすい場所は最大1000なので、かなり差がある。実際どのくらいかわからないが、汚れやすい場所をそうでない場所の10倍以上通るくらいがよさそう？
10より大きい場所だけでTSPを解けばいいのでは？
間に合わず 悲しい
結構いいアイディアが思いついたと思ったけど、実装しきれず… 参加賞が200人対象なので頑張ったが、さすがに届いてなさそう