Home Theory What is Backtracking?

What is Backtracking?

by nikoo28
0 comment

Backtracking is the method of exhaustive search using divide and conquer.

  • Sometimes the best algorithm for a problem is to try all the possibilities.
  • This is always slow, but there are standard tools that can be used for help.
  • Tools: algorithms for generating basic objects, such as binary strings [2n possibilities for n-bit string], permutations [n!], combinations [n!/r!(n-r)!], general strings [k-ary strings of length  n has kn possibilities], etc…
  • Backtracking speeds the exhaustive search by pruning.

Example Algorithms of Backtracking

  • Binary Strings: generating all binary strings
  • Generating k-ary Strings.
  • The knapsack problem
  • Generalized Strings
  • Hamiltonian Cycles
  • Graph coloring problem

Code Samples:

  1. Generate all the strings of n bits.
0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More