论文部分内容阅读
研究了求解约束满足问题（Constraint satisfaction problem，CSP）中的预处理技术．首先提出了子论域上的完全独立相容性（Entirety singleton consistency，ESC）概念和相廊算法，分析并证明了算法的复杂性和正确性，向后对其两条重要性质进行了详细证明．基于此概念和性质，提出了一种基于完全独立相容性的预处理算法：SAC—ESC算法，并给出了正确性证明。最后，本文采用分治思想，根据不同问题的论域自适应地合理划分其子论域．实验结果表明，对于随机问题、鸽巢问题、