量词约束满足问题的结构特征研究

The Constraint Satisfaction Problem (CSP) is a tool for solving a number of important problems in computer science and artificial intelligence. The goal of solving this problem is to find a group of assignments to variables such that all constraints are satisfied. The Quantified Constraint Satisfaction Problem (QCSP) is a generalization of the CSP, where variables are existentially or universally quantified. QCSPs can be employed to represent and solve problems with uncertainty. Recently, researchers have concentrated on QCSPs, as well as on its search algorithms and applications. However, investigating structural properties of QCSPs is still in its early stage. This project mainly intends to study and analyze properties of structures and constraint relations in QCSPs, and thus propose suitable algorithms based on those properties obtained. The detailed research contents include: study hybrid tractable subclasses that can be solved in polynomial-time, and then determine the sufficient conditions and necessary conditions to identify the tractable subclasses; analyze backdoor sets of QCSPs with the tractable subclasses; analyze decomposition methods using properties of tractable subclasses and backdoor sets to separate easy parts from a QCSP, and propose efficient algorithms associated with the decomposition methods to solve industrial problems. It can be regarded as a solid foundation research for industrial applications.

约束满足问题是解决计算机科学和人工智能领域中诸多重要问题的工具，求解该问题需要找到一组变量赋值并满足所有的约束关系。量词约束满足问题对变量限定了全称量词或存在量词，它是经典约束满足问题的扩展，被用于刻画问题模型中的不确定性。最近，研究者逐渐开始关注量词约束满足问题，其搜索算法以及相关应用方面的研究也受到重视。但是目前针对该问题的结构特征分析的研究还处于起步阶段。本项目的主要目标是研究和分析量词约束满足问题中的结构特征以及约束关系特征，并根据这些特征提出相应的求解算法，具体包括：探索量词约束满足问题的混合多项式时间可解子类，分析确定多项式时间可解子类的充分条件和必要条件；研究基于多项式时间可解子类的隐蔽集分析技术；根据多项式时间可解子类和隐蔽集的特征研究问题结构的分解方法，从而分离出问题中的易解部分，然后以此为依据针对工业问题设计高效的求解算法，并为其在工业领域的实际应用打下坚实的基础。

约束满足问题是人工智能领域的一个基础问题，被广泛地用于解决日程安排、车辆路线规划和资源分配等领域的决策与优化问题。而量词约束满足问题可以处理诸多实际问题中的不确定性。由于计算复杂性的限制，求解该问题通常是十分困难的，但是在这些问题中，某些特殊条件可以保证问题是多项式时间内可解的，这类问题构成了可解子类。研究可解子类所需要的限制条件并识别出更一般化的可解子类可以更好地理解问题的内在结构特征，分析出问题的难解或易解因素，从而为求解算法的设计提供理论依据。本项目的研究内容围绕可解子类的分析展开。首先，针对混合可解子类中的属性提出伴随值的概念，并通过伴随值扩展已知的混合可解子类，证明了更一般化的子类，同时还分析了新子类与现有子类的关系，证明了新子类与其他已知的混合可解子类是不可比较的，因此基于伴随值的子类包含了未知的多项式可解情况。其次，针对量词约束满足问题中全称量词变量的特性，提出了针对全称量词变量相容性的概念，并分析了相容性算法的时间复杂度，同时还分析了算法在多项式时间内可解的情况；基于该算法和全称量词变量结构分析的方法，采用全称量词变量与存在量词变量分别分析的方式，提出了一个一般化的理论结果，并确定了新的可解子类。另外，本项目通过所确定的可解子类，提出了隐蔽集的识别方法，并分析不同可解子类对隐蔽集的影响，还通过实验的方式验证了所提出的更一般化的可解子类可以分离出包含更多变量的多项式时间可解部分，并识别出更小的隐蔽集。基于约束结构的分析方法和可解子类的理论研究结果，提出了针对各种求解算法的启发式策略，具体包括：提出了一个基于隐蔽集的回溯搜索算法；提出了一个回溯算法中的值启发式策略；提出了一个针对局部搜索算法的变量选择启发式策略。所提出的算法和策略均通过实验的方式验证了有效性，与现有算法的比较结果表明它们具有更优的求解效率。以上研究成果为工业领域的应用提供了理论基础和技术支持。