アルゴリズムとデータ構造 補足資料 10-4
「バックトラックアルゴリズム」
横浜国立大学 理工学部 数物・電子情報系学科 富井尚志
バックトラックアルゴリズム
（まとめ）
• とりあえずやってみる
• ダメなら戻って別の道を探る
– あのとき別の道を選んでいたら、、、
• 試行錯誤（ trial and error ）
– 結局全部のケースをやってみる（完全解）
– その中で最適な解を選ぶ
（最適解を覚えておく）
バックトラックアルゴリズム
（まとめ）
try( ) {
候補選択の初期化
; do{次の候補の選択
;if (
仮の解として適する
) {解の一部として記録
;if (
まだ解くべき問題が残っている
) {try(
次の段階
); /*再帰呼出
*/if (
失敗
)先の記録を破棄
;} }
} while (
解がみつからない
||次の候補がある
)}
バックトラックアルゴリズム
（まとめ）
try()
A B … K
try()
A B … K
試行 バックトラック
try()
A B … K
try()
A B … K
「左側」の候補から、
「深いほう」に順に、
試行する。
ダメな場合には、
試行を破棄して
次の候補を試行する。
すべてダメな場合には、
1
