Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2008·April 29, 2008 8:24:07 PMCombinatorial Search‣permutations‣backtracking‣counting‣subsets‣paths in a graph2OverviewExhaustive search. Iterate through all elements of a search space.Backtracking. Systematic method for examining feasible solutionsto a problem, by systematically eliminating infeasible solutions.Applicability. Huge range of problems (include NP-hard ones).Caveat. Search space is typically exponential in size ⇒effectiveness may be limited to relatively small instances.Caveat to the caveat. Backtracking may prune search space to reasonable size, even for relatively large instancesGoal. Process all 2N bit strings of length N.•Maintain a[i] where a[i] represents bit i.•Initialize all bits to zero.•Simple recursive method does the job. Remark. Equivalent to counting in binary from 0 to 2N - 1.3private void enumerate(int n){ if (n == N) { process(); return; } enumerate(n+1); a[n] = 1; enumerate(n+1); a[n] = 0;}clean upN = 4enumerate(0)Warmup: enumerate N-bit strings0 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 11 0 0 01 0 0 11 0 1 01 0 1 11 1 0 0 1 1 0 11 1 1 01 1 1 10 0 00 0 10 0 00 1 00 1 10 1 00 0 01 0 01 0 11 0 01 1 01 1 11 1 01 0 00 0 0N = 3enumerate(0)public class Counter{ private int N; // number of bits private int[] a; // bits (0 or 1) public Counter(int N) { this.N = N; a = new int[N]; enumerate(0); } private void process() { for (int i = 0; i < N; i++) StdOut.print(a[i]); StdOut.println(); } private void enumerate(int n) { if (n == N) { process(); return; } enumerate(n+1); a[n] = 1; enumerate(n+1); a[n] = 0; } }4Warmup: enumerate N-bit stringspublic static void main(String[] args){ int N = Integer.parseInt(args[0]); Counter counter = new Counter(N);}% java Counter 40000000100100011010001010110011110001001101010111100110111101111all programs in thislecture are variationson this theme5‣permutations‣backtracking‣counting‣subsets‣paths in a graph6N-rooks problemQ. How many ways are there to place N rooks on an N-by-N board so thatno rook can attack any other?Representation. No two rooks in the same row or column ⇒ permutation.Challenge. Enumerate all N! permutations of 0 to N-1.int[] a = { 1, 2, 0, 3, 6, 7, 4, 5 };01234567012345677Enumerating permutationsRecursive algorithm to enumerate all N! permutations of size N.•Start with permutation 0 to N-1.•For each value of i-swap i into position 0-enumerate all (N-1)! arrangements of a[1..N-1]-clean up (swap i and 0 back into position)3 1 2 03 1 0 23 2 1 03 2 0 13 0 2 13 0 1 21 0 2 31 0 3 21 2 0 31 2 3 01 3 2 01 3 0 21 3 2 01 0 2 30 1 2 32 1 0 32 1 3 02 0 1 32 0 3 12 3 0 12 3 1 03 followed byperms of 1 2 00 followed byperms of 1 2 31 followed byperms of 0 2 32 followed byperms of 1 0 30 1 20 2 11 0 21 2 02 1 02 0 10 11 00 1 2 30 1 3 20 2 1 30 2 3 10 3 2 10 3 1 2example showing cleanup swaps that bring perm back to originalRecursive algorithm to enumerate all N! permutations of size N.•Start with permutation 0 to N-1.•For each value of i-swap i into position 0-enumerate all (N-1)! arrangements of a[1..N-1]-clean up (swap i and 0 back into position)private void enumerate(int n){ if (n == N) { process(); return; } for (int i = n; i < N; i++) { exch(n, i); enumerate(n+1); exch(i, n); }}Enumerating permutations8clean up% java Rooks 40 1 2 3 0 1 3 2 0 2 1 3 0 2 3 1 0 3 2 1 0 3 1 2 1 0 2 3 1 0 3 2 1 2 0 3 1 2 3 0 1 3 2 0 1 3 0 2 2 1 0 3 2 1 3 0 2 0 1 3 2 0 3 1 2 3 0 1 2 3 1 0 3 1 2 0 3 1 0 2 3 2 1 0 3 2 0 1 3 0 2 1 3 0 1 2 1 followed byperms of 0 2 30 followed byperms of 1 2 32 followed byperms of 1 0 33 followed byperms of 1 2 0public class Rooks{ private int N; // number of bits private int[] a; // bits (0 or 1) public Rooks(int N) { this.N = N; a = new int[N]; for (int i = 0; i < N; i++) a[i] = i; enumerate(0); } private void enumerate(int n) { /* as before */ } private void enumerate(int n) { /* see previous slide */ } private void exch(int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } public static void main(String[] args) { int N = Integer.parseInt(args[0]); Rooks rooks = new Rooks(N); }}9Enumerating permutations% java Rooks 20 1 1 0 % java Rooks 30 1 2 0 2 1 1 0 2 1 2 0 2 1 0 2 0 1 104-rooks search treesolutions. . .Studying slow way to compute N! but good warmup for calculations.Hypothesis. Running time is about 2(N! / 8!) seconds.% java Rooks 7 | wc -l5040% java Rooks 8 | wc -l40320% java Rooks 9 | wc -l362880% java Rooks 10 | wc -l3628800% java Rooks 25 | wc -l...N-rooks problem: back-of-envelope running time estimate11instant1.6 seconds 15 seconds 170 secondsforever12‣permutations‣backtracking‣counting‣subsets‣paths in a graphQ. How many ways are there to place N queens on an N-by-N board so that no queen can attack any other?Representation. Solution is a permutation: a[i] = column of queen in row i.Additional constraint. No diagonal attack is possibleChallenge. Enumerate (or even count) the solutions.13N-queens problem0123456701234567int[] a = { 4, 6, 0, 2, 7, 5, 3, 1 };144-queens search treediagonal conflicton partial solution:no point going deepersolutions15Backtracking paradigm. Iterate through elements of search space.•When there are N 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 row when diagonal conflict found.N-queens problem: backtracking solution164-queens search tree (pruned)solutionsbacktrack ondiagonal conflictsprivate boolean backtrack(int n) { for (int i = 0; i < n; i++) { if ((a[i] - a[n]) == (n - i)) return true; if ((a[n] - a[i]) == (n - i)) return true; } return false; } private void enumerate(int n) { if (k == N) { process(); return; } for (int i = k; i < N; i++) { exch(n, i); if (!backtrack(n)) enumerate(n+1); exch(i, n); } }17N-queens problem: backtracking solutionstop enumerating if adding the nthqueen leads to a diagonal violation% java Queens 41 3 0 22 0 3 1% java Queens 50 2 4 1 3 0 3 1
View Full Document