バックトラック

バックトラック(バックトラッキング、BackTracking)はPrologでのインタプリタで解を探すときのプロセスのこと.そもそもは効率的なしらみつぶし探索のことを指す.Prologにおけるこの処理過程は非決定性を備え複数の解がありうる場合もそのうちの一つ満たすものを返すように探索を行い、もしそれで条件が満たせない場合は次の解候補で探索を再度行う.

バックトラックでは、 入力として与えられるクエリに対して、 与えられている述語(clause)(factとrule)を元にその解を探索して求める. 解を暫定に決めて探索を続けるときにその解はchoice pointとして保持される. バックトラックの流れの例(Prolog) 以下の述語が宣言されているとする. 事実(fact) ・rainy("東京") ・rainy("北海道") ・cold("北海道") 規則(rule) ・snowy(X) :- rainy(X), cold(X) この状況で クエリ snowy(A) が与えられた時を考える. 1. snowy(A)はfactとruleのうちruleに該当するものがあるので、 rainy(A)に該当するものがあるかを検討します. 2. 次にrainy(A)に当てはまるものを上から順に探索をすると、rainy("東京")がヒットします. これをChoice PointとしてA = "東京"として残りの探索を続けます. 3. snowy(A)はrainy(A)とcold(A)の両方を満たす必要があるため、cold("東京")が事実としてあるかを探索します.ところがそのような事実はありません.そのためChoice Pointとして選んだA="東京"は破棄します. 4. そこで一つ前のrainy(A)に戻り、"東京"の次に候補となる解を探します.すると"北海道"が見つかります.これを次のChoice Pointとして解と暫定におきます. 5. そして再度cold(A)の解を探します.そこで事実にcold("北海道")が見つかります.すなわちこのA="北海道"はrainyとcoldの両方の条件を満たす解になっています. 6. A="北海道"は二つの条件を満たすためsnow("北海道")も正しいとわかります. 上記よりバックトラッキングによって ?- Snowy(A) A = 北海道 となります.

もし仮に他の事実として ・rainy("東京") ・rainy("北海道") ・cold("北海道") ・rainy("青森") ・cold("青森") のように青森も解にあった場合には、事実として宣言されている上から探索が行われますので、青森にたどり着くことなく探索は終了します. 次の候補を要求されるかさらに別の条件において"北海道"が解にならないときに限り"青森"が候補になります. バックトラッキングでは大量の解集合を持っているときにも、上記のように一つのみを返す非決定性を持つことで対処しています.