优化求解约束满足问题的MDDc和STR3算法

• 作者: 李占山 李哲 杨明奇
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 约束满足问题(CSP) 广义弧相容(GAC) 自适应 多元决策图(MDD) AdaptiveMDDc AdaptiveSTR
• 年，卷（期）: 2017,（12）
• 所属期刊栏目: 模式识别与人工智能
• 页码范围: 3156-3166
• 页数: 11页
• 分类号: TP18
• 字数: 8354字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005242

摘要

广义弧相容是求解约束满足问题应用最广泛的相容性,MDDc,STR2和STR3是表约束上维持广义弧相容应用较多的算法,其中,MDDc基于对约束压缩表示的思想,将表约束表示成多元决策图,对各个元组之间存在较多交叠部分的约束具有很好的压缩效果;STR3同STR2一样,基于动态维持有效元组的思想,当元组集规模缩减较慢时,STR3维持广义弧相容的效率高于STR2.通过深入分析发现,MDDc中查找节点的有效出边和STR3中检测并删除无效元组是耗时最多的操作.分别对MDDc和STR3提出一种自适应查找有效出边和检测删除无效元组的方法AdaptiveMDDc和AdaptiveSTR,对于同一操作,可以根据回溯搜索不同阶段的局势,自适应地选择代价最小的实现方法.得益于较低的判断代价以及回溯搜索不同阶段采用不同方法的效率差异,AdaptiveMDDc和AdaptiveSTR相比,原算法速度提升显著,其中,AdaptiveSTR在一些问题上相比STR3提速3倍以上.