JSW 2016 Vol.11(9): 903-911 ISSN: 1796-217X
doi: 10.17706/jsw.11.9.903-911
doi: 10.17706/jsw.11.9.903-911
Guiding Search by Singleton-Domain Variables for Constraint Satisfaction Problem
Yi Jun Liu*
Jilin University ,Changchun, Jilin Province, China.
Abstract—Heuristic is an important subject in the field of constraint satisfaction problem(CSP). In the study, we found a kind of variables named singleton-domain variables have a great influence on the solution process. Based on this, we propose a heuristic method named dom/wsdeg and the corresponding calculating method and combine the method with a constraint network compression technology proposed in this paper. The results have shown that the new heuristics are more efficient than the classical heuristics.
Index Terms—Constraint satisfaction problem, compression method, singleton-domain variable, variable ordering heuristic.
Abstract—Heuristic is an important subject in the field of constraint satisfaction problem(CSP). In the study, we found a kind of variables named singleton-domain variables have a great influence on the solution process. Based on this, we propose a heuristic method named dom/wsdeg and the corresponding calculating method and combine the method with a constraint network compression technology proposed in this paper. The results have shown that the new heuristics are more efficient than the classical heuristics.
Index Terms—Constraint satisfaction problem, compression method, singleton-domain variable, variable ordering heuristic.
Cite: Yi Jun Liu, "Guiding Search by Singleton-Domain Variables for Constraint Satisfaction Problem," Journal of Software vol. 11, no. 9, pp. 903-911, 2016.
General Information
ISSN: 1796-217X (Online)
Frequency: Quarterly
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, CNKI, Google Scholar, ProQuest, INSPEC(IET), ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsweditorialoffice@gmail.com
-
Mar 01, 2024 News!
Vol 19, No 1 has been published with online version [Click]
-
Jan 04, 2024 News!
JSW will adopt Article-by-Article Work Flow
-
Apr 01, 2024 News!
Vol 14, No 4- Vol 14, No 12 has been indexed by IET-(Inspec) [Click]
-
Apr 01, 2024 News!
Papers published in JSW Vol 18, No 1- Vol 18, No 6 have been indexed by DBLP [Click]
-
Nov 02, 2023 News!
Vol 18, No 4 has been published with online version [Click]