论文部分内容阅读
实际生活中的许多问题都可以建模为约束问题模型,然后用约束满足问题求解技术进行处理,比如物流规划,硬件电路设计,生产调度等各领域的问题,这就使得研究约束满足问题(Constraint Satisfaction Problem,CSP)具有重大的实用价值。求CSP的解,就是为每个变量赋一个其值域内的取值,使得所有约束被满足。弧一致性( Arc consistency,AC)技术作为经常与搜索算法相结合的约束推理求解技术,通过在搜索前或搜索过程中删除肯定不会出现在最终解中的值,达到压缩搜索空间,提高求解效率的目的。 传统弧一致性实现算法对于状态空间和变量组合难免要逐个枚举,使用有序二叉决策图(Ordered Binary Decision Diagram,OBDD)及其扩展形式代数决策图(Algebraic Decision Diagram,ADD)则可以实现状态空间或变量组合的隐式表示和搜索,且具有高效存储和易操作等特性,可以在一定程度上缓解组合复杂性问题。因此,本文对基于OBDD及其扩展形式ADD的弧一致性技术实现方法及其在求解中的应用做了相关研究,取得的主要研究成果如下: (1)根据经典 CSP及加权约束满足问题(Weighted Constraint Satisfaction Problem,WCSP)弧一致性定义及实现方法的具体步骤,重写了ADD中的量化提取操作、部分ITE操作、以及寻找子路径等操作。为提出基于AD D的弧一致性实现算法打下了基础,也为具体编程验证弧一致性符号ADD算法性能提供了理论依据。 (2)给出了经典CSP的弧一致性符号ADD算法,在搜索前利用该算法对已表示为ADD形式的原问题进行预处理,接着将该算法嵌入回溯(Backtracking algorithm, BT)搜索框架中,在搜索的过程中使由未实例化的变量组成的子问题也保持弧一致性,形成 BT+GetAC算法。实验通过对随机产生的测试用例及部分标准库中的测试用例进行求解对比,结果表明,对于经典 CSP求解,本文算法的执行效率既优于保持弧一致性的回溯算法,也优于现有带预处理的约束满足问题求解技术。 (3)给出了基于ADD的WCSP弧一致性预处理算法AC-Pre。实验结果表明利用该算法对WCSP进行AC预处理后,求得的初始可行解比现有WCSP的符号求解算法得到的初始可行解质量更高,求得最优解所需的回溯次数也有所减少,尤其是在结点数目较多,约束松紧度较大的情况下求解效率提高明显。