摘要: 1．该文创新点：
量化约束求解问题（QCSP）是一类PSPACE完全问题，是约束求解问题（CSP）问题的自然扩展。它可以用来编码许多实际应用问题，比如规划，博弈问题等。以前求解这类问题的主要方法是将其转换成QBF或者其他的公式，用其他的工具比如QBF Solver求解。最近开发出许多QCSP的求解器可以直接对 QCSP问题进行求解，并且取得了一些好的效果。变量选择策略在CSP中扮演了很重要的角色，好的变量选择策略能极大的提高CSP的求解效率。但是在QCSP领域，目前还没有求解器采用变量选择策略。这是因为对于QCSP来说，变量的选择只能在块之间进行，这样就限制了选择策略的应用。鉴于变量选择策略的重要性，本文研究了一种打破块约束的变量选择方法。一个QCSP公式中，很多后面的变量于前面的变量之间并无依赖关系，因此这些变量可以被先赋值。本文采用标准依赖关系图来找出变量之间的依赖关系，然后根据这个依赖图来进行变量选择策略。这在国内外还是首次。试验表明，采用了本文方案的求解器要比没有采用本文方案的求解器更高效。在变量选择策略上一般只考虑Dom和deg两个因素，即变量值域的大小和它的关联度。本文引入一个新的用于变量选择策略的计算因素Dep，这个因素用来表示一个变量相对于其他变量的依赖程度。试验证明采用了该因素的变量选择策略比没有采用该因素的更能提高求解器的效率。
2．实现方法
本文先给出理论上的算法，然后采用 C++语言实现了一个求解器，实现环境是Ubuntu10.4.
3．结论及未来待解决的问题
试验表明采用了标准依赖关系图的求解器要比没有采用的求解器更高效。达到了本研究工作的目的。将来的工作是将本文的工作成果整合到目前的主流求解器中，从而提高他们的效率。
此外还要将更多的先进技术引入本文实现的求解器，考察各种技术和标准依赖关系图相结合的效果。
4．实用价值或应用前景
本文提出的方法是一类通用的方法，独立于求解器。任何自上而下搜索型求解器都可以无困难的采用本文的工作，从而提高求解的效率，也就是说本文的工作可以以很小的代价整合到当前的主流求解器中。因此本文的工作有广泛的应用前景。