分枝限定法とは（全体像）
分枝限定法は、「いちばんよい答え」を確実に見つけるための探索のやり方。英語の頭文字からB&Bとも呼ばれる。
考え方の土台はバックトラック（候補を試して、ダメなら戻る）。これに「見積もり」を足したのが分枝限定法だ。
ポイントは、各枝について「この先どんなにがんばっても、この程度より良くはならない」という上限・下限を見積もること。すでに見つけた答えより良くなりようがないと分かれば、その枝は調べるだけムダなので、早めに刈ってしまう。これで探索量を減らしつつ、最適解を取りこぼさない。
身近な例が最安の旅行プラン探し。「この経路は途中までで、もう最安記録を超えてしまう」と分かれば、その先は調べない。これが分枝限定法のイメージだ。
詳しく：手順とバックトラックとの違いだけ覚えれば戦える
ここが記事の心臓部。分枝限定法は、次の流れで最適解を探す。
分枝限定法の流れ
| ステップ | やること |
|---|---|
| 分枝 | 問題を部分問題に分けて、木のように枝分かれさせる |
| 限定（見積もり） | 各枝の上限・下限を見積もる |
| 枝刈り | 今の最良解より良くなりえない枝は切る |
| 確定 | 残った枝を調べ尽くして最適解を決める |
いちばんの違いは、よく似たバックトラックとの関係。バックトラックは「解があるか・全部の解」を探すのに対し、分枝限定法は「いちばんよい解」を見積もりを使って確実に求める。
バックトラックとの違い
| バックトラック | 分枝限定法 | |
|---|---|---|
| 目的 | 解の有無・全部の解 | 最適解（いちばんよい解） |
| 見積もり（上下限） | 使わない | 使って枝を刈る |
| 代表問題 | 数独・8クイーン | 巡回セールスマン・ナップサック |
つまり、分枝限定法は「バックトラックに見積もりを足して、最適解を効率よく探す」手法。答えにくい難問（TSPやナップサックなど）でも、実用的な速さで最適解を出せるのが強みだ。ただし、最悪の場合は時間が大きくふくらむこともある、というわけだね。
わかりやすく言い換えると
要するに、分枝限定法は「見積もって、ムダな枝を刈る」探索だ。
①分枝 … 問題を枝分かれさせて部分問題にする
②限定 … 各枝の上限・下限を見積もる
③枝刈り … 今より良くなりえない枝は切って、最適解だけ残す
バックトラックとの違いは「最適解を見積もりで確実に求める」点。ここを押さえると混ざらない。
試験のツボ
🔴 一番出る：上限・下限で枝を刈り最適解を保証
①各枝の上限・下限を見積もる
②今より良くなりえない枝は切る
🔴 次に出る：バックトラックとの違い
①バックトラックは解の有無・全部の解を探す
②分枝限定法は見積もりで最適解を求める
🟡 押さえると安定：応用と計算量
①巡回セールスマン・ナップサックに応用
②最悪では時間が大きくふくらむこともある
よくある間違い
①「分枝限定法とバックトラックはまったく同じもの」→ ✗ 分枝限定法は見積もり（上限・下限）を使う最適化の発展形。
②「分枝限定法は最適解を保証しない」→ ✗ 見積もりで枝を刈っても、最適解は取りこぼさない。
③「分枝限定法はいつも一瞬で解ける」→ ✗ 最悪では時間が大きくふくらむ。実用的には速いが万能ではない。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（分枝限定法の考え方）
分枝限定法の考え方に関する次の記述のうち、正しいものはどれか。
- 上限や下限はいっさい見積もらず、すべての枝を最後まで調べ尽くすだけの手法だ
- 各枝の上限・下限を見積もり、今より良くなりえない枝を刈って最適解を求めるものだ
- 最適解を求めることはできず、近い答えを一つ返すだけで終わってしまう手法とされる
- 枝分かれをいっさい使わず、はじめから答えだけを直接書き出せる手法のことである
解答は 2 だよ。
分枝限定法は各枝の上限・下限を見積もり、今より良くなりえない枝を刈って最適解を求めるんだ。ムダな枝を切るから速いんだよ。
選択肢1の「見積もらない」、選択肢3の「最適解を求められない」、選択肢4の「枝分かれを使わない」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 上限・下限を見積もる |
| 2 | ✓ | 見積もりで枝を刈り最適解を求める |
| 3 | ✗ | 最適解を保証する |
| 4 | ✗ | 枝分かれを使う |
オリジナル問題2（バックトラックとの違い）
分枝限定法とバックトラックの違いに関する次の記述のうち、正しいものはどれか。
- バックトラックは解の有無や全部の解を、分枝限定法は見積もりで最適解を求める
- バックトラックは最適解、分枝限定法は解の有無を求めるという、逆の関係である
- どちらも上限・下限を必ず使う点で同じで、両者にはなんの違いも存在していない
- 分枝限定法は上限・下限をいっさい使わず、バックトラックだけが見積もりを使う
解答は 1 だよ。
バックトラックは解の有無や全部の解を探し、分枝限定法は見積もり（上限・下限）で最適解を求めるんだ。見積もりを使うのが分枝限定法だよ。
選択肢2は目的が逆。選択肢3の「違いがない」、選択肢4の「分枝限定法は見積もりを使わない」はどちらも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | バックトラック＝解探索・分枝限定＝最適解 |
| 2 | ✗ | 目的が逆 |
| 3 | ✗ | 見積もりの有無で違う |
| 4 | ✗ | 見積もりを使うのは分枝限定法 |
オリジナル問題3（応用と計算量）
分枝限定法の応用や計算量に関する次の記述のうち、正しいものはどれか。
- 分枝限定法はどんな問題でも必ず一瞬で解け、時間がふくらむことはありえない
- 分枝限定法は数独や8クイーンのような、解の有無を調べる問題だけに使われる
- 分枝限定法は巡回セールスマンやナップサックに応用でき、最悪は時間がふくらむ
- 分枝限定法は最適解を求められないので、実際の問題ではいっさい使われていない
解答は 3 だよ。
分枝限定法は巡回セールスマンやナップサックなどに応用できるんだ。実用的には速いけど、最悪では時間が大きくふくらむこともあるよ。
選択肢1の「必ず一瞬」、選択肢2の「数独・8クイーンだけ」、選択肢4の「使われていない」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 最悪では時間がふくらむ |
| 2 | ✗ | それはバックトラックの代表例 |
| 3 | ✓ | TSP・ナップサックに応用 |
| 4 | ✗ | 最適解を求める実用解法 |
まとめ
押さえどころ
- 🔴 考え方 ＝ 上限・下限を見積もり、今より良くなりえない枝を刈って最適解を求める。
- 🔴 バックトラックとの違い ＝ バックトラックは解の有無・全部の解、分枝限定法は見積もりで最適解。
- 🟡 応用と計算量 ＝ TSP・ナップサックに応用。実用的には速いが最悪では時間がふくらむ。
次に学ぶ
- バックトラック ── 分枝限定法の土台。「進む→ダメなら戻る」に見積もりを足したのが分枝限定法。
- 貪欲法 ── 目の前の最善を選び続ける手法。最適とは限らない点が、最適解を保証する分枝限定法との違い。
執筆: SikakuQuest編集部