ビームサーチ
研究室の後輩がマラソンに出るというので一緒に参加してみようかと思いました．ただ，まだ運営がvisualizerを用意してくれないので，とりあえず練習のため，ビームサーチを実装してみました．ビームサーチは名前は聞いたことがあるけどよくわからないアルゴリズムという印象でした．
ググると色々情報が出てくるのでとりあえずこの辺りのサイトを参考にしました．
要は幅優先探索をするんだけど，ただやると計算が終わらないから，それぞれの探索木の深さで評価値がTOP $k$のノードだけ探索を続けようという結構簡単なアルゴリズムでした．練習用にAOJの0-1ナップサック問題をビームサーチで解いてみました．コードはこんな感じです．
数十秒の計算時間がかかるくらいにビーム幅を設定すると最適値*0.9くらいの答えを出してくれるのでそんなに悪くない印象を受けました．ただ，この問題は評価関数簡単だからいいけどもっと複雑な問題は色々厳しそう．
あとはビームサーチをランクアップさせた探索アルゴリズムとしてchokudaiサーチ(正式名称 beam stack search)というのがあるのでそれも勉強しておこう．．．
アルゴリズムは実装してみると色々発見があって面白いです．
