ビームスタック探索[1]は、時系列バックトラッキング（つまり深さ優先探索）とビーム探索を組み合わせた探索アルゴリズムであり、深さ優先ビーム探索[2]に似ています。どちらの探索アルゴリズムも、ビーム探索のように、適切だがおそらく最適ではない解を迅速に見つけ、その後バックトラックして、最適解に収束するまで改善された解を探し続ける、 いつでも実行できるアルゴリズムです。
実装
ビーム スタック検索では、ビーム スタックをデータ構造として使用して時系列バックトラッキングをビーム検索と統合し、分割統治アルゴリズム手法と組み合わせて分割統治ビーム スタック検索を実現できます。
代替案
限定不一致バックトラッキングを用いたビーム探索[2]（BULB）は、限定不一致探索とビーム探索を組み合わせた探索アルゴリズムであり、非時系列バックトラッキングを実行する。このアルゴリズムは、ビームスタック探索や深さ優先ビーム探索による時系列バックトラッキングよりも優れた性能を示すことが多い。
参考文献
