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

Optimizing MDDc and STR3 for Solving Constraint Satisfaction Problem

作　　者：杨明奇 李占山[1,2] 李哲[1,2] 

机构地区：[1]吉林大学计算机科学与技术学院,吉林长春130012 [2]符号计算与知识工程教育部重点实验室(吉林大学),吉林长春130012

出　　处：《软件学报》2017年第12期3156-3166,共11页Journal of Software

基　　金：国家自然科学基金(61272208;61373052);吉林省自然科学基金(20140101200JC)~~

摘　　要：广义弧相容是求解约束满足问题应用最广泛的相容性,MDDc,STR2和STR3是表约束上维持广义弧相容应用较多的算法,其中,MDDc基于对约束压缩表示的思想,将表约束表示成多元决策图,对各个元组之间存在较多交叠部分的约束具有很好的压缩效果;STR3同STR2一样,基于动态维持有效元组的思想,当元组集规模缩减较慢时,STR3维持广义弧相容的效率高于STR2.通过深入分析发现,MDDc中查找节点的有效出边和STR3中检测并删除无效元组是耗时最多的操作.分别对MDDc和STR3提出一种自适应查找有效出边和检测删除无效元组的方法AdaptiveMDDc和AdaptiveSTR,对于同一操作,可以根据回溯搜索不同阶段的局势,自适应地选择代价最小的实现方法.得益于较低的判断代价以及回溯搜索不同阶段采用不同方法的效率差异,AdaptiveMDDc和AdaptiveSTR相比,原算法速度提升显著,其中,AdaptiveSTR在一些问题上相比STR3提速3倍以上.Generalized arc consistency （GAC） is the most widely studied consistency for solving constraint satisfaction problem （CSP）. MDDc, STR2 and STR3 are widely used algorithms for enforcing GAC on table constraints, where MDDc represents constraints in a compression method which converts a table constraint into a multi-valued diagram （MDD）. When a MDD has many identical parts, the compression ratio is high and MDDc outperforms others. STR3, similar to STR2, dynamically reduces the table size by maintaining a table of only valid tuples. When valid tuples decrease slowly, STR3 outperforms STR2. Considering that finding valid outgoing edges of MDD nodes and checking and deleting invalid tuples in dual table are the most time-consuming operations in MDDc and STR3, this study proposes AdaptiveMDDc and AdaptiveSTR respectively for MDDc and STR3 to perform the above two operations in an adaptive way so that the lowest cost strategy in different backtrack search stages is always employed. Benefiting from lower cost of strategy and significant performance difference of each strategy during different backtrack search stages, AdaptiveMDDc and AdaptiveSTR have better performance compared to the original methods, and ApaptiveSTR is over three times faster than STR3 in some instances.

关 键 词：约束满足问题(CSP) 广义弧相容(GAC) 自适应 多元决策图(MDD) AdaptiveMDDc AdaptiveSTR 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]