College of Computer Science and Technology, Jilin University, Changchun 130012, China;Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China 在期刊界中查找 在百度中查找 在本站中查找
College of Computer Science and Technology, Jilin University, Changchun 130012, China;Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China 在期刊界中查找 在百度中查找 在本站中查找
Constraint satisfaction problems have been widely investigated in artificial intelligence area. This paper investigates whether the coarse-grained maintaining arc is consistent, which is used to solve CSPs. The study has found that during the search for a solution, there are ineffective revisions, which revise the arcs that point to assigned variables. This study has proved that such revisions are redundant and proposed a method to avoid such redundant revisions. The paper gives the improved basic frame for the coarse-grained arc consistency algorithms, named AC3_frame_ARR. The new frame can be applied to improve all the coarse-grained AC algorithms. The experimental results show that the improved algorithms can save at most 80% revisions and 40% CPU time.
[6] Debruyne R, Bessière C. Some practicable filtering techniques for the constraint satisfaction problem. In: Pollack ME, ed. Proc. ofthe IJCAI’97. Morgan Kaufmann Publishers, 1997. 412-417. http://www.emn.fr/z-info/rdebruyn/ijcai97.pdf
[7] Bessière C, Cardon S, Debruyne R, Lecoutre C. Efficient algorithms for singleton arc consistency. Constraints, 2011,16(1):25-53.[doi: 10.1007/s10601-009-9080-5]
[8] Freuder EC. A sufficient condition for backtrack-free search. Journal of ACM, 1982,29(1):24-32. [doi: 10.1145/322290.322292]
[9] Bessière C. Arc-Consistency and arc-consistency again. Artificial Intelligence, 1994,65(1):179-190. [doi: 10.1016/0004-3702(94)90041-8]
[11] Lecoutre C, Hemery F. A study of residual supports in arc consistency. In: Veloso MM, ed. Proc. of the IJCAI 2007. AAAI Press,2007. 125-130. https://www.aaai.org/Papers/IJCAI/2007/IJCAI07-018.pdf
[12] Sabin D, Freuder EC. Contradicting conventional wisdom in constraint satisfaction. In: Cohn AG, ed. Proc. of the 11th EuropeanConf. on Artificial Intelligence. Amsterdam: John Wiley & Sons, 1994. 125-129.
[13] Bessière C, Freuder EC, Régin JC. Using constraint metaknowledge to reduce arc consistency computation. Artificial Intelligence,1999,107(1):125-148. [doi: 10.1016/S0004-3702(98)00105-2]
[14] Lecoutre C, Boussemart F, Hemery F. Exploiting multidirectionality in coarse-grained arc consistency algorithms. In: Francesca R,ed. Proc. of the CP 2003. Springer-Verlag, 2003. 480-494. http://www.cril.univ-artois.fr/~lecoutre/research/publications/2003/CP2003.pdf
[15] Mehta D, van Dongen MRC. Reducing checks and revisions in coarse-grained MAC algorithms. In: Kaelbling LP, ed. Proc. of theIJCAI 2005. Professional Book Center, 2005. 236-241. http://ijcai.org/papers/0820.pdf
[16] Wallace RJ, Freuder EC. Ordering heuristics for arc consistency algorithms. In: Proc. of the 9th Canadian Conf. on ArtificialIntelligence. Vancouver, 1992. 163-169. http://4c.ucc.ie/web/upload/publications/misc/wallace92ordering.pdf
[17] van Dongen MRC. Saving support checks does not always save time. Artificial Intelligence Review, 2004,21(3-4):317-334. [doi:10.1023/B:AIRE.0000007389.67810.17]
[18] Li ZS, Li HB, Zhang YG, Wang ZW. An approach of solving constraint satisfaction problem based on cycle-cut. Chinese Journal ofComputers, 2011,34(8):1528-1535 (in Chinese with English abstract). [doi: 10.3724/SP.J.1016.2011.01528]
[19] Boussemart F, Hemery F, Lecoutre C, Sais L. Boosting systematic search by weighting constraints. In: Saitta L, ed. Proc. of the16th European Conf. on Artificial Intelligence. IOS Press, 2004. 146-150. http://www.cril.univ-artois.fr/~lecoutre/research/publications/2004/ECAI2004.pdf
[20] Smith BM, Dyer ME. Locating the phase transition in binary constraint satisfaction problems. Artificial Intelligence, 1996,81(1):155-181. [doi: 10.1016/0004-3702(95)00052-6]
[21] Xu K, Li W. Exact phase transitions in random constraint satisfaction problems. Journal of Artificial Intelligence Research,2000,12(3-4):93-103.