期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于序列的子问题相容性技术

Singleton Sub-problem Arc Consistency Based on Order
在线阅读 下载PDF
导出
摘要 研究约束求解中的相容性技术,针对目前已有相容性的传播级别,提出一种新的相容性概念——基于序列的子问题相容性（SSAC）,并给出相应的实现算法。然后分析其时空、空间复杂性及正确性,证明SSAC化简不改变原约束满足问题的解集,同时证明SSAC的约束传播能力介于SAC和AC之间。通过对随机问题和composed问题的测试表明,所提算法的效率是已有算法SAC-SDS和SAC-3的2~3倍。 In investigation of the consistency techniques,a new consistency concept SSAC was proposed based on the recently propagation levels.The algorithm and properties of SSAC were given successively in the paper.Thereafter we concluded that simplification of SSAC dosen＇t change the solution set of the original constraint satisfaction problem.Meanwhile the propagation ability of SSAC is between SAC and AC.Experiments results show that the performance of SSAC is 2 or 3times than the existed algorithms.
作者 陈德泉 张永刚 辛颖 刘文壮
机构地区 吉林大学计算机科学与技术学院 吉林大学符号计算与知识工程教育部重点实验室
出处 《计算机科学》 CSCD 北大核心 2015年第7期28-31,37,共5页 Computer Science
基金 国家自然科学基金面上项目:基于自适应约束传播的约束求解方法研究(61170314) 国家自然科学基金面上项目:结合自主搜索机制的约束求解方法研究(61373052)资助
关键词 约束满足 相容性技术 SSAC Constraint satisfaction Arc consistency technique SSAC
分类号 TP181 [自动化与计算机技术—控制理论与控制工程]
  • 相关文献

参考文献18

  • 1Bartak R. Theory and Practice of Constraint Propagation[C]// Proceedings of the 3rd Workshop on Constraint Programming in Decision and Control. Gliwice, Poland, 2001 : 7-14.
  • 2Gent I P, Nightingale P, Rowley A, et al. Solving quantified con- straint satisfaction problems[J]. Artificial Intelligence, 2008, 172(6/7) : 738-771.
  • 3Yokoo M, Durfee E H, Ishida T, et al. Distributed constraint satisfaction for formalizing distributed problem solving[C]// Proceedings of the 12th IEEE International Conference on Dis- tributed Computing System. Yokohama, Japan: IEEE Computer Society Press, 1992 : 614-621.
  • 4Bessiere C, Regin J C, Yap R H C, et al. An optimal coarse grained Arc Consistency algorithm[J]. Artificial Intelligence, 2005,165(2) : 165-185.
  • 5Maekworth A K. Consistency in networks of relations[J]. Arti- ficial Intelligence, 1977,8( 1 ) : 99-118.
  • 6Bessiere C, Regin J C. Refining the basic constraint propagation algorithm[C]//Proceedings of the 17th International Joint Con- ference on Artificial Intelligence. Seattle, USA: Morgan Kauf- mann, 2001 : 309-315.
  • 7Deburyne R, Bessiere C. Some practical filtering techniques for the constraint satisfaction problem[C]//Proceedings of the 15tb International Joint Conference on Artificial Intelligence. Nago- ya, Japan: Morgan Kaufmann, 1997 : 412-417.
  • 8Bartak R, Erben tL A new algorithm for singleton arc consisten- cy[C]// Proceedings of FLAIRS Conference. Florida, USA: AAAI Press, 2004 : 257-262.
  • 9Bessiere C, Debruyne R. Optimal and suboptimal singleton arc consistency algorithms[C]//Proceedings of the 19th Interna- tional Joint Conference on Artificial Intelligence. Edinburgh, UK: Professional Book Center, 2005 : 54-59.
  • 10Lecoutre C, Cardon S. A greedy approach to establish singleton arc consistency[C]//Proceedings of the 19th International Joint Conference on Artificial Intelligence. Edinburgh, UK: Profes- sional Book Center, 2005 : 199-204.

二级参考文献74

  • 1Gent I P, Macintyre E, Prosser P, Smith B M, Walsh T. Random constraint satisfaction flaws and structure. Journal of Constraints, 2001, 6(4): 345-372
  • 2Xu Ke, Li Wei. Exact phase transitions in random constraint satisfaction problems. Journal of Artificial Intelligence Research. 12(2000): 93-103
  • 3Xu K, Boussemart F, Hemery F, Lecoutre C. A simple model to generate hard satisfiable instances. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence. Edinburgh, UK: Professional Book Center, 2005. 337-342
  • 4Bartak R. Theory and practice of constraint propagation. In: Proceedings of the 3rd Workshop on Constraint Programruing in Decision and Control. Gliwice, Poland: Springer, 2001. 7-14
  • 5Bessiere C, Regin J C, Yap R H C, Zhang Y L. An optimal coarse-grained arc consistency algorithm. Artificial Intellgence, 2005, 165(2): 165-185
  • 6Lecoutre C, Cardon S, Julien V. Conservative dual consistency. In: Proceedings of the 22nd Conference on Artificial Intelligence. California, USA: AAAI Press, 2007. 237-242
  • 7Lecoutre C, Cardon S. A greedy approach to establish singleton arc consistency. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence. Edinburgh, UK: Professional Book Center, 2005. 199-204
  • 8Bessiere C, Debruyne R. Optimal and suboptimal singleton arc consistency algorithms. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence. Edinburgh, UK: Professional Book Center, 2005. 54-59
  • 9van Dongen M R C. Beyond singleton arc consistency. In: Proceedings of the 17th European Conference on Artificial. Amsterdam, Holand: IOS Press, 2006. 163-167
  • 10Prosser P, Stergiou K, Walsh T. Singleton consistencies. In: Proceedings of Constraint Programming. Singapore, Singapore: Springer, 2000. 353-368

共引文献15

计算机科学
2015年 第7期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部