Local Search and Backtracking vs. Non-Systematic Backtracking

Steven Prestwich

This paper addresses the following question: what is the essential difference between stochastic local search (LS) and systematic backtracking (BT) that gives LS superior sealability? One possibility is LS’s lack of firm commitment to any variable assignment. Three BT algorithms are modified 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 sometimes gives better results. It is argued that randomised backtracking is a form of local search.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.