Title: Local Search and Backtracking vs Non-Systematic Backtracking
Abstract: 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.
Publication Year: 2001
Publication Date: 2001-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 28
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot