handbook of CP 10.5 Dynamic Symmetry Breaking Methods 翻译
动态对称破坏方法是在搜索过程中破坏对称性的方法。 SBDD和SBDS是本节中描述的两种方法。 在这两种方法中，对称性作用于变量/值对。 通过启发式破坏对称性包含在此类别中，因为尽管这些变量和值排序启发式算法在搜索开始之前已完全定义，但它们在搜索期间使用。 这些方法将在后续章节中概述。
Figure 10.9: 一个示例显示，即使所有行和列都是lex排序，右下子矩阵中的完整矩阵对称也可以保留。 初始矩阵（为清晰起见分为四分之一）首先通过交换第四和第六行，然后交换第一列和第三列进行转换。 结果仍然是双排序，但我们已经交换了子矩阵的第一行和第三行。 我们可以类似地交换两列。
10.5.1 Symmetry Breaking During Search (SBDS)
Backofen和Will [4,5]引入了对称排除搜索树。 Gent和Smith [51]更详细地描述了这种技术的实现，使用了“搜索过程中的对称性破坏”这个名称，但是后一个名称及其首字母缩略词“SBDS”似乎已经成为这种方法的通用名称。。 这可能有点不幸，因为在搜索过程中有许多其他方法可以打破对称性，最值得注意的是第10.5.2节中讨论的SBDD。
SBDS的基本思想是为问题添加约束，以便在从搜索决策回溯后，SBDS约束确保不允许该决策的对称等价。 这是一种动态技术，因为在我们知道正在做出什么样的搜索决定之前，我们无法添加约束。 一般而言，SBDS可以处理任何类型的搜索决策。 然而，为了简化讨论，我们将假设所有搜索决策的形式为var = val，并且SBDS的许多实现做出相同的假设。
我们将首先用一个例子说明SBDS添加的约束类型。8-Queens问题的搜索树如图10.10所示，其中SBDS添加的对称约束由 指明。解释SBDS最简单的方法是遍历树广度优先搜索，而不是实际搜索算法将探索的深度优先搜索。
- 从根开始，图10.10中搜索树中的第一个搜索决策是Q[1] = 2，即第一行中的皇后位于位置2。SBDS没有向正向决策Q[1] = 2添加约束。如果我们在根上回溯，我们可以断言Q[1]
2。从这一点开始，我们再也不想尝试任何包含任何对称等价于Q[1] = 2的状态。我们可以通过添加对称版本的Q[1]
- 在搜索的下一层，在左边，下一个搜索决策是Q[2] = 4。同样，我们没有为这个积极的决定添加任何约束。但是如果我们从这里回溯，我们断言Q[2] = 4。禁止这个决策的每个对称版本不再是正确的，因为初始搜索决策Q[1] = 2可能已经破坏了一些对称性。在本例中，Q[1] = 2排除了Q[1] = 7、Q[7] = 7、Q[2] = 1和Q[8] = 2，因为这些正方形分别位于同一行、列、对角线和对角线上。这意味着没有包含Q[1] = 2的解可能具有对称x、y、d1或d2。对于Q[1] = 2以下的这些对称性，不需要断言任何约束，在图10.10中省略了它们。
- 仍然考虑相同的节点，更复杂的情况是对称r90、r180和r270。在搜索的这一点上，我们不知道这些对称性是否适用。它们可能在未来的一些状态成立，而在另一些状态中不成立。我们不能排除，例如，
对于所有未来的状态，因为我们可能会在r90不成立的状态中丢失解，但同样，如果我们不排除它在r90成立的状态中，我们将做冗余搜索。SBDS通过添加有条件地排除
，即Q[4]
我们现在可以概括地说明SBDS添加的约束，考虑搜索中的节点，其中部分分配A将由决策var = val扩展。 对于任何问题对称性g，我们可以添加约束：
要理解此约束的合理性，请注意它等价于这几乎是微不足道的。 更重要的是，这个等式在搜索开始之前是正确的，因为它适用于任何A，var，val和g。从这个角度来看，我们可以把SBDS看作是对(在实际中)要添加的无限种约束中的哪一种进行启发式选择。SBDS的实际实现通常不会添加(10.2)的完整形式。如果我们在搜索中添加约束，从var = val的选择开始回溯，那么我们就知道A是真的，我们也知道var
val，这样就得到了更简单，但在上下文中等价的形式:
我们可以通过指出必须确保只处理不间断对称来解释这个更简单的形式，因此检查 是否仍然有效。然后，为了确保不探索与当前子树对称等价的子树，将放置
。
Backofen and Will证明了这种方法是合理的，因为它将探索整个非对称搜索空间[5]，即没有解是完全可以忽略的。Backofen和Will还表明，只要所有的对称性都正确提供，所有的对称性都会被消除，即SBDS返回的两个解不可能是等价的。
已经提供了许多SBDS的实现。到目前为止，最公开可用的是ECLiPSe[88]。在系统使用的编程语言中，这些实现总是要求约束程序员提供一个单独的函数来实现每个对称g的动作。如果一个问题有大量的对称，用户可能无法手工识别和实现太多的对称。尽管有这样的困难，SBDS还是被成功地使用了，问题包含了几千个对称[49]。我们将在10.5.4节中看到如何使用计算群理论来减轻程序员的负担。
SBDS有一些重要的实现问题。SBDS的一个特性是，它只破坏当前部分赋值中尚未破坏的对称:这避免了设置不必要的约束。当当前局部分配的对称等价与问题约束不一致时，对称性就会破坏。由于包含到目前为止设置的所有值，所以它可能很大，因此检查对称性是否完整可能会很昂贵。但是，可以注意到，如果将A扩展到下一个局部赋值A1，那么
(其中var = val是搜索树的下一个决策)。那么
。那么可以为每一个表示
是否满足的对称g构造一个布尔变量：它对于
的值是它对于
和var =
的值的结合。因此，可以增量地决定
是否成立。此外，当其中一个布尔变量的值变为false时，就知道相应的对称被永久破坏，不再需要在这个分支上考虑。
SBDS的一个问题是，当对称的数量很大时，必须描述大量的对称函数。在最坏的情况下，可能有太多的代码无法成功编译。这个困难可以通过选择与SBDS一起使用的对称函数的子集来解决。McDonald和Smith[82]探索了对称随机子集的“部分对称破坏”概念，并给出了一种算法来选择对称函数的子集，该子集启发式地破坏了大量对称。不幸的是，将该方法用于除具有小对称群的最小问题外的所有问题是不可行的。
与在搜索之前添加打破对称性的约束相比，SBDS具有一些主要的优势。首先，与lexleader方法相比，对称不需要是变量对称。其次，在每一类等价解中找到的解总是遍历搜索树中最左边的解。再次与lex-leader相反，这意味着可以使用任意变量和值排序启发式，而无需更改SBDS或提供的对称函数集。我们说SBDS“尊重”搜索使用的变量和值排序启发式。
10.5.2 Symmetry Breaking via Dominance Detection (SBDD)通过优势检测（SBDD）破坏对称性
通过优势检测对称破裂（SBDD）的方法由Focacci＆Milano [34]和Fahle，Schamberger＆Sellmann [33]独立开发。SBDD的标题来自于这些文章的后一篇，并且已经被CP社区采用为该方法的标准名称。1988年，Brown、Finkelstein和Purdom提出了类似的算法。实际上，本文将该算法的计算组理论版本描述为GAPSBDD, CP社区现在已经很熟悉这个版本(在下面的10.5.5节中进行描述)。不幸的是，Brown等人的论文虽然相当有名，但对constraints community的影响似乎很小，可能是太超前了。
Figure 10.11:用于说明SBDD的部分搜索树，以及列出与每个节点对应的搜索状态的表。
SBDD通过在搜索树中的每个节点处执行检查来操作，以查看将要探索的节点是否与已经探索的节点对称等效，并且如果是，则修剪该分支。 虽然这是一个简单的想法，但是我们需要存储一个明显的问题，即我们需要存储已经探索过的整个指数大小的树。 一个关键的想法将SBDD转变为一种空间效率高的方法。这就是说，我们只需要在完全探索过的子树的根上存储节点。我们不检查一个节点是否完全等同于我们存储的一个节点。相反，我们确定一个节点是否等价于作为存储节点之一的扩展的任何节点，即处于完全探索的子树中的节点。由于搜索已经回溯，我们必须先访问等效节点，或者由于某些其他原因推断出不需要访问它：在任何一种情况下都不需要访问对称等效节点。
与SBDS一样，SBDD基于设置变量和从变量域中删除值之间的二进制分支。 基于[34]中概述的示例，SBDD如何在实践中起作用的示例如下。 考虑三个变量v1，v2和v3的问题，这些变量受“all-different”约束的约束。 所有变量的域都是{1,2,3,4}，所有值都可以置换。 有24个问题的解决方案。图10.11显示了树搜索的一部分，假设只有一个基本的all-different的传播过程，那么深度优先搜索过程将探索该部分，以枚举所有解决方案。决策是按词典顺序选择的。节点由n：δ表示，其中n表示节点是要通过搜索过程扩展的第n个节点，δ是对节点n与其父节点之间的弧的决策的决定或否定。 该图还为每个节点n给出了从根节点到n的路径上所做的一组决策，以及对应于其状态的变量的域。在图解搜索中得到了四个解。然而，在节点7处找到的解与在节点3处找到的解是对称的。这些解是{v1 = 1, v2 = 3, v3 = 2}， {v1 = 1, v2 = 2, v3 = 3}第一个解可以通过交换对称变量v2和v3映射到第二个解。更一般地说，任何变量置换都是问题的对称性。
SBDD基于no-goods的概念。 No-goods是最大子树的根，在n之前通过深度优先搜索完全遍历。 可以通过遍历从根节点到n的路径来找到那些no-goods，如下所示。 每当路径从节点转到其右子节点时，该节点的左子节点就是no-good：在遍历给定节点的右子节点之前，深度优先搜索完全遍历该节点的左子树。 请注意，我们使用名称“no-good”，尽管我们正在搜索所有解决方案，但完全探索的树可能包含解决方案。 在这种情况下，我们仍然希望避免在子树中搜索与任何节点相对应的任何对称，包括解决方案。 在图10.11中，考虑节点4，节点3是一个no-good，节点2对于节点5和其子树中的所有节点是no-good。 节点8的no-goods是节点2和7。
Definition 10.25. No-good.
节点ν对于n是一个no-good，如果存在n的祖先na，满足ν是na的左手子，而ν不是n的祖先。
对于每个no-good，SBDD存储要与当前状态进行比较的信息。 我们使用一组决策来标记从树根到no-good的路径[99]。 我们为此写δ（n）。 图10.11中表中标有“决定”的列给出了与每个节点对应的决策信息。 我们还使用被搜索节点的状态信息。具体地说，对于域被简化为单例的所有变量vi，我们为一组对vi = ai写∆(S)。在节点8在我们的例子中,根节点的决策是δ(8)= {v1 = 1, v2 = 3},而∆(8)= {v1 = 1, v2 = 3, v3 = 4}。
Definition 10.26. Dominance
如果存在关于n的no-good v和关于的对称g，则我们说节点n被主导。 我们说ν主导n。
SBDD在概念上非常简单:它从不生成受控节点的子节点，并且排除了受控解决方案。因此，如果节点n是一个解、一个failure或一个受控节点，那么它就是一个叶子。在我们的例子中，no-good 2支配节点7。我们有δ(2)= {v1 = 1, v2 = 2}。使用对称g，交换v2和v3变量,得到∆(7)= {v1 = 1, v3 = 2，v2 = 3}的一个子集。【其实也就是说，v=2，n=7，7是被2主导的】
其他主导地位的定义是可能的：定义10.26来自[99]。 但是，如果我们知道搜索总是在其否定（var val）之前选择（var = val），我们可以*地忽略定义10.26 [34,59,102]中δ（n）中的否定决策。 例如，考虑图10.11中的否定决策v2
2∈δ（7），现在假设某个未来节点由δ（7）支配，其中v2
2被移除。我们仍然可以终止搜索，因为未来子树中的每个叶节点要么具有v2
2或v2 = 2的对称图像。如果是前者，则节点由δ（7）支配。 但是如果是后者，节点由δ（2）支配，因为相应的子树完全探索了v2 = 2并且我们有
。 研究结构的结构使得这种观察一般，所以如果首先探讨正面差异，我们可以省略支配决策中的否定决策。
[33]中对优势的最初定义是相当不同的，并且基于状态包容。 如果存在针对n的no-goods ν和对称性g使得 中的变量的域包含n中的变量的域，则节点n占主导地位。 这具有存储no-goods需要更多空间的缺点。 而且，它违背了以下直觉。由于我们希望建立这个节点上的集合是过去NG的超集，所以我们希望这个节点上的集合是大的，在NG上的集合是小的:这应该使通过优势度测试尽可能容易。另一方面，我们还希望优势检查尽可能容易实现，尽可能快地运行。因此，我们可能最好使用主导地位的定义，但这个定义要尽快失效，这可能是支持状态包容主导地位的论据。从来没有对这个问题进行过明确的研究，而且也许不可能决定回溯搜索的最佳启发式是什么。
到目前为止，我们已经掩盖的关键问题是如何执行优势检查。 SBDD算法需要一个问题特定函数Φ：（ν，n）→{false，true}如果先前的no-goods ν支配当前的部分赋值n，则产生真。对于小对称组的问题，提供Φ对程序员来说可能是比SBDS所需的少数对称函数更大的负载。 对于较大的群体，SBDD具有巨大的优势，即它的空间需求非常有限。 但是，这并不能解决时间复杂性问题。 对于每对ν和n，搜索g等于解决子图同构问题，其已知为NP完全。 虽然SBDD要求在每个节点上解决几个NP完全问题，但使用该技术已经获得了良好的结果。
似乎有三种广泛的技术来实施支配性检查。 首先，程序员可以针对特定类别的问题实施优势检查，例如社交高尔夫球手问题的实例[33]。 对此的需求是SBDD的主要问题。 编码将识别搜索树中的节点何时被另一个节点对称支配的函数可能是困难的，并且它不会在具有不同类型的对称性的不同问题之间进行概括。但是，如果能找到这样的函数，那么SBDD是一种非常有效的方法，可以打破大量的对称性。 Sellmann和Van Hentenryck创造了一种更普遍的优势检测函数[107]。这可以导致针对特定应用程序进行非常有效的解决方案优化，但是这种方法依赖于程序员的技能和洞察力，并给他们带来了相当大的负担。其次，由于它是np完全问题，可以构造一个优势问题的约束编码[99]。这特别有趣，因为它相当于在计算群理论中使用约束规划。然而，对于每一类需要求解的新问题，仍然需要构造一个特殊目的的约束问题。第三种方法是直接使用计算群理论[16,53]，我们将在10.5.5节进一步描述这一点。
SBDD的一个重要改进是注意到有时失败的优势检查会导致传播[34,33]。 假设我们的优势检查可以报告某个变量值对，如果在当前节点中设置，则会导致当前节点被控制。 然后我们可以从变量的域中删除该值并在结果上传播。 这可以执行非常有用的传播。 像往常一样，我们必须注意，产生的好处不会大于执行必要计算的成本。 需要注意的另一点是，不需要在搜索树的每个节点上进行优势检查。只要在每个叶子节点上进行检查，那么只返回非同构解。决定在何处应用检查是检查成本与结果的搜索节省之间的权衡:不幸的是，很少有人知道在这个权衡中最佳的位置。
与SBDS一样，SBDD可以显示为完整的对称破坏方法，只要正确实施优势检查即可。 也就是说，返回每个等价类的一个解决方案。 与SBDS一样，找到的解决方案是搜索树中关于变量和值排序启发式的最左边的解决方案。 因此，SBDD尊重变量排序启发式，并且可以使用动态变量排序而不更改为SBD [33]。 SBDD也适用于软CSP [11]。
Harvey[59]讨论了SBDS和SBDD之间的关系。这两种算法的不同之处在于对称性的破坏。SBDS设置了一些约束，以阻止以前在搜索中搜索到的对称等价节点被访问。另一方面，SBDD删除已经到达的节点，并发现它们与之前搜索中探索过的部分是对称的。事实上，完全有理由把它和SBDS之间的区别仅仅看作是实现上的区别。由于可接受的解决方案集在每种情况下都是相同的，所以SBDS的实现在某种意义上就是SBDD的实现，反之亦然。这种观点原则上可以是理解技术的有用方法，但存在巨大的实际差异。 SBDD在许多问题上可以胜过SBDS，因为它没有发布约束，因此没有等待大量对称破坏约束传播的开销。 它可以成功地用于具有太多对称性的问题，以使SBDS成为合适的技术。
10.5.3 Symmetry Excluding Heuristics 不包括启发式的对称性
Meseguer和Torras[84]研究了如何利用对称性来指导搜索。具体来说，它们通过在每个变量赋值时打破尽可能多的对称性，将搜索指向具有高度非对称赋值的子空间。提出的对称破缺启发式破坏了尽可能多的对称性。Meseguer和Torras进一步提出了“多样性最大化”启发式，它结合了最小域优先启发式，在一定条件下比对称破坏启发式的性能更好，并结合对称破坏启发式。在一个简单的问题上，多样性最大化启发式建立一个略小的搜索树，比最小域优先启发式，以找到所有的解决方案。在寻找第一个解决方案时，多样性最大化显然效果更好。Meseguer和Torras继续将多样性最大化启发式与no-good记录的对称值修剪结合起来。 这组no-goods的大小可能是指数级的，因此只存储和使用一个子集。 这种组合的结果相当令人失望; 在任何所遇到的问题中，包含对称值修剪并不能提供优于（单一的）多样性最大化的主要优势。
使用变量排序启发式(实际上是值排序启发式)来打破对称性是一个很有吸引力的提议，因为它没有与其他动态对称打破方法相关的计算成本。尽管Meseguer和Torras做了很多工作，但是在启发式中使用对称性的范围似乎比社区迄今为止所利用的范围要大得多。其他启发式使用对称的方法也有相当大的空间。例如，如果我们正在解决具有大量对称性的问题，我们可能只会寻找具有某种对称性的解决方案。 这排除了搜索空间的大部分内容。 一方面，这意味着搜索将是不完整的，因为负面答案并不意味着没有对称性较低的解决方案。 另一方面，我们可能会很幸运，并且可能会有这样的解决方案：如果我们拥有减少搜索的所有优势。 虽然这看起来过于乐观了，但它在实践中取得了成功[119]。
10.5.4 SBDS with Computational Group Theory
为了允许SBDS在有太多对称的情况下使用，从而允许为每个对称创建一个函数，Gent等人在ECLiPSe中使用GAP(组、算法和编程)[46]链接了[52]SBDS。GAP是一个计算代数系统，特别是计算群理论(CGT)。使用GAP或ECLiPSe没有什么基本的东西，关键是这是子系统之间的合作，以提供约束算法和计算群理论算法。ECLiPSe附带了一个用于GAP-SBDS的库。
GAP-SBDS允许描述对称组而不是其单个元素。 GAP-SBDS在一组点上运行，其中每个点对应于变量值对。 考虑点的一种方法是根据n×m数组的成员，其中n是变量的数量，m是每个变量的域的大小。 数组中的第i，第j个元素表示变量i和值j。 对称组G作用于这些n×m个点，每个点由单个整数表示。组生成器在ECLiPSe中给出，并以点的形式传递给GAP。这意味着ECLiPSe中需要将变量/值对转换为表示点的整数的函数，反之亦然。在使用GAP-SBDS系统时，这可能是错误的来源。即使没有错误，为了有效地使用系统，用户必须对CGT有一定的了解。虽然编写一组生成器就足够了，但即使这样也会使许多用户无法访问系统。然而，正如我们在第10.8节中所述，在这方面已经取得了一些进展。
GAP-SBDS算法可以根据第10.5.1节中的公式10.2来描述：在GAP-SBDS中，由GAP控制的该过程的唯一部分是g（A），其他组件由ECLiPSe控制，如在标准SBDS算法中那样。 g（A）是使用右横向链计算的，这是在搜索树中的每个节点处迭代计算的集合，作为到目前为止获得的每个右横向的笛卡尔乘积。更正式的，
被定义为
，其中
。RTchain的每个成员都是对称集的代表，它们对A∧var
val中的每个变量/值对的映射达成一致。 这意味着通过根据RTchain中的元素转换var
val，可以将对称性破坏约束置于回溯上。 然而，除了相对较小的群体外，通过遍历每一个对称来实现这一点是不可行的。为了克服这个困难，Gent等人使用了延迟评估。约束g(var
val)只在已知g(A)为真时才施加，而不是像原始SBDS中那样放置条件约束。这意味着尽管GAP-SBDS保证会破坏所有的对称性，但它可能不会像SBDS那样在搜索中尽早破坏对称性。这可能导致GAP-SBDS具有比SBDS更大的回溯计数。
在GAP-SBDS中，Gent等人创建了一个有效的SBDS实现，它可以有效地处理相对大量的对称。这将SBDS可与之一起使用的组的顺序从数千个移动到数十亿个。对称的数量限于这种比例，因为在搜索期间添加的约束的数量可能导致空间问题。 当群体成倍增长时，甚至数十亿也是一个小数字。
10.5.5 SBDD and Computational Group Theory
我们在第10.5.2节中提到，实践SBDD可能很难实现。 优势检测函数的设计可能是复杂的，并且对于具有相似类型的对称性的问题没有设计函数的一般规则。 实际上，两个“相似”的问题可能具有完全不同的支配函数; 对于一个问题，可能存在多个支配函数，其中一些比其他问题更有效地修剪。 Gent等人 [53]，开发了GAP-SBDD以通过提供通用优势检查器来解决这个问题，该检查器现在可用作ECLiPSe库。
SBDD是SBDD的一个通用版本，它使用问题的对称组，而不是单个优势检测函数。与GAP- sbds一样，GAPSBDD通过GAP和ECLiPSe之间的接口工作，并通过一组排列生成的对称组对点执行计算。GAP-SBDD通过维护failSet和pointSet来运行。 failSet对应于在搜索过程中为到达已完成子树的根而做出的积极决策所导致的一组点。pointSet表示对应于变量的点集，这些变量已被设置为当前搜索分支上的固定值（通过赋值和传播）。 如果在对称组G中存在g并且在failSet S中存在s使得 ⊆pointSet，则搜索树上的当前节点由完整子树支配。
使用树数据结构实现优势检查，该树数据结构对当前适用的所有failSet进行编码。 可以识别点A1，...，Ak和B0，...，Bk的不相交集合，与这些点相关联的failSets对于每个i是A1∪...∪Ai∪Bi。 树的右分支元素用A的元素标记，树的左边元素标记为B。树的每个节点与从根到它的路径上的标签序列相关联。优势度检查使用递归搜索执行，递归搜索遍历树，以每一种方式将关联的点序列映射到当前点的方式输入每个节点一次。这是实现在GAP使用稳定剂链。虽然本质上只是对适当的组元素进行回溯搜索，但GAP中的搜索包含了许多优化，这些优化会使原始实现[53]的速度提高几个数量级。与常规SBDD一样，可以识别除failSet的最终元素之外的所有元素都可以映射到pointSet并将它们报告回ECLiPSe的情况，因此可以从关联的变量域中删除该值。 但是，与GAP-SBDS一样，并非所有可能的值都被识别，因为这会导致运行时间过多增加。
SBDD是一种处理大对称群问题的有效方法。原则上，可以使用的组的大小是不受限制的，而且它在实际中已经用于包含1036个元素的组。然而，它并没有为显性检验的固有硬度提供灵丹妙药。这种硬度可以通过运行花费大量时间的个人优势检查来体现。此外，人们还发现细微的差异会对运行时产生巨大的影响。例如，虽然GAP-SBDD确实尊重变量排序启发式，但同一实例上的不同启发式方法可能导致时间优势检查桩的显着变化。 这意味着该方法可能缺乏鲁棒性。 然而，从非常小的输入而没有算法内容，GAP-SBDD自动构建一个完整的对称破坏工具。
10.5.6 GE-Trees
构建GE树的想法是加入动态对称破坏方法的最新想法[103]。 （GE代表“Group Equivalence”，但缩写是普遍使用的。）它与本类中的其他缩写不同，因为它本身就是一种考虑对称破缺方法的方法，而不是对称破缺方法。 GEtree被定义为一棵树，其中没有两个节点是对称等价的，并且其中，为了解决问题，对称等效节点在树中。 GE树的定义与搜索树类似：特别是，算法在构造完整树之前可以*停止，例如在找到第一个解决方案之后。 GE树的一部分意图被视为一种概念范式，用于对对称破缺技术进行分类和比较。随着搜索解决方案的进行，任何GE树构造的方法（通过定义）都会破坏所有问题的对称性。 SBDS和SBDS都可以被视为构建GE树的方法，但是lex-leader也可以使用它所需的所有约束。 仔细分析GE树的属性（通过SBDS和SBDD等不同方法构建，适用于相同的实例）可以允许现有技术的改进和扩展，甚至是新技术的开发。
在某些情况下，GE树几乎在民间传说中。 例如，考虑每种颜色无法区分的图形着色。 许多程序员已经意识到第一个节点可以任意着色。 对于第二个节点，我们只需要考虑给它相同的颜色或任意不同的颜色。 第三个节点只需要给出给予前两个节点的颜色，以及任意不同的节点。 这个过程一直持续到我们使用了所有颜色。这种直觉可以概括和形式化。 Roney-Dougal等人使用GE树范例创建一个多项式时间算法来破坏任意值对称性。 这可以被视为基于计算组理论的[64]中提出的算法的推广。它是一种特殊用途的算法，它只创建保证在树中唯一的新节点。 总的来说这很难，但是Roney-Dougal等人表明，值对称群的特殊性质可以用来非常有效地构建GE树[103]。 他们报告了这种方法与GAP-SBDD之间的实验比较，以解决仅具有值对称性的问题。 在所有情况下，发现GE树是最好的方法。 这并不奇怪：GAP-SBDD在搜索树中的每个节点处执行潜在的指数搜索，以便破坏对称性，与低阶多项式算法相比，以打破所有值对称性。
10.5.7 The STAB Method
使用稳定器（STAB）的对称性破坏，如SBDS，在搜索过程中增加了对称性破坏约束[98]。 与SBDS不同，SBDS设置约束以打破问题的所有对称性，STAB仅对对称性设置对称性破坏约束，使得当前节点处的部分赋值A保持不变。 也就是说，STAB不是破坏整个组中的对称性，而是破坏稳定器 中的对称性。 这些约束采用词典排序约束的形式。 第10.1节介绍了稳定剂。在实践中，稳定器的大小通常远小于G的大小。STAB方法相当于在每个节点A处添加以下一组约束。
这些约束消除了相对于以A为根的子树中的稳定器GA，在词典上没有最小化的所有解决方案。
Example 10.27. 考虑一个4×5矩阵模型。 为简单起见，我们将通过V引用变量矩阵，即我们用其矩阵表示来识别变量的向量：
考虑部分赋值A，其中前10个变量分配如下：
A的每个对称性由行置换和列置换定义。除了恒等置换之外，我们可以为每个对称性声明约束。 例如，让我们说明由行的置换（1 2）和列上的（2 4 3 5）组成的对称性σ的约束。矩阵W=是：
对称破坏约束是，允许赋值为A，那么就是
由于两个向量具有相同的前10个元素，因此约束可以简化为：
回到一般情况，基于相同前缀的简化在一般情况下是有效的。给定n向量V，设tail(V,n-d)为去掉V的前d个元素后得到的向量。如果A是d向量，那么约束可以简化为
应该注意的是，STAB是关于对称性破坏的不完整方法，这意味着它不仅仅返回非同构解。