ビームサーチは DP

この記事は Competitive Programming (1) Advent Calendar 2018 - Adventar の 6 日目です。
5 日目の記事は armeria_betrue さんの解説記事のはなし - ARMERIA です。
7 日目の記事は xuzijian629 さんの Implicit Treap - 競プロ練習記録です。

ビームサーチとは

ビームサーチとはグラフのヒューリスティック探索アルゴリズムです。初期ノード群から BFS 順に探索していき、深さ（初期ノードからの遷移回数）ごとに良さそう順のノードの上位 N コ以外を枝刈りすることで時間 / 空間計算量を改善します。

58-72p でくわしく説明されているので引用します。

Procon29 public from KubotaHideya

本記事の趣旨

ビームサーチといったら上述のような説明が定番？です。その説明は正しいのですが、私はビームサーチを上述を含んだより広汎なアルゴリズムだと思っています。なので、私の現在の解釈である「ビームサーチは DP の拡張」という観点で説明してみます。色々な視点から同じものの説明がなされるのも一般に良いことですし。

DP の説明は省略します。

f:id:hakomof:20181205200921p:plain

例えば、木を探索するとして、どんな経路を通ったかによらず以降の最適な経路が同じ状態を同一とみなすと、木は DAG になり合流部以降の重複探索をなくすと DP になります。つまり、どういう状態群を同一とみなすかは DP の一端です。

同様に今度は深さが同じ状態群を同一とみなして DP で解いてみましょう。

f:id:hakomof:20181205200949p:plain

単純な形ですが DAG は DAG です。この DAG を DP するコードを起こすとこんなかんじでしょうか。

State dp[Depth];
dp[0] = initialState;
for (int d = 0; d < Depth - 1; ++d) {
    for (State nextState : dp[d].getAllNextStates()) {
        dp[d + 1] = max(dp[d + 1], nextState);
    }
}

お気づきいただけただろうか… この配る DP の振る舞いは幅 1 のビームサーチと完全に一致します（なにやら冗長なただの greedy でもよいです）。なぜ一致するのかというとビームサーチが DP そのものだからというほかないです。結局、ビームサーチは深さごとに状態をまとめる、 DAG になる、 DAG のトポロジカル順序である深さの昇順にビームを更新していく、と DP をしているに過ぎなかったのです。

ビームサーチの DP との違い

状態のまとめ方が過剰
評価関数
ビーム幅

状態のまとめ方が過剰

効率的な探索をしてなお最適解が現実的な時間で求まらないとき、非最適解でよいから現実的な時間で求めたいという動機があります。そこで、現実的な実行時間になるまで状態を過剰にまとめるというのが思想の出発点だと思っています。

評価関数

本来異なる状態を同一とみなす以上、最適解に通じる状態が残るとは限りません。ですが、状態のつぶれた情報をフルに駆使した評価関数で精度の底上げができます。

ビーム幅

例えば、実行時間が 10 秒くらいになるような状態数が 500 万くらいに状態をまとめるといった器用なことはできません。そのため、実行時間と性能に融通が利きません。ですが、ビーム幅を導入すると実行時間は約ビーム幅倍になり相応に性能が上がる（ことがある）ので、少し融通が利くようになります。

以上よりビームサーチは状態の過剰なまとめを許容する形に拡張された配る DP だと思っています。

で、何ができるの？

ビームは深さ以外でも切れます
あるビーム内状態の次状態は直後のビームでなくてよいです
1 次元でなくてよいです
ビームサーチ以外の嘘 DP との併用や換装ができます
DP の知見が流用できます

例えば以下のような 2 次元の DP をビームサーチ化するとしたら、ビームはタテにもナナメにも切れます（切った後も DAG になっています）。逆にヨコにはループができるので切れません。¹

f:id:hakomof:20181205212430p:plain

f:id:hakomof:20181205212441p:plain

f:id:hakomof:20181205212503p:plain

ビームをどう切るかで性能が大きく変わるのは想像にたやすいでしょう。肝心のビームをどう切ればよいかですが、パラメータが違う状態同士の優劣判断が一番難しいパラメータで切るのが良さそうに思います。なぜなら、各ビームにはそのパラメータが同じ状態しか含まれないので、そのパラメータを評価関数に含めなくてよくなるからです。例えば、ゲーム AI などで 5 ターン目と 100 ターン目の比較は難しいからビームをターンで切るといったかんじです。

おわりに

近年マラソンをする人が増えうれしい限りで、焼きなまし / ビームサーチを覚えたい / 覚えたといったツイートをよく見かけるようになりました。しかし、インターネット上の情報は少なく例も単純です。そこで、実際のビームサーチ（や焼きなまし）が単純な例よりもはるかに柔軟でそれ自体に工夫の余地が多いことを少しでも感じてもらえたらなと思い本記事を書きました。もちろん、それ以前のどんな方針を立てるかがマラソンで一番おもしろいとは思います。ですが、ビームを撃つとか焼くとか決めた上でそれ自体を改造するのも十分おもしろいので楽しんで欲しいなと思います。

切れないことはない↩