ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2015, Vol. 52 ›› Issue (5): 1091-1097.doi: 10.7544/issn1000-1239.2015.20131588

• 人工智能 • 上一篇    下一篇

基于实例化次数的约束求解方法研究

李占山,张乾,张良   

  1. (吉林大学计算机科学与技术学院 长春 130012) (符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012) (zslizsli@163.com)
  • 出版日期: 2015-05-01
  • 基金资助: 
    基金项目:国家自然科学基金项目(61170314,61272208,61373052);吉林省自然科学基金项目(20140101200JC);教育部高等学校博士学科点专项科研基金项目(20100061110031)

Constraint Solving Based on the Number of Instantiation

Li Zhanshan, Zhang Qian, Zhang Liang   

  1. (College of Computer Science and Technology, Jilin University, Changchun 130012) (Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012)
  • Online: 2015-05-01

摘要: 启发式是约束满足问题领域的重要研究课题,有效的启发式方法可以极大地提高问题的求解效率.在求解约束满足问题时,发现变量实例化失败次数与值实例化成功次数反映了变量和值与已实例化集合之间的关系,将实例化次数加以利用可以对问题求解效率有很大的影响.据此,提出了实例化次数的权值统计方法,并将其与现有启发式方法相结合,提出了实例化次数启发式及其相应的约束求解算法MAC_Try,并证明了其在一个分支上的最坏时间复杂度是O(ned3).大量实验结果表明,新的MAC_Try方法在求解效率上明显优于国际上流行的MAC3rm方法.

关键词: 人工智能, 约束满足问题, 启发式, 变量实例化失败次数, 值实例化成功次数

Abstract: Heuristics is an important topic in the domain of constraint satisfaction problems. Effective heuristics can improve the efficiency of the search algorithms quite a lot. As a result, lots of heuristics to solve the constraint satisfaction problems are presented. Heuristics are divided into many types depending on the acquisition and application of heuristic information, and the main heuristics include variable ordering heuristics and value ordering heuristics. When solving the constraint satisfaction problems, we find that the failed numbers of instantiating a variable reflect the conflict between this variable and the instantiated set, and that the successful numbers of assigning a value reflect the possibility for this value of composing a local solution with the instantiated set. Both numbers have a great influence upon the efficiency of solving constraint satisfaction problems. Based on the above research conclusions, this paper proposes a method of counting the weight number of instantiation and a heuristic of instantiation number combined with the existing mainstream heuristics, and then presents a new corresponding constraint solving algorithm called MAC_Try. We prove that the worst-case time complexity is O(ned3) on a branch. A large number of experimental results show that our proposed algorithm MAC_Try is more effective than the popular constraint solving method MAC3rm.

Key words: artificial intelligence, constraint satisfaction problem(CSP), heuristic, failed number of variable instantiation, successful number of value assigning

中图分类号: