Backtracking

Backtracking paradigm. -> Finding all solution

Backtracking works for decision solution, which means find the solution of hard problem.

Algorithm:

• Traverse through all the "search paths" to locate "solutions" or "dead ends".

Algorithm Backtrack(x):
Input: A problem instance x for a hard problem
Output: A solution for x or “no solution” if none exists

F ← {(x, ∅)}. //F is the “frontier” set of subproblem configurations
while F = ∅ do
  Select from F the most “promising” configuration (x, y).
  Expand (x, y) by making a small set of additional choices.
  Let (x1, y1), (x2, y2), . . ., (xk, yk) be the set of new configurations.

for each new configuration (xi, yi) do
  Perform a simple consistency check on (xi, yi).

if the check returns “solution found” then
  return the solution derived from (xi, yi)

if the check returns “dead end” then
  Discard the configuration (xi, yi). // Backtrack
else
  F ← F ∪ {(xi, yi)} // (xi, yi) starts a promising search path
  return “no solution”

Iterate through elements of search space. ・When there are several possible choices, make one choice and recur. ・If the choice is a dead end, backtrack to previous choice, and make next available choice.

Benefit:

Identifying dead ends allows us to prune the search tree. Ex. [backtracking for N-queens problem] ・Dead end: a diagonal conflict. ・Pruning: backtrack and try next column when diagonal conflict found.

Applications. Puzzles, combinatorial optimization, parsing ...