Day 147-Q2 | ビームサーチ（Beam Search）

問題

長さ $L$ の文字列を、アルファベット $C$ 種類（'a','b','c',...の先頭$C$文字）から1文字ずつ選んで構築する。位置$i$（0-indexed）で文字$c$を選んだスコアは $\text{score}[i][c]$。隣接文字は同一不可（$c_i\ne c_{i-1}$）。

ビームサーチ（ビーム幅$K$）で以下の手順を実行する。

位置0で全ての文字を試した候補を作る。
各位置で、保持中の候補それぞれに直前と異なる文字を1つ追加した候補を全生成。
候補全体をスコア降順、同点なら辞書順昇順でソートし上位$K$個だけ残す。
位置$L-1$まで処理し、最終ビームでスコア最大（同点なら辞書順最小）の候補を答えとする。

この手順はビームサーチそのものであり真の最適解を保証しない。手順通りに実装した結果を出力すればよい。

入力形式

L C K
score[0][0] ... score[0][C-1]
:
score[L-1][0] ... score[L-1][C-1]

制約

$1 \le L \le 12$

$2 \le C \le 6$

$1 \le K \le 8$

$0 \le \text{score}[i][c] \le 100$

入出力例

入力例1

出力例1

abca
16

概念図：ビーム幅K=2による枝刈り探索木

ヒント（段階的開示）

ヒント1（方向性）

全探索は各位置で最大$C-1$通りなので$O((C-1)^L)$で爆発する。各段階で「今のところ良さそうな候補」だけに絞り込めば計算量を抑えられるが、捨てた候補が真の最適解につながる可能性は排除できない。

ヒント2（アプローチ）

「現在のビーム（最大K個）」を保持し、位置ごとに「全候補を合法な次の文字で拡張→スコアでソート→上位K個だけ残す」を繰り返す。同点の扱い（タイブレーク）を固定しないと実装によって答えが変わる。

ヒント3（誘導）

def beam_search(L, C, K, score):
    chars = [chr(ord('a') + c) for c in range(C)]
    beam = [(score[0][c], chars[c]) for c in range(C)]
    beam.sort(key=lambda t: (-t[0], t[1]))
    beam = beam[:K]
    for i in range(1, L):
        candidates = []
        for total, s in beam:
            last = s[-1]
            for c in range(C):
                if chars[c] == last:
                    continue
                candidates.append((total + score[i][c], s + chars[c]))
        candidates.sort(key=lambda t: (-t[0], t[1]))
        beam = candidates[:K]
    return beam[0]

模範解答 (Python)

import sys

def beam_search(L, C, K, score):
    chars = [chr(ord('a') + c) for c in range(C)]

    beam = [(score[0][c], chars[c]) for c in range(C)]
    beam.sort(key=lambda t: (-t[0], t[1]))
    beam = beam[:K]

    for i in range(1, L):
        candidates = []
        for total, s in beam:
            last = s[-1]
            for c in range(C):
                if chars[c] == last:
                    continue
                candidates.append((total + score[i][c], s + chars[c]))
        candidates.sort(key=lambda t: (-t[0], t[1]))
        beam = candidates[:K]

    beam.sort(key=lambda t: (-t[0], t[1]))
    best_total, best_str = beam[0]
    return best_str, best_total


def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    L = int(data[idx]); idx += 1
    C = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    score = []
    for _ in range(L):
        row = [int(data[idx + c]) for c in range(C)]
        idx += C
        score.append(row)

    best_str, best_total = beam_search(L, C, K, score)
    print(best_str)
    print(best_total)


main()

Step-by-Step 解説

1初期ビームの構築
位置0はC種類すべてが候補。スコア降順・同点辞書順昇順でソートし上位K個。例では`a:3,c:2`が残る。

2各深さでの拡張と枝刈り
ビーム中の各候補に直前と異なる文字を追加、全候補をソートしK個に絞る。位置1では`ab:7,cb:6`が残る。

3探索を最後まで進める
ビームはK個に保たれたまま更新されるためメモリは$O(K\cdot L)$。全探索$O(C^L)$とは対照的。

4最終選択
最後のビームでスコア最大（同点辞書順最小）の候補を答えとする。ビームはソート済みなので先頭を取るだけ。

よくあるミス

ミス	原因	正しい書き方
タイブレーク規則を決めずに実装する	同点候補の生成順で結果が揺れる	`key=lambda t: (-t[0], t[1])`で第2キーを明示する
ビーム幅Kを超えて候補を保持し続ける	各深さでの`candidates[:K]`切り詰めを忘れる	拡張・ソートのたびに必ず先頭K個だけ残す
隣接禁止制約を最後にまとめて除こうとする	ビームサーチは途中で切り捨てる探索なので手遅れ	候補生成の時点で`chars[c]==last`をスキップする
ビームサーチの結果を最適解と誤解する	Kが小さいと真の最適解を見逃す近似であることを忘れる	最適値が必要ならDP・全探索と併用する
各候補のスコアを毎回再計算する	文字列全体を舐めると$O(L)$余分にかかる	直前の総スコアに今回のスコアを足す差分更新にする

次のステップ

発展: DPによる真の最適値を計算し、$K=1,2,4,8$での近似率（ビームサーチのスコア／真の最適値）の推移を実測せよ。
次回予告: Four Russians法（四露人法・LCSのブロック単位高速化）

自己評価

完全理解おおむね理解要復習

Day 147-Q2 — ビームサーチ（Beam Search・ビーム幅Kによる近似探索）

問題