摘要翻译：
近年来，人们对求解约束满足问题的回溯算法提出了许多改进。改进回溯算法的技术可以方便地分为前瞻方案和回溯方案。不幸的是，前瞻和回顾方案并不完全正交，因为经验表明，前瞻技术的提高有时会与回顾技术的效果相反。在本文中，我们重点讨论了两个最重要的前瞻技术--使用变量排序启发式和在回溯搜索过程中保持一定程度的局部一致性--与冲突导向反跳(CBJ)的回溯技术之间的关系。我们证明了存在一个“完美”的动态变量排序，使得CBJ变得冗余。我们还从理论上证明，随着回溯搜索中保持的局部一致性水平的增加，回溯搜索的改进就越少。我们的理论结果部分解释了为什么在前瞻阶段做得更多的回溯算法不能从背跳回溯方案中受益更多。最后，我们通过经验证明，将CBJ加入到一个保持广义弧一致性(GAC)的回溯算法中，我们称之为GAC-CBJ算法，仍然可以提供数量级的加速。我们的实证结果与Bessiere和Regin(1996)的结论形成了对比，CBJ对于保持弧一致性的算法是无用的。
---
英文标题：
《Conflict-Directed Backjumping Revisited》
---
作者：
X. Chen, P. van Beek
---
最新提交年份：
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 recent years, many improvements to backtracking algorithms for solving constraint satisfaction problems have been proposed. The techniques for improving backtracking algorithms can be conveniently classified as look-ahead schemes and look-back schemes. Unfortunately, look-ahead and look-back schemes are not entirely orthogonal as it has been observed empirically that the enhancement of look-ahead techniques is sometimes counterproductive to the effects of look-back techniques. In this paper, we focus on the relationship between the two most important look-ahead techniques---using a variable ordering heuristic and maintaining a level of local consistency during the backtracking search---and the look-back technique of conflict-directed backjumping (CBJ). We show that there exists a "perfect" dynamic variable ordering such that CBJ becomes redundant. We also show theoretically that as the level of local consistency that is maintained in the backtracking search is increased, the less that backjumping will be an improvement. Our theoretical results partially explain why a backtracking algorithm doing more in the look-ahead phase cannot benefit more from the backjumping look-back scheme. Finally, we show empirically that adding CBJ to a backtracking algorithm that maintains generalized arc consistency (GAC), an algorithm that we refer to as GAC-CBJ, can still provide orders of magnitude speedups. Our empirical results contrast with Bessiere and Regin's conclusion (1996) that CBJ is useless to an algorithm that maintains arc consistency.
---
PDF链接：
https://arxiv.org/pdf/1106.0254