一致性与随机约束满足模型

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

摘要翻译：
本文研究了利用结构与典型硬度之间的内在联系设计非平凡随机CSP模型的可能性。我们发现，约束一致性是一个用来提高CSP算法效率的概念，它实际上是设计具有有趣的相变行为和保证指数分辨率复杂度的随机CSP模型的关键，而不对约束紧性参数或问题的域大小施加太多限制。我们提出了一个非常灵活的框架来构造具有有趣行为的问题实例，并开发了各种具体的方法来构造特定的随机CSP模型，这些模型执行不同程度的约束一致性。通过一系列的实验研究和有趣的观察来说明在随机情况下引入结构元素的有效性，验证我们的建议的鲁棒性，并研究基于我们框架的一些特定模型的特征，这些特征与回溯搜索算法的行为高度相关。
---
英文标题：
《Consistency and Random Constraint Satisfaction Models》
---
作者：
J. Culberson, Y. Gao
---
最新提交年份：
2011
---
分类信息：

一级分类：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中的材料。
--

---
英文摘要：
  In this paper, we study the possibility of designing non-trivial random CSP models by exploiting the intrinsic connection between structures and typical-case hardness. We show that constraint consistency, a notion that has been developed to improve the efficiency of CSP algorithms, is in fact the key to the design of random CSP models that have interesting phase transition behavior and guaranteed exponential resolution complexity without putting much restriction on the parameter of constraint tightness or the domain size of the problem. We propose a very flexible framework for constructing problem instances withinteresting behavior and develop a variety of concrete methods to construct specific random CSP models that enforce different levels of constraint consistency. A series of experimental studies with interesting observations are carried out to illustrate the effectiveness of introducing structural elements in random instances, to verify the robustness of our proposal, and to investigate features of some specific models based on our framework that are highly related to the behavior of backtracking search algorithms.
---
PDF链接：
https://arxiv.org/pdf/1110.2204

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：一致性 Intelligence Experimental observations satisfaction 模型 有效性 元素 结构 引入