Backtracking

From Progteam

Revision as of 02:51, 22 February 2008 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Backtracking, according to Skiena, is another word for a brute force approach to a problem. While "brute force" sounds inelegant, there is still much room for creativity in:

  1. Modeling: How do you model a real life situation as a mathematical search space and evaluation function?
  2. Pruning: How do you identify certain cases as irrelevant, and don't need to be searched?
  3. Caching: How do you avoid unnecessary recomputing? This is very much related to dynamic programming.
  4. Ordering: How can you navigate the search space such that you search in places that you're more likely to find the answer first?

Backtracking problems almost always involve optimizing some function, or finding out whether an object has a certain property.

Personal tools