模式识别与人工智能
2025年4月4日 星期五   首 页     期刊简介     编委会     投稿指南     伦理声明     联系我们                                                                English
模式识别与人工智能  2011, Vol. 24 Issue (1): 14-21    DOI:
论文与报告 最新目录| 下期目录| 过刊浏览| 高级检索 |
加权约束满足问题的符号ADD求解算法
徐周波1,2,古天龙2,常亮2
1.西安电子科技大学电子工程学院西安710071
2.桂林电子科技大学计算机科学与工程学院桂林541004
Symbolic ADD Algorithms for Weighted Constraint Satisfaction Problem
XU Zhou-Bo1,2, GU Tian-Long2 , CHANG Liang2
1.School of Electronic Engineering, Xidian University, Xian 710071
2.School of Computer Science and Engineering, Guilin University of Electronic Technology, Guilin 541004

全文: PDF (501 KB)   HTML (1 KB) 
输出: BibTeX | EndNote (RIS)      
摘要 加权约束满足问题(WCSP)是一类软约束满足问题。给出WCSP的代数决策图(ADD)描述,以及基于ADD的两种符号求解算法。首先,通过对变量和变量域值的二进制编码,给出软约束图的ADD表示。其次,将分支定界搜索算法与桶消元算法及符号ADD技术相结合,在静态变量序下,利用结点一致性预处理技术,对WCSP问题进行符号ADD求解。通过引入有向弧一致性计数技术提高符号ADD算法的搜索下界,对符号ADD求解算法作了改进。最后,对大量随机生成的测试用例进行实验分析。结果表明,文中算法在性能上明显优于带有存在有向弧一致性或结点一致性预处理技术的具有前向检查功能的深度优先分支定界搜索算法。
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
徐周波
古天龙
常亮
关键词 加权约束满足问题(WCSP)分支定界桶消元符号算法代数决策图(ADD)    
Abstract:The weighted constraint satisfaction problem (WCSP) is a kind of soft constraint satisfaction problems with many practical applications. An algebraic decision diagram (ADD) based scheme is proposed to solve WCSP efficiently. Firstly, the soft constraint network is represented as ADDs so that the WCSP can be formulated symbolically and manipulated implicitly. Secondly, the symbolic ADD algorithm is presented, where the branch and bound algorithm is integrated with bucket elimination algorithm symbolically. And the static variable orderings and the node consistency during search are used. To improve the lower bound of the symbolic ADD algorithm, the counting technique of directional arc consistency is adopted, and thus the symbolic ADD algorithm is improved. Finally, experiments on random problems are implemented, and the results show that the proposed algorithms outperform the depth-first branch and bound algorithms enhanced with a look-ahead process and a preprocessing step of either existential directional arc consistency or the node consistency.
Key wordsWeighted Constraint Satisfaction Problem (WCSP)    Branch and Bound    Bucket Elimination    Symbolic Algorithm    Algebraic Decision Diagram (ADD)   
收稿日期: 2010-03-01     
ZTFLH: TP301  
基金资助:国家自然科学基金(No.60963010,60903079)、广西自然科学基金(No.0832006Z)资助项目
作者简介: 徐周波,女,1976年生,博士研究生,讲师,主要研究方向为符号计算、智能规划.E-mail:xzbli_11@guet.edu.cn.古天龙,男,1964年生,教授,博士生导师,主要研究方向为形式化方法、符号计算、知识工程等.常亮,男,1980年生,博士,副教授,主要研究方向为知识表示与推理、语义Web、智能主体.
引用本文:   
徐周波,古天龙,常亮. 加权约束满足问题的符号ADD求解算法[J]. 模式识别与人工智能, 2011, 24(1): 14-21. XU Zhou-Bo, GU Tian-Long , CHANG Liang. Symbolic ADD Algorithms for Weighted Constraint Satisfaction Problem. , 2011, 24(1): 14-21.
链接本文:  
http://manu46.magtech.com.cn/Jweb_prai/CN/      或     http://manu46.magtech.com.cn/Jweb_prai/CN/Y2011/V24/I1/14
版权所有 © 《模式识别与人工智能》编辑部
地址:安微省合肥市蜀山湖路350号 电话:0551-65591176 传真:0551-65591176 Email:bjb@iim.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn