摘要
从地理信息系统、环境智能等领域的实际需求出发,提出了半定性约束满足问题(SQCSP),并得到了初步结果。证明了区间代数及扩展模型的SQCSP可由QCSP判定。给出了RCC5的多项式时间SQCSP判定算法。RCC8的SQCSP是NP完全问题,给出了带限制条件SQCSP的多项式时间判定算法。证明了上述判定算法的正确性,并给出了实例构造算法。最后,利用SQCSP算法实现了带变量布尔运算的QCSP求解。
Motivated by the requirement of the geographical information system and ambient intelligence, the Semi-Qualitative Constraint Satisfaction Problem （SQCSP） is proposed, and some preliminary results are obtained. The SQCSP of interval algebra and its extension model can be determined Qualitative Constraint Satisfaction Problem （QCSP）. A polynomial-time decision algorithm of RCC5 is given. The SQCSP of RCC8 is a Non-deterministic Polynomial time （NP）- complete problem. A polynomial-time decision algorithm with constriction is given. The correctness proofs and instance algorithms for the above problems are provided. Finally, QCSP with boolean operations on variables is solved using SQCSP algorithm.
出处
《吉林大学学报（工学版）》
EI
CAS
CSCD
北大核心
2012年第4期942-946,共5页
Journal of Jilin University:Engineering and Technology Edition
基金
教育部留学回归人员科研启动基金项目
国家自然科学基金重点项目(61133011)
吉林大学科学前沿与交叉学科创新项目(450060481091)
吉林大学青年教师创新项目(450060481194)
关键词
人工智能
定性空间推理
半定性约束满足问题
区域连接演算
空间对象布尔运算
artificial intelligence
qualitative spatial reasoning
semi-qualitative constraint satisfactionproblems region connection calculus
boolean operations on spatial objects
