加权约束满足问题的改进RDS符号代数决策图求解算法

徐周波; 杨新亮; 古天龙; 宁黎华

首页> 中文期刊> 《模式识别与人工智能》 >加权约束满足问题的改进RDS符号代数决策图求解算法

加权约束满足问题的改进RDS符号代数决策图求解算法

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

加权约束满足问题(WCSP)是一类约束最优化问题.文中基于RDS思想,从减少RDS分解的子问题个数及提高各个子问题的求解效率入手,提出WCSP的改进RDS符号代数决策图(ADD)求解算法.通过改进最多约束变量的变量选择法,引入RDS变量引导原问题的子问题分解,进而减少RDS中分解的子问题个数.利用变量的后向度,进一步改进子问题的分解方法.为提高各个子问题的求解效率,利用桶消元算法并结合ADD操作消去子问题中的非RDS变量,进而减少子问题中的变量个数,提高深度优先分支界定法的下界.在大量随机生成的测试用例上的实验证明文中算法的优越性.

著录项

来源
《模式识别与人工智能》 |2015年第12期|1074-1083|共10页
作者
徐周波; 杨新亮; 古天龙; 宁黎华;
展开▼
作者单位

桂林电子科技大学广西可信软件重点实验室桂林541004;

桂林电子科技大学广西可信软件重点实验室桂林541004;

桂林电子科技大学广西可信软件重点实验室桂林541004;

桂林电子科技大学广西可信软件重点实验室桂林541004;

展开▼
原文格式 PDF
正文语种 chi
中图分类理论、方法;
关键词
加权约束满足问题(WCSP); Russian Doll Search (RDS); 代数决策图(ADD); 符号算法;

相似文献

中文文献
外文文献
专利

1. 基于改进树分解技术的约束满足问题的符号ADD求解算法 [J] . 王敏 ,徐周波 . 桂林电子科技大学学报 . 2017,第002期
2. 加权约束满足问题的改进深度优先搜索算法 [J] . 贺仁杰 ,谭跃进 . 系统工程学报 . 2004,第005期
3. 一种高效的动态图最大加权独立集求解算法 [J] . 祁才云 ,周军锋 ,杜明 . 新一代信息技术 . 2021,第007期
4. 一种高效的动态图最大加权独立集求解算法 [J] . 祁才云 ,周军锋 ,杜明 . 新一代信息技术 . 2021,第007期
5. 基于极小代数赋权有向图最短路径求解算法 [J] . 李彦平 ,魏昆 ,王丹 . 沈阳大学学报 . 2015,第001期
6. 基于模糊约束满足问题的谈判决策研究 [C] . 李海晨 ,黑龙江大学信息管理学院 ,冯玉强 . 第八届中国管理科学学术年会 . 2006
7. 基于RDS技术的加权约束满足问题的符号算法研究 [A] . 杨新亮 . 2015

加权约束满足问题的改进RDS符号代数决策图求解算法

摘要

著录项

相似文献

相关主题

期刊订阅