半定性约束满足问题求解

从地理信息系统、环境智能等领域的实际需求出发,提出了半定性约束满足问题(SQCSP),并得到了初步结果。证明了区间代数及扩展模型的SQCSP可由QCSP判定。给出了RCC5的多项式时间SQCSP判定算法。RCC8的SQCSP是NP完全问题,给出了带限制条件SQCSP的多项式时间判定算法。证明了上述判定算法的正确性,并给出了实例构造算法。最后,利用SQCSP算法实现了带变量布尔运算的QCSP求解。