全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

基于论域折半的最大限定路径相容算法

, PP. 229-235

Keywords: 人工智能,论域折半,弧相容,最大限定路径相容,不可满足问题

Full-Text   Cite this paper   Add to My Lib

Abstract:

针对绝大多数不可满足问题的特点,提出了一种将弧相容算法与最大限定路径相容算法相结合的相容性算法——基于论域折半的最大限定路径相容的算法。该算法充分利用了弧相容计算开销小和最大限定相容删值能力强的优点,可以减少在求解不可满足问题中生成的结点数,进而提高求解效率。实验结果表明,本文算法在处理不可满足问题时的求解效率明显优于传统的维持弧相容算法。

References

[1]  Sabin Daniel, Freuder Eugene C. Contradicting conventional wisdom in constraint satisfaction[C]∥Proceedings of CP, Rosario, Orcas Island, Was- hington, 1994: 10-20.
[2]  Likitvivatanavong Chavalit,Zhang Yuan-lin, Bowen James,et al.Arc consistency during search[C]∥Proceedings of IJCAI, India: Morgan Kaufmann, 2007: 137-142.
[3]  Mackworth Alan K.Consistency in networks of relations[J]. Artificial Intelligence, 1977,8(1): 99-118.
[4]  Christophe Lecoutre, Fred Hemery. A study of residual supports in arc consistency[C]∥Proceeding of IJCAI, 2007:125-130.
[5]  Christophe Lecoutre, Julien Vion. Enforcing arc consistency using bitwise operations[J]. Const- raint Programming Letters,2008(2): 21-35.
[6]  Romuald Debruyne, Christian Bessiere. Some practical filtering techniques for the constraint satisfaction problem[C]∥Proceedings of IJCAI, 1997: 412-417.
[7]  Romuald Debruyne, Christian Bessiere. From restricted path consistency to max-restricted path consistency[C]∥Proceedings of CP, 1997: 312-326.
[8]  Thanasis Balafoutis, Anastasia Paparrizou, Kostas Stergiou, et al. New algorithms for max restricted path consistency[J]. Constraints, 2011,16(4): 372-406.
[9]  Christophe Lecoutre, Patrick Prosser. Maintaining singleton arc consistency[C]∥Proceedings of CPAI, 2006: 47-61.
[10]  Julien Vion, Romuald Debruyne. Light algorithms for maintaining max-RPC during search[C]∥Proceedings of SARA,2009.
[11]  Possi Francesca, Van Beek Peter, Walsh Toby. Handbook of Constraint Programming[M] .New York: Elsevier, 2006:13-29.
[12]  Frédéric Boussemart, Fred Hemery, Christophe Lecoutre, et al. Boosting systematic search by weighting constraints[C]∥Proceedings of ECAI, 2004: 146-150.
[13]  李占山,张良,郭劲松,等.基于问题结构的边界启发式方法[J].吉林大学学报:工学版,2013,43(5):1045-1051.Li Zhan-shan, Zhang Liang, Guo Jin-song, et al. Boundary heuristic based on problem structure[J]. Journal of Jilin University (Engineering and Technology Edition), 2013, 43(4):1045-1051.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133