摘要翻译：
我们描述了搜索过程中的分解(DDS)，这是一种将和/或树搜索集成到基于传播的约束求解器中的方法。该算法将约束满足问题的子问题动态分解为独立的部分问题，避免了冗余工作。本文讨论了DDS如何与基于传播的求解器成功的关键特征相互作用：约束传播，特别是全局约束，以及动态搜索启发式。我们已经为Gecode约束编程库实现了DDS。图着色中的解计数和蛋白质结构预测两个应用实例说明了DDS在实际应用中的好处。
---
英文标题：
《Decomposition During Search for Propagation-Based Constraint Solvers》
---
作者：
Martin Mann and Guido Tack and Sebastian Will
---
最新提交年份：
2008
---
分类信息：

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

---
英文摘要：
  We describe decomposition during search (DDS), an integration of And/Or tree search into propagation-based constraint solvers. The presented search algorithm dynamically decomposes sub-problems of a constraint satisfaction problem into independent partial problems, avoiding redundant work.   The paper discusses how DDS interacts with key features that make propagation-based solvers successful: constraint propagation, especially for global constraints, and dynamic search heuristics.   We have implemented DDS for the Gecode constraint programming library. Two applications, solution counting in graph coloring and protein structure prediction, exemplify the benefits of DDS in practice.
---
PDF链接：
https://arxiv.org/pdf/0712.2389