Technical reports

Reducing thrashing by adaptive backtracking

D.A. Wolfram

August 1987, 15 pages

DOI: 10.48456/tr-112

Abstract

Adaptive backtracking dynamically reduces thrashing caused by blind backtracking and recurring failures, by locating early backtrack points and deleting choices which are not part of any solution. Search problems with hereditary bounding properties are soluble by this method. These problems include searches in theorem proving, logic programming, reason maintenance, and planning. The location of a backtrack point uses a particular minimal inconsistent subset, which is called the cause set. A rejection set is computed from the union of cause sets and rejection sets at a failure are used to locate subsequent backtrack points. A choice is deleted when a rejection set is a singleton. The worst case overhead is O(nf(n)) in time if the bounding property can be tested in O(f(n)) time, and O(n²) in space. An implementation confirms the expected exponential speed-ups for problems whose solution involves much thrashing.

Full text

PDF (0.7 MB)

BibTeX record

@TechReport{UCAM-CL-TR-112,
  author =	 {Wolfram, D.A.},
  title = 	 {{Reducing thrashing by adaptive backtracking}},
  year = 	 1987,
  month = 	 aug,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-112.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-112},
  number = 	 {UCAM-CL-TR-112}
}