非厳密アルゴリズム のバックアップ(No.4)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• 非厳密アルゴリズム へ行く。
  • 1 (2017-03-23 (木) 05:33:48)
  • 2 (2017-03-23 (木) 06:47:42)
  • 3 (2017-05-24 (水) 18:35:32)
  • 4 (2017-08-17 (木) 12:00:25)
  • 5 (2017-09-21 (木) 15:54:27)
  • 6 (2018-04-13 (金) 16:41:20)
  • 7 (2018-06-11 (月) 13:18:54)
  • 8 (2018-12-21 (金) 11:41:03)
  • 9 (2019-05-02 (木) 22:24:29)
  • 10 (2019-12-15 (日) 02:50:45)
  • 11 (2019-12-15 (日) 19:32:29)
  • 12 (2020-04-03 (金) 17:30:41)
  • 13 (2024-03-03 (日) 01:24:30)
  • 14 (2024-03-05 (火) 11:38:31)

プロコン

概要 †

• wataさん「マラソンのコツはコードを書かないこと」

詰まったら †

• 考察を丁寧に。得点が増える・増えない理由を、丁寧に考える。
• 思考過程をまとめれば、変なのに気付くの自明なので、メモを必ずとる。
• 点が平均以下のときは、絶対に簡単な解法を見逃している

意識すべきこと †

• 問題をしっかり把握する
• 判断基準を明確にする
  • この工数の作業をすれば、どのぐらいの順位になるのかの予測をなるべく正確に答えられるように。
  • 「この方針の長所と短所は何か？」、「この方針が失敗する可能性としては、どんなものが考えられるか？」
  • もしダメなら根本的に見直す必要性
• 反復期間を短くする
  • 反復は4時間以内に（実装が難しいなら、100倍ローカルで時間がかかってもよいし、並列化してもよいし、GPGPUしても良い）

あいまいな問題文 †

• テスタのソースコードに書かれている問題生成手順が、多くの場合、本番でも使われます。

問題解法について †

• 大きいサイズと小さいサイズで同じ解法を使うべきかを考える
• 評価関数が低い理由を大別して、カウントアップする

高度合成数 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 これが便利らしい

問題のタイプ †

• ビームサーチ系
  • ゲームの遷移みたいなものがある場合はこういう遷移（DAGっぽいやつ）
• 焼きなまし系
  • 貪欲でいいのなら、焼きなましもやっぱり行けるでしょう

量子アニーリング †

• 組み合わせ最適化問題の一般的な近似解法
• 巡回セールスマンを量子アニーリングでpythonで解く
• 量子アニーリングの専用マシン（D-Wave）が存在する。
  • 量子アニーリングはD-Waveという専用マシンで有名になったわけですが、このマシンは約10億円（推定）はする高価な装置です。
  • 装置の内部には減磁や冷却のための装置が詰まっていて、絶対零度に近い極低温で動作する超伝導デバイスを守っています。
  • 超高級な物理実験装置を、組み合わせ最適化問題を解く仕組みとして使う
• 量子アニーリングを、パソコンでシミュレーションする方法を量子モンテカルロ法と呼ぶ。
• 量子アニーリングを機械学習に応用

Kaggleの勝ち方 †

• https://codezine.jp/article/detail/9330