改进求解约束满足问题粗粒度弧相容算法
作者:
基金项目:

国家自然科学基金(60773097, 60873148, 60973089); 吉林省自然科学基金(201101039, 20071106, 20080107); 国家教育部博士点专项基金(20100061110031)


Improving Coarse-Grained Arc Consistency Algorithms in Solving Constraint Satisfaction Problems
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [21]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    约束满足问题在人工智能领域有着广泛的应用.研究了约束满足问题的粗粒度维持弧相容求解算法,发现在求解过程中,对于指向已赋值变量的弧存在无效的修正检查,证明了这类修正检查是冗余的.提出一种方法避免这类冗余的修正检查,给出改进后的粗粒度弧相容算法的基本框架AC3_frame_ARR,该改进框架可用于改进所有粗粒度弧相容算法.实验结果表明,经过AC3_frame_ARR 改进后的算法最多可以节省80%的修正检查次数和40%的求解耗时.

    Abstract:

    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.

    参考文献
    [1] Freuder EC, Mackworth AK. Constraint satisfaction: An emerging paradigm. Rossi F, van Beek P, Walsh T, eds. Handbook ofConstraint Programming. Amsterdam: Elservier, 2006. 13-27. [doi: 10.1016/S1574-6526(06)80006-4]
    [2] van Beek P. Backtracking search algorithms. In: Rossi F, van Beek P, Walsh T, eds. Handbook of Constraint Programming.Amsterdam: Elservier, 2006. 85-134. [doi: 10.1016/S1574-6526(06)80008-8]
    [3] Bessière C. Constraint propagation. Rossi F, van Beek P, Walsh T, eds. Handbook of Constraint Programming. Amsterdam:Elservier, 2006. 29-84.
    [4] Mackworth AK. Consistency in networks of relations. Artificial Intelligence, 1977,8(1):99-118. [doi: 10.1016/0004-3702(77)90007-8]
    [5] Mohr R, Henderson TC. Arc and path consistency revised. Artificial Intelligence, 1986,28(2):225-233. [doi: 10.1016/0004-3702(86)90083-4]
    [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]
    [10] Bessière C, Regin JC, Yap RHC, Zhang YL. An optimal coarse-grained arc consistency algorithm. Artificial Intelligence, 2005,165(2):165-185. [doi: 10.1016/j.artint.2005.02.004]
    [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.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

李宏博,李占山,王涛.改进求解约束满足问题粗粒度弧相容算法.软件学报,2012,23(7):1816-1823

复制
分享
文章指标
  • 点击次数:4204
  • 下载次数: 6663
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2011-06-29
  • 最后修改日期:2011-10-08
  • 在线发布日期: 2012-07-03
文章二维码
您是第19938597位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号