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