摘要:
基于树分解的回溯搜索算法, 结合separator分解算子提出一种新的搜索算法BTD+-MAC. 该算法在搜索时, 优先选择separator中的变量进行相容性检查和实例化, 由于树宽度的减小能提高约束传播的效率, 进而提高问题求解效率. 对几组benchmark问题进行测试, 测试结果表明, 该算法在问题求解效率上超过了MAC3rm算法和BTD-MAC算法.
中图分类号:
吕巍, 张舒娟. 结合Separator的约束满足问题树分解方法[J]. 吉林大学学报(理学版), 2016, 54(02): 291-296.
LV Wei, ZHANG Shujuan. Tree Decomposition Method Combined with Separator in Constraint Satisfaction Problems[J]. Journal of Jilin University Science Edition, 2016, 54(02): 291-296.