Algorithm Series 2
Backtracking
What is Backtracking?
Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, which incrementally builds candidates to the solutions, and abandons each partial candidate ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.
1. Define a systematic generation order to avoid both repetitions and missing.
2. Viewing backtracking as a depth-first search on an implicit graph.
How?
At each step in the backtracking algorithm, we try to extend a given partial solution a=(a1,a2, ..., ak) by adding another element at the end. After extending it, we must test whether what we now have is a solution: if so, we should print it or count it. If not, we must check whether the partial solution is still potentially extendible to some complete solution.
If all has been tried and nothing worked, return false to trigger backtracking.
Backtracking procedures are characterized by multiple recursive calls, typically within a loop.
backtrack(int a[], int k, data input)
{
int c[MAXCANDIDATES]; /* candidates for next position */
if (is_a_solution(a,k,input))
process_solution(a,k,input);
else {
k = k+1;
construct_candidates(a,k,input,c);
for (i=0; i<ncandidates; i++) {
a[k] = c[i];
make_move(a,k,input);
backtrack(a,k,input);
unmake_move(a,k,input);
}
}
}
Search Pruning
Pruning is the technique of cutting of the search the instant we have established that a partial solution cannot be extended into a full solution.
Cutting paths that are known (doomed) to be dead-ends as early as possible.
When to use backtracking?
Backtracking is used to solve problems for which a sequence of objects is to be selected from a set such that the sequence satisfies some constraint.
Examples
Puzzle of N Queens
public void PlaceQueen(int row){
if (row == 8) {
printBoard();
return;
}
for (int i = 0; i < 8; i++) {
columnForRow[row]=i;
if(isConsistent(row)){
PlaceQueen(row+1);
}
}
}
Solving a maze
Maze Generation and solver
Sudoku Solver
Generating Permutations - O(n!)
Random permutation, Partial Permutation [TODO]
Generating Subsets - O(2^n)
Solution:
Generating all subsets then really just comes down to generating all binary numbers (that is, all integers).
Random Subset, Partial Subset[Same solution as above]
Generating Partitions
Generate (1) all, or (2) a random, or (3) the next integer or set partitions of length n.
Integer Partitions [TODO]
Set partitions [TODO]
To permute set S, we can select the frst character, A1, permute the remainder of the string to get a new list then, with that new list, we can "push" A1 into each possible position
Constructing All Paths in a Graph
Constructing all paths between two vertices
Other Examples
Find how many pairs in the given array sum to a given number
Find the number of trailing zeroes in the factorial of a given number.
Resources:
