混合exactly-one约束的模型计数研究

摘要

模型计数是求给定命题公式的模型数,是人工智能领域的一个基本问题.在贝叶斯网络、有界模型检测、精确集合覆盖等众多实际问题中,存在许多exactly-one约束.常见的处理方法是将exactly-one约束编码为CNF公式,再调用模型计数器求解.这种方法扩大了命题公式的规模,容易导致求解时间过长.本文分别提出从CNF公式中还原exactly-one约束的ECR算法和处理exactly-one约束的ECP算法.ECR算法能明显提高C2D编译器的求解效率.基于最新的模型计数器ExactMC,本文改进了能识别和单独处理exactly-one约束的模型计数器ECMC.实验结果表明,ECMC的时间效率相比ExactMC有显著提高.