DOC PREVIEW
Princeton COS 226 - Combinatorial Search

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Princeton COS 226 - Combinatorial Search

Documents in this Course
QUICKSORT

QUICKSORT

14 pages

QUICKSORT

QUICKSORT

55 pages

STRINGS

STRINGS

69 pages

Lecture

Lecture

4 pages

STRINGS

STRINGS

18 pages

Hashing

Hashing

7 pages

MERGESORT

MERGESORT

14 pages

Quicksort

Quicksort

12 pages

Strings

Strings

10 pages

Overview

Overview

15 pages

Hashing

Hashing

13 pages

Mergesort

Mergesort

15 pages

Tries

Tries

13 pages

Final

Final

12 pages

Final

Final

12 pages

Mergesort

Mergesort

13 pages

Final

Final

10 pages

Load more
Download Combinatorial Search
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Combinatorial Search and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Combinatorial Search 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?