Title :
Minimal forward checking
Author :
Dent, M.J. ; Mercer, R.E.
Author_Institution :
Dept. of Comput. Sci., Univ. of Western Ontario, London, Ont., Canada
Abstract :
Forward Checking (FC) is a highly regarded complete search algorithm used to solve constraint satisfaction problems. In this paper a lazy variant of FC called minimal forward checking (MFC) is introduced. MFC is a natural marriage of incremental FC and backchecking. Given a variable selection heuristic which does not depend on domain size MPC´s worst case performance on any CSP instance is the number of constraint checks performed by FC. Experiments using hard random problems are presented which show that MFC outperforms FC especially for problems with large domain sizes and/or a large number of variables
Keywords :
constraint handling; search problems; backchecking; constraint satisfaction; hard random problems; minimal forward checking; search algorithm; variable selection heuristic; worst case performance; Algorithm design and analysis; Artificial intelligence; Computer science; Costs; Filters; Input variables; Performance analysis; Table lookup;
Conference_Titel :
Tools with Artificial Intelligence, 1994. Proceedings., Sixth International Conference on
Conference_Location :
New Orleans, LA
Print_ISBN :
0-8186-6785-0
DOI :
10.1109/TAI.1994.346460