ビームスタックサーチについての勉強メモ

マラソンマッチ界隈でよく知られている通称chokudaiサーチ、それと似ていると言われてるビームスタックサーチ(beam-stack search)について、ちょっと調べてみました。論文はこちらです。
R Zhou, EA Hansen (2005) Beam-Stack Search: Integrating Backtracking with Beam Search, 15th International Conference on Automated Planning and Scheduling

でも、いまだ分からないところも多いので、まとめました。誤解してそうなので、間違いを指摘してもらえると助かります！論文と照らし合わせながら読んでもらえると良いと思います。

この記事を読むのには以下の知識が必要です。

• ビームサーチ
• 全探索（深さ優先探索など）
• A*アルゴリズム等で出てくる、ヒューリスティック関数の意味

ビームスタックサーチの概要

前提

• 許容的なヒューリスティック関数、つまり、最小値を求めるときは、現在の状態～未来で取りうるコストの下限が必要。最大値を求めるときは上限。（Admissible heuristics)
• 最適解を求めるのが目的。枝刈りは行われるが、基本は全部のパスを通ろうとするので、最適解があれば、必ず見つけられる。(Completeness)

特殊なケース

• ビーム幅が十分に大きいときは、分枝限定法-幅優先探索と同じ。バックトラッキングは行われない。
• ビーム幅が1のときは、分枝限定法-深さ優先探索と同じ。（ちなみに、ビームサーチだと、ビーム幅1は貪欲法と同じ。）

疑似コード

上記の論文に載っているビームスタックサーチの疑似コードの引用である。24～28行目の変数relayの部分は、拡張バージョンdivide and conquer beam-stack searchの部分なので、今回は無視する。

ビームスタックサーチの流れ

ビーム幅2で、ビームスタックサーチを使って、最小値を求める場合を考える。（注意：まだ不明な点があるので、グラフをわざと簡単な木にしてます）

各ノードnを状態とし、それぞれのノード内の数字は評価値を表す（f-costと呼ぶ。ノード番号では無い！）。評価関数f(n) は
f(n) = g(n) + h(n)

• g(n)は、スタートノードからノードnまでのコスト
• h(n)は、許容的なヒューリスティック関数、ノードnからゴールノードまでのコストの下限（絶対に過大評価しない値）

スタートノード（f-costが0）から、最小値を求めていく。

Layerごとに、

• f-costでソートする。
• fmin・fmaxという範囲を示すペアの値を持つ。初期値は fmin=0, fmax=U。(Uは現在までの最適解。Uの初期値は+∞で良い)。

fmin・fmaxのペアをレイヤーの小さい順からスタックにpushしていったものを、ビームスタック(beam stack)と呼ぶ。

スタートノードから、ビームサーチをしていく（8行目）。注意点は、f-costが[fmin,fmax)に入るノードだけを探索するところ21行目?。ビーム幅が2なので、上位2つ（低いコスト）しか入れない。ビーム幅から漏れたノードの評価値が新たにfmaxとなる（3行目）。つまり範囲が狭まる。

ゴールノードにたどりついたので、最小値を更新し、U=6となる。もし、fmax>Uとなった場合は、そのLayerはEmpty Layerとなる。Empty Layerが、ビームスタックのtopに来たら除去される。つまり深いLayerから探索から外れていく（46～48行目）。

（ここが全く分かってない可能性あり！）最深層までたどり着いたら、最深層のfminとfmaxが更新される。fminが今までのfmax、fmaxがUになる（50～51行目）。

ここはfmaxはそのまま。評価値5のノードは辿っておらず、ビーム幅2からあぶれたわけではない。

深さ優先探索順に新しい訪問先を辿っていく

別のゴールノードにたどり着いたので、最小値を更新し、U=5となる。常に後で見つかった解のほうが、良い最適解になるのに注意する(44～45行目)。これでビームスタックが空になったので、終了（49行目）。

私見と疑問点

アルゴリズムの観点から

• 疑似コードで、どうやってバックトラッキング（深さ優先探索）を実行しているのか？
  • 普通は深さ優先探索をするには、再帰にするか、stackにpush・popをするか、どちらかだけど、8～37行目を見る限り、popはしていないし、再帰呼び出しもない。
  • 関数searchは毎回スタートから行われているので、新たに訪問するノードの順が、深さ優先探索順になるだけかもしれない。
    • ただ、そうだとすると、毎回スタートから同じノードを何度もたどり、計算量がひどいことになりそうな…。
• 以下の例は大丈夫なのか？f-cost3のノードを訪問する前に、f-cost4と5のノードを訪問するので、fmaxが6になり(3行目)、その後すぐfminが6になるので、f-cost3のノードを訪れずに終わってしまいそう。

• wikipediaでビームサーチを見たら、そこでもヒューリスティック関数の例がでていたし、先行する論文のいくつかもそうだった。もしかして、それが普通？
• ビームスタックサーチを分枝限定法（branch and bound）と呼ぶのは大げさな感じが…。ただの枝刈りでは…。でも、英語版wikipedia見ると、ヒューリスティック関数で枝刈りするだけでも、そう呼べるみたい。

マラソンマッチの観点から

• 許容的なヒューリスティック関数が必要だとすると、使用箇所は限定されそう。
  • 最短距離のようにコストが増えていくだけなら、許容的なヒューリスティック関数を常に0とみなしても、よさげですが。自由に値をとりうる評価関数だと、枝刈りが行われず、ビームスタックサーチは、ただの探索になってしまいます。
• マラソンマッチの探索上手な人だと、そもそも、幅優先だか深さ優先だか最良優先だかあまり区別のつかないような、自由な探索を書く人も多く、まさにビームスタックサーチは、その中に含まれそう。
• ビームスタックサーチとほぼ同じと言われてたchokudaiサーチとは、アルゴリズムも目的も全然違うっぽい。