DocumentCode :
2302582
Title :
Minimal forward checking
Author :
Dent, M.J. ; Mercer, R.E.
Author_Institution :
Dept. of Comput. Sci., Univ. of Western Ontario, London, Ont., Canada
fYear :
1994
fDate :
6-9 Nov 1994
Firstpage :
432
Lastpage :
438
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Tools with Artificial Intelligence, 1994. Proceedings., Sixth International Conference on
Conference_Location :
New Orleans, LA
Print_ISBN :
0-8186-6785-0
Type :
conf
DOI :
10.1109/TAI.1994.346460
Filename :
346460
Link To Document :
بازگشت