DH_FFP AND RANK_FFP: SOLVING CONSTRAINT SATISFACTION PROBLEMS VIA ORDERING THE DOMAIN VALUES
Fail First Principle (FFP) is a general heuristic algorithm (for solving constraint satisfaction problems) considering the order of variables. However, FFP neglects the order of values in domains. In this paper, we describe two algorithms,DH_FFP and Rank_FFP based on FFP. DH_FFP partitions a domain recursively with the middle value after choosing the variable that has the smallest domain. Rank_FFP makes use of the heuristic information between variables and constraints,evaluating and ranking every partition of a domain. We implemented these two algorithms and embedded into the constraint solving platform Ming Yue SOLVER 1.0 designed by us. The experimental results show that both DH_FFP and Rank_FFP enhance FFP to much extent on both solving efficiency and size.
JI-GUI SUN TIAN LIANG QING-YUN YANG MING-HAO YIN
College of Computer Science and Technology, Jilin University, Changchun, China, 130012;Key Laborator College of Computer Science and Technology, Jilin University, Changchun, China, 130012;Key Laborator
国际会议
2006 International Conference on Machine Learning and Cybernetics(IEEE第五届机器学习与控制论坛)
大连
英文
101-106
2006-08-13（万方平台首次上网日期，不代表论文的发表时间）