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 tasks to processors in the
Processor Scheduling Problem). A complete solution is a partial solution that
satisfies some property (e.g., visits every square exactly once or assigns
every task to some processor).
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. For the initial
// call, S is the empty sequence of moves and the values 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 when the valuation function value() cannot
// decrease if a move is added to a partial solution. S is a partial solution;
// SBESTSOFAR is the best complete solution found previously; VBESTSOFAR =
// value(SBESTSOFAR); and LOWERBOUND is a lower bound on the minimum value.
// Returns with SBEST = SBESTSOFAR or the best complete solution that extends
// S, whichever has the smaller valuation; and VBEST = value(SBEST). For the
// initial call S is the empty sequence of moves; and VBESTSOFAR may be an
// upper bound on the minimum value, in which case SBESTSOFAR can be 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/27/16