ビームサーチの説明

この記事はCompetitive Programming Advent Calendar 2014の25日の記事です。

ビームサーチを全く知らない人向けにビームサーチについて簡単に説明します。

まず貪欲法をイメージし、それからビームサーチについて説明します。 貪欲法は下記のような疑似コードのような形で実装します。 (この擬似コードは過去に行われたMMの問題のSquareRemoverのようなゲームをイメージしています。) extractNextStates(s) は状態sから遷移可能な状態を返す関数だと思ってください。

State curState;
curStateを初期化
for(int i = 0; i < MAX_TURN; i++) {
    // 最終ターンに到達するまで、毎ターン最善の状態を選んでいきます。
    State bestState;
    for(State &state : extractNextStates(curState)) {
        if(state.score > bestState.score) {
            bestState = state;
        }
    }
    curState = bestState;
}

貪欲法なので常に最善の状態を選ぶだけ、非常に単純です。 グラフにすると下のようなイメージです。(バツは選ばれなかった状態)

では、何の工夫もないビームサーチの疑似コードを書きましょう。

const int BEAM_WIDTH = XXXXX;
vector<State> curStates;
curStates.push_back(初期の状態);
for(int i = 0; i < MAX_TURN; i++) {
    vector<State> nextStates;
    for(State &s : curStates) {
        for(State &state : extractNextStates(s)) {
            nextStates.push_back(state);
        }
    }
    // ↓の評価値が降順になるようにソート。
    sort(nextStates.begin(), nextStates.end());
    nextStates.resize(BEAM_WIDTH);
    curStates = nextStates;
}

貪欲法とあまり変わらないですね(、と書きたかったけど割と違いますね)。 下記の図はビーム幅2のときのグラフのイメージです。

ビームサーチは各ターンごとにビーム幅の分だけ上位の状態を選び、展開していきます。 ビーム幅が1ならば、常に最善の状態を選んでいきます。つまり、貪欲法と同じ動きになります。 また、貪欲法を改造して毎ターン上位n個の状態を保持していくようにすればビーム幅nのビームサーチを同じような動作になります。

以上です、まとまりのない記事になってしまいました。 なんとなくでもビームサーチのイメージができれば幸いです。できなかったらごめんなさい。 念のため書きますが、上記のコードはあくまで一例です。

ちなみにSquareRemoverは問題文はここから見ることができ、 standings から本番で提出されたソースコードを見られます。 上位陣がどんなことをしているのか知りたい方は見てみるとよいと思います。