- 鉄則本のビームサーチ用問題
- 追記：毎ターン得点が決まるからといってビームサーチとは限らない
- 現状：ビームサーチの使い所が分からない！
- 2024/01/09 追記：ビームサーチは多様性が大事
- 追記：ビームサーチで状態のコピーが重いなら1手でやることを大きくすればいい
- 山登りでは筋が悪そうならビーム？
- 2-optが効果的でなさそうならビーム？
- AHC028
- 2024/02/05 元の解を「少し」変更して（高速に）以前と比較できるなら「焼きなまし」？
- 2024/04/10 仮説：山登りの発展が焼きなまし、貪欲の発展がビーム？
- 2024/04/13 木上のビームサーチに興味
- 2024/04/14 "焼きなまし法 >= 山登り法 > ビームサーチ >= greedy" !?
- 2024/04/15 ビームサーチの改善手法を試す
鉄則本のビームサーチ用問題
- これ https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_aw
- 鉄則本を手に入れたのでやってみた
- 自分流にアレンジを加えつつ1から書いたことで、少しハマったが理解が深まった
- Beamの状態がメモリを食うのでグローバルに置く必要があった
- 提出 score=48805 https://atcoder.jp/contests/tessoku-book/submissions/35392329
- これを叩き台としてAHCでも使っていこう
- この問題では序盤の得点も響いてくるのでビームサーチで上位を取るのが効くのかな
- 一方、最終状態でのみスコアが決まるなら焼きなましが向いているのかな
追記：毎ターン得点が決まるからといってビームサーチとは限らない
- AHCでビームサーチを使ったがハマらず
- 道路工事を分配するやつ https://atcoder.jp/contests/ahc017/tasks/ahc017_a
- 毎ターン得点が決まるとはいえ、全体で1つの解として焼きなましとして扱うことも可能
- みんな焼きなまししていたし、ビームサーチしている人は見当たらず
- 追記：今見返すとなぜビームしたのか分からない。貪欲に動くなら「今日は工事しない」が最適になってしまうため
現状：ビームサーチの使い所が分からない！
- 😭
- thunderさんの本によると、
- 文脈がある
- && 多様性に自信 →ビーム
- && 多様性に自信なし →chokudaiサーチ
- 文脈がない
- →焼きなまし
- https://twitter.com/iwiwi/status/1625074245285085184/photo/2
2024/01/09 追記：ビームサーチは多様性が大事
- っぽいぞ AHC021（A - Pyramid Sorting）解説放送 https://youtu.be/VCFmQ4Aa0lg?t=2991
- 上位X個残すとして、スコアが高いが似たようなものをX個残してしまうのはダメ
- （というか、ビームサーチが刺さりそうという感覚がまだないのだが、取る手の多様性が出せそうならビームが刺さるのかも？）
追記：ビームサーチで状態のコピーが重いなら1手でやることを大きくすればいい
- 2024/01/09
- そうすると、データをそのまま持ってコピーしても収まることも https://youtu.be/VCFmQ4Aa0lg?t=3008
山登りでは筋が悪そうならビーム？
- https://twitter.com/e869120/status/1746140523491151944/photo/1
- E8さんでも、山登りでやってみて初期解からそんなに伸びなかったからビームに変更という動きをしているので、見分けられるものでもないのかも
2-optが効果的でなさそうならビーム？
- toriidao.hateblo.jp/entry/2024/01/17/225440
AHC028
- 延長戦。ビームサーチはスコアをそのまま持つのではなく、最適化したいもの（今回では移動距離）を持ってもいい
- 候補を削ってビーム幅を増やすのは良い
- 提出 https://atcoder.jp/contests/ahc028/submissions/49424562
- 延長線perf 2499
2024/02/05 元の解を「少し」変更して（高速に）以前と比較できるなら「焼きなまし」？
2024/04/10 仮説：山登りの発展が焼きなまし、貪欲の発展がビーム？
- AHC032をやって思った
- それは、そう
- ビームにも滑らかさが必要 https://twitter.com/MathGorilla_cp/status/1777494287921586547
- 追記：AHC032にて貪欲をビームに発展させてperf1948 => perf2461
- https://atcoder.jp/contests/ahc032/submissions/52252993
- とはいえかなり時間がかかった。何度も書かないとスラスラいかないだろうし、4hに間に合わないだろう
2024/04/13 木上のビームサーチに興味
- Stateのコピーは重い。それを速くするために木上のビームサーチと言われているものがある
- 詳しい記事を書いてくれている人たちのおかげで学べそう
- しかし、貪欲からビームサーチへの壁があったように、ビームサーチから木上のビームサーチへの壁もありそう
2024/04/14 "焼きなまし法 >= 山登り法 > ビームサーチ >= greedy" !?
- https://github.com/hakomo/Simulated-Annealing-Techniques/blob/master/%E7%84%BC%E3%81%8D%E3%81%AA%E3%81%BE%E3%81%97%E6%B3%95%E3%81%AE%E5%84%AA%E4%BD%8D%E6%80%A7.md
- そうであるならば「とりあえず焼いてみる」という人がいる気持ちがわかる
- うまく行かなければ「いい貪欲を探してみる」からビームへ発展させればいい
2024/04/15 ビームサーチの改善手法を試す
- ゲーム実況者Xの挑戦
- 提出一覧 コード上部に導入手法を記入 https://atcoder.jp/contests/rco-contest-2018-qual/submissions?f.Task=&f.LanguageName=&f.Status=&f.User=peroon
- int visited[50][50]をbitset<2500>に書き換える →効果あり✅️
- BEAM_WIDTH*2のサイズになるごとにソートして下位半分を切り捨てる（＆切り捨て基準GET） →効果あり✅️
- visitedをhashにして「重複除去」（上行って右と、右行って上は同じ事がある） →hash計算コストが高くて悪化❌️
- 色々試せて良かった！
