Algorithms for Backtracking
~~~~~~~~~~~~~~~~~~~~~~~~~~~
A PARTIAL SOLUTION is a possibly empty sequence of moves (e.g., knight's moves
in the Knight's Path Problem or assignments of items to bins in the Bin-Packing
Problem). A COMPLETE SOLUTION is a partial solution that satisfies some
additional property (e.g., visits every square exactly once or assigns every
item to some bin).
Backtracking to Find Some Solution
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Try to extend the partial solution S to a complete solution. If successful,
// return with STATUS = SUCCESS and COMPLETE = the complete solution found;
// otherwise return with STATUS = FAILURE and COMPLETE = S. On the initial
// call, S is the EMPTY sequence of moves and the values of STATUS and COMPLETE
// returned include a complete solution or an indication that there is none.
[status, complete] = backtrack (S)
if S is a complete solution
return [SUCCESS, S]
Generate a list L of possible next moves
Apply heuristics to prune L by eliminating moves that cannot lead to a
complete solution
Apply heuristics to sort L to increase the likelihood of early success
For each possible next move M in L (in sorted order)
Add M to S giving the augmented partial solution S'
[status, complete] = backtrack (S')
If status == SUCCESS
Return [SUCCESS, complete]
Return [FAILURE, S]
Backtracking to Find a Minimal Solution
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Find a minimal complete solution assuming the VALUATION FUNCTION VALUE()
// does not decrease when a move is added to a partial solution. S is a
// partial solution; SBESTSOFAR is the best complete solution found earlier;
// VBESTSOFAR = VALUE(SBESTSOFAR); and LOWERBOUND is some lower bound on the
// minimum value. Returns with SBEST = SBESTSOFAR or a best complete solution
// that extends S, whichever has a smaller valuation; and VBEST = VALUE(SBEST).
// On the initial call, S is the EMPTY sequence of moves; VBESTSOFAR is some
// UPPER BOUND on the minimum value; and SBESTSOFAR is anything.
[vBest, sBest] = backtrack (S, vBestSoFar, sBestSoFar, lowerBound)
if S is a complete solution
if value(S) < vBestSoFar
return [value(S), S]
else
return [vBestSoFar, sBestSoFar]
Generate a list L of possible next moves
Apply heuristics to prune L by eliminating moves that cannot lead to a
better solution than sBestSoFar
Apply heuristics to sort L to increase the likelihood of early success
For each possible next move M in L (in sorted order)
Add M to S giving the augmented partial solution S'
if value(S') < vBestSoFar
[vBestSoFar, sBestSoFar] = backtrack (S', vBestSoFar, sBestSoFar)
if vBestSoFar == lowerBound
return [vBestSoFar, sBestSoFar]
Return [vBestSoFar, sBestSoFar]
CS-223-01/23/20