【ばっくとらっきんぐ】
バックトラッキング とは？
最終更新:
💡 試す、行き詰まったら戻る、別の候補へ
候補を順に試し、成立しない選択から戻って別の候補を探す探索方法。部分解と枝刈り、状態を戻す理由、探索量の限界を解説します。
📌 このページのポイント
- 部分的な解を作りながら、選択肢を試す
- 解につながらないと分かった枝から戻る
- 状態を戻してから、別の候補を試す
- 枝を減らせても、探索が大きくなる問題はある
ひよこ バックトラッキングは、やり直すこと？
ペンギン先生 選択肢を試し、解につながらないと分かったら、その選択をした地点へ戻って別の候補を試す方法だよ。少しずつ解を作る探索で使うんだ。
ひよこ 全部作ってから、正しいか見るの？
ひよこ 気に入らない候補は、すぐ外してよい？
ペンギン先生 後で正しい解になる可能性があるなら、勝手には外せないよ。その部分解からは解を完成できない、と判断できる条件が必要なんだ。外し方を間違えると、正しい解を見落としてしまう。
ひよこ 戻るときは、何をするの？
ペンギン先生 直前に加えた選択や、それで変更した状態を元に戻す。それから別の候補を試すよ。以前の候補の値が残ると、別の枝の判定までおかしくなるんだ。
ひよこ 解が見つかったら終わり？
ペンギン先生 一つ見つかればよい問題では終われるけれど、全解を探すなら、解を記録して探索を続ける。再帰で書くこともあるよ。枝を減らせる場合があっても、候補が増えると探索量が大きくなることはあるんだ。
もっと詳しく知りたい人へ
深さ優先探索とどう関係する？
候補の選択を木として見ると、部分解から一つの枝を深く試し、戻って次の枝へ進む探索です。NISTも、可能な部分解の木に対する深さ優先探索として説明しています。
再帰を使わないと実装できない？
再帰は選択地点と戻り先を管理する便利な方法ですが、必須ではありません。スタックなどで候補や状態を管理する実装も考えられます。重要なのは、戻る地点と状態を正しく管理することです。
まとめ：ざっくりこれだけ覚えればOK！
「バックトラッキング」って出てきたら「候補を試し、行き詰まったら戻って別の候補を探す方法」と思えばだいたいOK！
📖 おまけ：英語の意味
「Backtracking」 ＝ 後戻りすること
💬 選択した地点へ戻り、別の選択肢を試す探索方法を表します。