![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
[[プロコン]] *概要 [#a37a76e9] -wataさん「マラソンのコツはコードを書かないこと」 *詰まったら [#b20c7172] -考察を丁寧に。得点が増える・増えない理由を、丁寧に考える。 -思考過程をまとめれば、変なのに気付くの自明なので、メモを必ずとる。 -点が平均以下のときは、絶対に簡単な解法を見逃している *意識すべきこと [#iffc23aa] -問題をしっかり把握する -判断基準を明確にする --この工数の作業をすれば、どのぐらいの順位になるのかの予測をなるべく正確に答えられるように。 --「この方針の長所と短所は何か？」、「この方針が失敗する可能性としては、どんなものが考えられるか？」 --もしダメなら根本的に見直す必要性 -反復期間を短くする --反復は4時間以内に（実装が難しいなら、100倍ローカルで時間がかかってもよいし、並列化してもよいし、GPGPUしても良い） *あいまいな問題文 [#o9f7ff42] -テスタのソースコードに書かれている問題生成手順が、多くの場合、本番でも使われます。 *問題解法について [#x18ab6ba] -大きいサイズと小さいサイズで同じ解法を使うべきかを考える -評価関数が低い理由を大別して、カウントアップする 高度合成数 https://gist.github.com/pekempey/9eddf9342f65552a92845e035960e8a3 Chokudai Contest 2 これ劣モじゃない？？ 多項式時間で厳密最適解がでる。 http://ibisforest.org/index.php?%E5%8A%A3%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%A9 近似解法もある。 http://www.kurims.kyoto-u.ac.jp/~takazawa/coss2010/shioura-1.pdf 非厳密DP面白い（Chokudai Contest 1のchokudai解答） 結局、自分が解ける部分問題に落とすパートが強い マラソン感想 ある前提を入れると最適解がもとまる「パスなら…」「左上から右下なら…」 強化学習は人よりかは強くなっても、アドホックアルゴリズムに比べるとね https://topcoder.g.hatena.ne.jp/CKomaki/20141202 Topcoderではtime関数がいみわからんくらい重い ビームサーチ、焼きなまし、山登りを習得するのが基本。 貪欲や山登りを使っている場合は大抵焼き鈍しやビームサーチ等に変えることにより大幅に得点を伸ばすことができます。 大抵「問題のスコアリング + 良さそうな状態にボーナスポイント」という形になります。 やきなまし 診断人さんのマラソン解説 http://shindannin.hatenadiary.com/entry/20121224/1356364040 焼きなましとビーム、どっちを使うべき？ http://qiita.com/takapt0226/items/b2f6d1d77a034b529e21 焼きなましは初期解答が大雑把にきまるとつよい http://topcoder.g.hatena.ne.jp/agw/20141205 コルンさんのマラソンのはなし。テストかけ、テスト300ケースはかけ。プロファイラを使え。プロトタイピングは4時間以内。開発ループを回せ。枝刈りを観測的に行う方法。 http://www.colun.net/archives/294 まず生の点捨をとる。根性が大事。 例えば、最近流行りのビームサーチを例にしましょう。「ビームサーチで200ターンのゲームをする、幅は10000」とかあったとするじゃないですか。これ、「100ターン時点で、50ターン時点の親となるノードは何種類残ってるか」とか、多分みんな調べてないじゃないですか。 そういうの調べれば、「途中でどれくらい偏ってるか」とか、「どれくらい同じノードの情報で埋め尽くされちゃってるか」とかわかるじゃないですか。それをやれば、例えばchokudaiサーチに切り替えたら良さそうとか、もっと別の変則ビームサーチだったり、微妙に焼きなまし混ぜたりとか、色んなバリエーション試せるじゃないですか。こんなんビジュアライズするまでもなく、ちょっとコード書いてデバッガで見るなりprintfで出力してみるなりすれば、すぐに解ります。でもみんな調べてないわけですよ。こういう、「とりあえず今どう動いているか調べてみよう」みたいな気概が大切なんです。ぶっちゃけ、こういうの１個１個やっていくの、超めんどくさいです。めんどくさいけど、「こうなってるといいな」って予想して、「こうなってない」みたいな状態を見つけることこそが、プログラムの改善に繋がるわけですよ。そこら辺手抜いちゃいけない。手抜いちゃいけないけど超根性いる。でも頑張らないとだめ。ってことは、「これを実装してスコアが上がると思った理由」ってのがそれなりにあるはずです。それであれば、「自分はこう思っていたのに、そうならなかった」って発見がこの時点であるわけですね。もうこの時点で十分な収穫なんですよ。「こう思っていた」自体が嘘だった。それが悪い要素だったり、反対向きだったりした。 「こう思っていた」は正しかったのだけど、それよりもっと大きい「こうなってはいけない」要素が存在した 手法だけ覚えてもしゃーないんです。とにかく自分で生のデータを見る。生のデータが良くわからんなら、どうやって可視化するか考える。別に「可視化」「ビジュアライズ」って、絵として表示しろって意味じゃないんですよ。普段プログラム動かしてて見えてない部分とか、そういうのを何らかの形で見えるようにしろって話なんですよ。すっげー泥臭い部分なわけですよ。 http://chokudai.hatenablog.com/entry/2014/12/04/000132 これが便利らしい *問題のタイプ [#w94a657c] -ビームサーチ系 --ゲームの遷移みたいなものがある場合はこういう遷移（DAGっぽいやつ） -焼きなまし系 --貪欲でいいのなら、焼きなましもやっぱり行けるでしょう -- *量子アニーリング [#g59e4123] -組み合わせ最適化問題の一般的な近似解法 -[[巡回セールスマンを量子アニーリングでpythonで解く>http://qiita.com/ab_t/items/8d52096ad0f578aa2224]] -量子アニーリングの専用マシン（D-Wave）が存在する。 --量子アニーリングはD-Waveという専用マシンで有名になったわけですが、このマシンは約10億円（推定）はする高価な装置です。 --装置の内部には減磁や冷却のための装置が詰まっていて、絶対零度に近い極低温で動作する超伝導デバイスを守っています。 --超高級な物理実験装置を、組み合わせ最適化問題を解く仕組みとして使う -量子アニーリングを、パソコンでシミュレーションする方法を量子モンテカルロ法と呼ぶ。 -[[量子アニーリングを機械学習に応用>http://knowledge.sakura.ad.jp/tech/4273/]] *Kaggleの勝ち方 [#xb35cb15] -https://codezine.jp/article/detail/9330 *まとめる [#vc16bf81] これが有効になるのは、「連結性」だったりとか「連鎖」だったりとか、隣り合うものとの繋がりが重要になるケースが多いかな。逆にそういう要素がなければ、手順が限定される必要がないのに順番に埋めてる分、焼きなましにほぼ確実に負ける。 逆にビームサーチ系列は、ターン制ゲームじゃない限り使わない！って人がいて勿体ないなあ、とちょっと思ってる。どうせ最適解が出せない問題だったら、「こういう順番で埋めていく！」って決めてビームサーチ、ってのは、普通に有力な選択肢だよ。埋めた後に補正かけるとなお良い。 Chokudai先生も連結性を問う問題はビームサーチが有効と明言してるのに人々はなぜ焼きなましてしまうのか gnuplotでhistogramを書くためのいいまとめ http://www.ss.scphys.kyoto-u.ac.jp/person/yonezawa/contents/program/gnuplot/bar-graph.html Matplotlibのいいまとめ http://myenigma.hatenablog.com/entry/2015/08/30/223559 動画的にプロットする方法 matplotlib http://qiita.com/hausen6/items/b1b54f7325745ae43e47 http://hakomof.hatenablog.com/entry/2017/08/24/195537 評価関数はO(S2)だがy_kawanoさんがchokudai contest（本問題と似ていて連結数を大きくする問題）で使っていたテクで数倍早くした。自力で思いつける類ではないので感謝 かぐるのslack https://twitter.com/tkm2261/status/899987496443887617 GNU parallelの良いまとめ。 https://www.slideshare.net/koji_matsuda/gnu-parallel hakomoさん、MMで最小費用流を使ってる… http://hakomof.hatenablog.com/entry/2017/05/25/232039 部分問題として厳密解が（何らかの理由によって）求められないとき特に悩む。厳密解が求まらない以上どんな実装をするかで何(が/を)犠牲になるのかが変わるので、その選択に自信が持てないことが多い。全体方針とのバランス結構難しくてわからない hakomoさん、MMでセグ木も使ってる… http://kurenai3110.hatenablog.jp/entry/2017/05/05/124133 hakomoさん、今回のMMでも永続UnionFindを使ってる… http://chokudai.hatenablog.com/entry/2017/05/01/231825 https://www.slideshare.net/yowaken/topcoder-marathon-match-92-lighting-yowa 自分はスコアに対して温度管理をするのではなく、温度と連携させるのは速度という形で焼きなましを実現した 例えばchokudaiサーチに切り替えたら良さそうとか、もっと別の変則ビームサーチだったり、微妙に焼きなまし混ぜたりとか、色んなバリエーション試せるじゃないですか。 めんどくさいけど、「こうなってるといいな」って予想して、「こうなってない」みたいな状態を見つけることこそが、プログラムの改善に繋がる 「スコアが上がらなかったら捨てる」と言いました。まぁこれだと勝てません。「こう思っていた」自体が嘘だった。それが悪い要素だったり、反対向きだったりした。 「こう思っていた」は正しかったのだけど、それよりもっと大きい「こうなってはいけない」要素が存在した。 前者の時は、「これは嘘だったから、意識しないで良い」って思えるし、運が良ければパラメータ反転させるだけでスコア上がったりします。こっちはそんなに嬉しくない。逆張り… https://www.slideshare.net/kazumamikami1/88-54397136 前の行動が影響する無茶振りにはビームサーチが便利 Beam searchは 貪欲法である程度良い解が出せるが、最適な解が出せない、というような問題に対し、手軽により良い解を見つけることが出来ます。 ビームサーチでは、評価値の上の方のものから採用していきます。すると、似たような状態だけどちょっとだけ違う、というのが大量に発生してしまいます。これだと、ビーム幅が広くても、様々な局面を探索することが出来ません。 ここで、chokudaiサーチを使うと、「先行してあんまりよくなかった結果」と「後から見つけてとりあえず良さそうな結果」の両方が探索されます。ざっくり見積もって、ビーム幅Kだと、logK種類くらいの結果がそこそこ探索される感じになります。ビームサーチだとこれが1種類になりがちなので、悪いパターンにハマってしまうことが多いです。 chokudaiサーチでは、多様性が生きない場面だと、単純に悪くなることが多いです。多様性が要らない場合は、chokudaiサーチの最初の方の探索は純粋に無駄になります。隠しパラメータ、評価のラグの時定数が大きかったり多かったりするばあいは、chokudaiサーチのほうが良さそう 上位陣はビームサーチだそうです。「2つの操作の間で依存関係が強いから」だそうです。納得 その3度ともが、予選では強文脈ゲームによる通過であり、焼きなまし法の使えない問題分類だった。 近年、文脈のない探索の出題が増えてきており、焼きなまし法が正解方針であることが多くなっている 2年前に想像していたよりずっとずっと高温からスタートし、そして局所解になってすらいない様な中途半端なところを行ったり来たりしながら、温度が下がっていくことで移動可能な範囲が狭まっていくが、その間、より大局解に近い領域を高確率で選び続ける。 焼きなましは正直あんまり使ったことがなかったのだけれども、この間、大学院の後輩の焼きなましに関する説明を聞いてからは、根本的に焼きなまし法は凸凹している広域の探索には向かないんだなと思った。 焼きなまし法は、大局的な凸、中曲的な凸、消極的な凸が、フラクタルっぽく重ねあっている時に使えるらしい これは、「温度変化でしっかり冷ましていけば、ランダムな動きでもある程度良い方向行けるでしょー」みたいな甘えが生み出すもので、最後の方はある程度やっぱり貪欲とか混ぜて、しっかり深いところまで見に行く動きを入れないとうまくいかないこともしばしば。とりあえず、よほど探索空間が焼きなまし法に向いていない限りは、致命的な欠陥がある探索法、という理解を僕はしている。 あまりにトゲトゲしている場合は、ちゃんと一旦底まで降りてあげるような動きを積極的に入れてあげないと上手くいかないことが多い。 そもそも「全体を包むおっきいお椀」というのが存在しなくって、色んなところにそこそこの解があるやつ！ こういうのは焼きなましでやること自体が悪い。多点スタートでどうにかしよう。短い時間である程度の解を出して、一番良いところを見つけたら潜ってく、みたいな感じ 。「距離が近いことと、スコアの期待値にどう相関があるのか？」が、まぁ、探索空間の形 自分の場合はまず「近傍」というものを作りやすいかどうか（2点スワップすればいいじゃんとかそういうの）を見てる あとはまぁ根本的な話として、「評価を差分で高速に取ることが可能か？」って焼きなましにおいて超重要なところ やきなまし http://shindannin.hatenadiary.com/entry/20121224/1356364040 http://www.colun.net/archives/774 ちょくだいさんの具体例を含んだ焼きなましの「解空間」の話 https://togetter.com/li/607979?page=2 valid pathを全部表示するくらいのビジュアライザは作るべきでした (上位陣はほとんど作ってた) https://topcoder.g.hatena.ne.jp/CKomaki/20141202/1418158488 質のよい乱数大事 C言語のrand()は遅いので、高速なxor128を使いましょう。 前回サブミット時の結果と比較する マラソンの感想 http://d.hatena.ne.jp/wata_orz/20100805/1281000288 http://topcoder.g.hatena.ne.jp/shindannin/20110601/1306944431 ただ、多点スタートで結果がよくなるケースは、そもそもスコア関数や近傍が良くないので、そこを見直したほうがよいかもしれません。 短時間系コンテストとの関連 MarathonがSRMなどの短時間系のコンテストと全く違うのが、「最適解じゃ無くてもよい、というか最適解とか無理」という部分だと思います。 「ちゃんと良い解を得るにはどうすれば」とあまり深く考えていると、手が止まってしまって先に進まなくなりがちです。 SRMのレーティングは高いけれどもMarathonは苦手、という人は、このあたりで引っかかってるんじゃないでしょうか。 逆に、短時間系のコンテストで使うようなアルゴリズムは知らないでいいかというとそんなことはありません。 解答の一部にDPが登場することはよくありますし、探索や最短経路も頻出です。 事実、日本からの参加者をMarathonレーティング順で見ていくと、上位18人までがSRMのレーティング黄色以上、うち11人が赤経験者です。（2012-05-02現在） https://www.otinn.com/groups/view_group.php?gid=1376&sort=14 Greedyは強い 「Marathon何やったら良いかわからない」という人には「とりあえずGreedyで」と言っています。 もちろんそれだけで上位は取れませんが「この方針でこんなにスコア取れるのか」とびっくりすることは多いです。 ランダムは強い 上に同じ。 せっかく制限時間が10秒・20秒とあるのだから、計算パワーをめいっぱい使ってあげましょう。 逐次的に改善できるか 要は焼きなまし・山登り。この形にできるかどうかが大きな分かれ目になります。 焼きなましが有効であることが明らかな問題はみんなそれをやってくるので、そこまでたどり着いていなかったら勝負から蚊帳の外な感じになってしまいます。 焼きなませることが自明ではない場合にも、うまく状態の近傍を設計して逐次的改善が可能な形にできると強いです。 探索空間の削減 単純化して言ってしまうと、Marathonの問題というのは「ものすごく大きな探索空間から、いかに良さげな解を持っていそうなところだけを探れるか」です。 そこで、探索空間を減らすため、一部のパラメタを決めうってしまったり、嘘枝刈りを入れたりします。 この"嘘"の加減が重要なのですが、そのあたりが職人芸になる部分でしょうか。 巡回セールスマンはLKHが早い。1700頂点20秒0.5%誤差。 https://www.google.co.jp/search?q=Lin-Kernighan+heuristic%E3%80%80%E5%AE%9F%E8%A3%85&oq=Lin-Kernighan+heuristic%E3%80%80%E5%AE%9F%E8%A3%85&gs_l=psy-ab.3...3216.6079.0.6310.8.8.0.0.0.0.153.858.3j5.8.0....0...1.1j4.64.psy-ab..3.1.105...0i30i19k1.RMxlmavYZ4c |
