RCC8的一致分割及其算法

• 作者: 崔文正
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 空间定性推理 一致分割 约束满足问题 路径一致性算法 区域连接演算
• 年，卷（期）: 2015,（1）
• 所属期刊栏目: 数据库、数据挖掘、机器学习
• 页码范围: 143-150
• 页数: 8页
• 分类号: TP182
• 字数: 8836字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1301-0259

摘要

区域连接演算（Region Connection Calculus，RCC）是一种用于空间定性表示和推理的形式化模型，如RCC5，RCC8等，其一致性检查被证明是一个NP问题。幸运的是，在其可处理子集上，路径一致性和一致性等价，即便这样也有O(n3)的时间复杂度和O(n2)的空间复杂度。为了提高一致性检查的效率，提出了一致分割的概念，给出了其定义和成立的充分必要条件，用来将RCC8的约束图在保持一致性的前提下分割成若干个子图，分而求解各个子图的一致性；并随后给出了几种一致分割的充分条件，和相应的高效分割算法。在随机生成的大型、稀疏约束图上的实验表明了一致分割的有效性。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	崔文正	中国科学院数学与系统科学研究院	1	3	1.0	1.0