Backtracking

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:
Post a Comment

Labels

Java (159) Lucene-Solr (112) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (38) Eclipse (33) Code Example (31) Linux (25) JavaScript (23) Spring (22) Windows (22) Web Development (20) Tools (19) Nutch2 (18) Bugs (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) Troubleshooting (13) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) Problem Solving (9) UIMA (9) html (9) Http Client (8) Maven (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) Shell (7) ANT (6) Coding Skills (6) Database (6) Lesson Learned (6) Programmer Skills (6) Scala (6) Tips (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) System Design (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Spark (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Python (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts