发帖
雷达卡
摘要翻译：
CSPs的两种标准分支方案是D-路和2-路分支。尽管在理论上，后者可以比前者更有效，但缺乏显示这种差异的经验证据。为了研究这一点，我们首先在广泛的基准上对这两个分支方案进行了实验比较。实验结果验证了D-路和2-路分支之间的理论差距，因为我们从一个简单的变量排序启发式（如dom）转向更复杂的启发式（如dom/DDEG）。然而，也许令人惊讶的是，实验还表明，当使用像DOM/WDEG这样的最先进的变量排序启发式时，在许多情况下，d-way显然比2-Way分支更有效。基于这一观察，我们开发了两个通用的启发式，它们可以应用于搜索过程中的某些点，以决定是否遵循双向分支或与D-方向分支接近的限制性双向分支版本。这些启发式的应用得到了一个自适应分支方案。两种启发式算法的实例实验证明，在许多问题上，自适应分支搜索优于固定分支搜索。
---
英文标题：
《Adaptive Branching for Constraint Satisfaction Problems》
---
作者：
Thanasis Balafoutis 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 two standard branching schemes for CSPs are d-way and 2-way branching. Although it has been shown that in theory the latter can be exponentially more effective than the former, there is a lack of empirical evidence showing such differences. To investigate this, we initially make an experimental comparison of the two branching schemes over a wide range of benchmarks. Experimental results verify the theoretical gap between d-way and 2-way branching as we move from a simple variable ordering heuristic like dom to more sophisticated ones like dom/ddeg. However, perhaps surprisingly, experiments also show that when state-of-the-art variable ordering heuristics like dom/wdeg are used then d-way can be clearly more efficient than 2-way branching in many cases. Motivated by this observation, we develop two generic heuristics that can be applied at certain points during search to decide whether 2-way branching or a restricted version of 2-way branching, which is close to d-way branching, will be followed. The application of these heuristics results in an adaptive branching scheme. Experiments with instantiations of the two generic heuristics confirm that search with adaptive branching outperforms search with a fixed branching scheme on a wide range of problems.
---
PDF链接：
https://arxiv.org/pdf/1008.0660
京公网安备 11010802022788号
