摘要翻译：
CP求解器的搜索策略由它所采用的变量和值排序启发式以及它所遵循的分支方案决定。尽管变量排序和值排序启发式对搜索努力的影响已经得到了广泛的研究，但不同分支方案对搜索努力的影响却很少受到关注。在本文中，我们通过一个实验评估来研究这种影响，包括标准的分支方案，如2路，D-路和二分域分裂，以及在值集合上执行分支的集合分支的变化。我们还提出并评价了一种通用的集合分支方法，其中使用值排序启发式算法分配给值的分数来创建一个域到集合的划分，以及一种来自机器学习的聚类算法。实验结果表明，尽管分枝方案之间的指数差异并不是很普遍，正如理论上所预测的那样，分枝方案的选择在某些问题上仍然会产生很大的差异。集合分支方法与双向分支方法相比具有很强的竞争力，并且在某些问题类上优于双向分支方法。对结果的统计分析表明，我们提出的基于聚类的集合分支方法是所有方法中最好的。
---
英文标题：
《Experimental Evaluation of Branching Schemes for the CSP》
---
作者：
Thanasis Balafoutis, Anastasia Paparrizou and Kostas Stergiou
---
最新提交年份：
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 search strategy of a CP solver is determined by the variable and value ordering heuristics it employs and by the branching scheme it follows. Although the effects of variable and value ordering heuristics on search effort have been widely studied, the effects of different branching schemes have received less attention. In this paper we study this effect through an experimental evaluation that includes standard branching schemes such as 2-way, d-way, and dichotomic domain splitting, as well as variations of set branching where branching is performed on sets of values. We also propose and evaluate a generic approach to set branching where the partition of a domain into sets is created using the scores assigned to values by a value ordering heuristic, and a clustering algorithm from machine learning. Experimental results demonstrate that although exponential differences between branching schemes, as predicted in theory between 2-way and d-way branching, are not very common, still the choice of branching scheme can make quite a difference on certain classes of problems. Set branching methods are very competitive with 2-way branching and outperform it on some problem classes. A statistical analysis of the results reveals that our generic clustering-based set branching method is the best among the methods compared.
---
PDF链接：
https://arxiv.org/pdf/1009.0407