关于扩展对象之间基本方向的推理 硬度结果

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
Goyal和Egenhofer提出的基数方向演算(CDC)是一种对扩展对象方向信息具有很强表达能力的定性演算。早期的研究表明，基本CDC约束的完备网络的一致性检验是容易的，而用CDC进行推理一般是NP困难的。然而，本文表明，如果允许某些未指定的约束，那么对可能不完全的基本CDC约束网络的一致性检验已经是困难的。这在疾病预防控制中心的易处理和难处理的亚类之间划出了一条清晰的界限。该结果是由众所周知的3-SAT问题得到的。
---
英文标题：
《Reasoning about Cardinal Directions between Extended Objects: The
  Hardness Result》
---
作者：
Weiming Liu, Sanjiang Li
---
最新提交年份：
2010
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  The cardinal direction calculus (CDC) proposed by Goyal and Egenhofer is a very expressive qualitative calculus for directional information of extended objects. Early work has shown that consistency checking of complete networks of basic CDC constraints is tractable while reasoning with the CDC in general is NP-hard. This paper shows, however, if allowing some constraints unspecified, then consistency checking of possibly incomplete networks of basic CDC constraints is already intractable. This draws a sharp boundary between the tractable and intractable subclasses of the CDC. The result is achieved by a reduction from the well-known 3-SAT problem.
---
PDF链接：
https://arxiv.org/pdf/1011.0233

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Intelligence Presentation Constraints Consistency Directional 表明 consistency 网络 constraints 信息