$\newcommand{\set}[1]{\{#1\}}$ $\newcommand{\inset}[2]{\{#1 \mid #2\}}$ $\newcommand{\name}[1]{\emph{#1}}$ $\newcommand{\size}[2][]{\left| #2^{#1} \right|}$

ビームスタックサーチ

この前,ビームサーチを書いてみたので,今度はビームスタックサーチを書いてみました.この辺のサイトを参考に勉強しました.

このサイトに載っているchokudaiさんのスライドが(ビームサーチをわかっている人なら)結構わかりやすいと思いました.ビームスタックサーチは僕なりの理解として,ビーム幅を増やしながら何回もビームサーチを行うのだが,今までのサーチ中で探索したノードを記憶しておいて,一度探索した部分は探索しないようにしているようなビームサーチという感じです.ビームサーチで厄介(らしい)ビーム幅の設定を色々頑張らなくとも,探索時間をこちらで設定すればその時間内で,頑張れるだけ勝手にビーム幅を増やしてくれるので,楽ができるという利点があるようです.

解いた問題はナップサック問題で,計算時間を2秒で設定して計算しました.コードはこんな感じです.

確かにビームスタックサーチの方が計算時間を設定できる分使いやすそうだという印象でした.