Local Search and Backtracking vs Non-Systematic Backtracking
Steven Prestwich · 2001
This paper addresses the following question: what is the es-sential difference between stochastic local search (LS) and systematic backtracking (BT) that gives LS superior seal-ability? One possibility is LS’s lack of firm commitment to any variable assignment. Three BT algorithms are mod-ified to have this feature by introducing randomness into the choice of backtracking variable: a forward checker for n-queens, the DSATUR graph colouring algorithm, and a Davis-Logemann-Loveland procedure for satisfiability. In each case the modified algorithm scales like LS and some-times gives better results. It is argued that randomised back-tracking is a form of local search.