約束中的對稱性一直很重要，但近年來已成為一個主要的研究領域。 約束編程中的一個關鍵問題早已被認識到：搜索可以一遍又一遍地重新審視等效狀態。 原則上，已經通過許多不同的技術解決了該問題。 在我們寫作時，由于兩個原因，研究仍然非常活躍。 首先，在對稱排除已知的技術的實際應用中存在許多困難，并且克服這些仍然是重要的研究問題。 其次，到目前為止，該領域取得的成功鼓勵研究人員找到利用對稱性的新方法。在本章中，我們將討論這些問題，以及已經構思出的對稱排除方法的細節。

圖10.1:找到一個包含9個皇后和每種顏色的一個國王的象棋位置的難題的解決方案，規則是沒有任何棋子與任何相反顏色的皇后在同一條線上(行、列或對角線)。對于對稱性，解是唯一的。

為了說明對稱性的含義，我們考慮圖10.1所示的國際象棋難題。 這個難題的解決方案是獨特的“達到對稱性”[115]，但在這種情況下，對稱性是什么意思呢？ “對稱性”是指一種改變碎片位置的操作，但當且僅當起始狀態發生時，其末端狀態服從所有約束。給定一個滿足所有約束條件的解，我們可以通過對第一個解應用任何對稱性來找到一個新的解。例如，給定圖中謎題的解決方案，我們可以交換每個部分的顏色，因此黑色皇后出現在白色皇后出現的地方，反之亦然。同樣，我們可以將棋盤旋轉90度的任意倍數，以得到一個新的解。最后，我們可以反映棋盤的水平軸，垂直軸和兩個對角線軸。由于這些對稱可以組合在一起，所以有16種可用的對稱，包括將所有東西放在原地的標識操作。

為什么對稱性很重要？主要原因是我們可以利用對稱性來減少解決問題所需的搜索量。這具有巨大的潛在利益。例如，假設我們搜索國際象棋拼圖的解決方案，第一個任務是在左上角放置一個白皇后。事實上，搜索決定并不是真正嘗試左上角的白色女王，而是決定嘗試所有可能的解決方案，在棋盤的任何角落都有任意顏色的女王。由于有16個對稱性，我們有可能將搜索減少16倍。對稱性的重要性的第二個原因是許多約束問題在它們中具有對稱性。此外，建模行為可以引入對稱性。例如，如果我們使用每個女王的變量為上面的國際象棋謎題建模，范圍從1到64表示其位置，則每個解決方案將有個對稱版本，因為每組皇后可以被置換并且交換了兩套。然而，這種模型對于有效傳播和啟發式可能是理想的，因此我們希望能夠有效地處理其對稱性。

對稱在約束規劃中最重要的應用是為了減少搜索而進行的“對稱性破壞”。對稱性破壞的目的絕不是探索兩個相互對稱的搜索狀態，因為我們知道這兩種情況下的結果必須是相同的。在約束規劃中，確定對稱性破壞的三種主要方法是很常見的。第一種方法是重新構造問題，使其具有較少的對稱性，甚至完全沒有對稱性。第二種方法是在搜索開始之前添加打破對稱性的約束，從而使一些對稱解不可接受，同時在每個對稱等價類中至少保留一個解。最后一種方法是在搜索過程中動態打破對稱性，對搜索過程進行適當的調整。這種分類是簡單的，因為每種方法都有巨大的差異，并且方法之間有很大的共性。然而，這是一個非常有用的非正式分類，我們將圍繞它進行討論。

在本章的其余部分，我們希望回答以下問題：我們如何實現可能的搜索減少？ 有哪些一般方法，涉及哪些權衡？ 我們怎樣才能讓日常約束程序員盡可能地使用它？ 還有哪些研究方向？

10.1 Symmetries and Group Theory

數學中對對稱性的研究叫做群論。在閱讀這一章時，我們假設沒有小組理論的背景知識，所以我們將介紹所有我們需要的概念。我們不為在這個早期階段強調群理論的作用而道歉，因為它對于理解對稱在約束規劃中的作用是至關重要的。我們只能非常簡短地介紹關鍵概念，因此這一部分應該只作為對數學中最大的研究領域之一的最簡單的介紹。幸運的是，對于大多數約束程序員來說，一點關于組理論的知識實際上就足以理解到目前為止所做的大部分工作。遺憾的是，數學家對群理論的介紹常常想當然地認為它與對稱性有關，因此我們將花一點時間來解釋這一點。我們將通過排列來解釋群體理論。首先，沒有任何東西丟失，因為每個組都可以表示為一組排列。其次，它使我們很容易理解作為一個組元素的對稱性和作為一個動作的對稱性之間的聯系。我們將強調群體動作的概念，因為這表達了對稱性如何改變搜索狀態，這是我們的主要興趣所在。

Example 10.1. Chessboard Symmetries 例10.1。棋盤上的對稱性

考慮一個3×3棋盤。我們用數字1到9標記9個正方形。這些數字是會被對稱移動的點。棋盤有八種自然的對稱性。我們總是包含恒等對稱，這使得每一點都是這樣。標識顯示在圖10.2的左上角。然后，我們可以順時針方向旋轉棋盤90度、180度和270度。這些點的最終位置顯示在圖10.2頂部行的其余部分中。最后，在垂直軸上有反射，在水平軸上有反射，在兩個主要的對角線軸上有反射，這些都顯示在下面一行。

對稱性和排列之間的聯系可以非常簡單地看到。置換是一個集合和它自己之間的一一對應。每一種對稱都定義了一組點的排列。寫排列的一個簡單方法是用柯西形式。柯西式是兩行數。第一行是按升序排列的元素的完整集合，這些元素由置換操作完成。第二行顯示頂部行中的每個元素映射到的編號。例如，恒等對稱和置換將每個點映射到自身，如圖10.3左上角的Cauchy形式所示。90度的旋轉對稱在右上角的柯西式中顯示出來。我們看到點1在r90后被7所取代，7依次被9所取代，9被3所取代，3被1所取代。這是一個循環(1 7 9 3)另一個循環是(2 4 8 6)還有一個平凡的循環只包含(5)。一般來說，群理論家不使用柯西形式，他們更喜歡一種基于排列定義的循環集的符號。

圖10.3:表示棋盤對稱性的排列，以柯西形式書寫

Example 10.2. Cyclic form?循環形式

上面的對稱r90包含循環(1 3 9 7)、(2 4 6 8)和(5)。r90的循環形式是(1 3 9 7)(2 4 6 8)(5)，盡管可以省略長度為1的循環。置換將每個點映射到它所在循環的后續元素，但最后一個元素映射到第一個元素，沒有循環中的一個點映射到它自己。在循環形式中，我們可以編寫3×3棋盤的對稱性，如圖10.4所示。

圖10.4：表示棋盤對稱性的排列，以循環形式書寫

比較圖10.3和10.4表明，循環形式更加簡潔，特別是當許多點不被置換移動時。 一個缺點是它沒有準確定義排列作用的點集：例如，上面的排列都沒有移動點5，因此數字5沒有出現在圖10.4中。同樣，相同的排列也可以用許多不同的方式寫下來，因為循環可以以任何順序出現，并且每個循環可以從其中的任何元素開始。然而，循環形式對于人們來說是如此自然，以至于計算群體理論系統GAP將其作為排列的輸入語言，盡管它隨后會在內部將其轉換為更高效的計算形式。

兩種形式的寫下排列都可以很容易地看出置換如何作用于一個點。 一般來說，如果p是一個點而g是一個排列，那么我們將寫來記下p被移動到g下的點。 例如， = 7， = 3。我們經常以自然的方式將這種表示法擴展到包含點的其他數據結構集。例如，我們有?= {, , } ={7, 1, 6} ={1, 6, 7}:最后兩項之間的等價僅僅是因為集合是無序的。

關于排列的某些關鍵事實提供了它們與群體之間的聯系。 我們將解釋這些，然后提供一個組的基本定義。 首先，很容易計算出兩種排列的組合，對于排列f和g，我們將寫為f?g。f?g的結果是將每個點先移到f，然后移到g，通過移動該點的結果來計算的。 也就是說，對于任何點p，。 重要的是要注意動作的順序，即當我們寫f?g時我們做f然后g，這是與sin（cos（x））等函數組合相比的另一種方式。 由于f和g都是一對一的對應關系，因此它們的組成也是如此，因此兩種排列的組合是另一種排列。 我們可以逐點計算出構圖：我們只需計算1移動到f下的值，然后將結果移到g下，然后重復每個點。

相當于是將id先轉90度，再對x軸軸對稱翻轉，得到的3*3棋盤結果

我們已經描述了恒等置換的存在，我們稱之為id。 這可以定義為任何一組點的空循環集。 對于任何排列f，存在逆置換，使得。 這很容易計算：在循環形式中，我們只是顛倒每個循環的順序; 在Cauchy形式中，我們交換兩行，然后重新排序列，以便第一行按數字順序排列。

最后，我們注意到排列的組合是滿足結合律的。 也就是說，f?（g?h）=（f?g）?h。 這個事實的真相依賴于排列組成的定義，即g?h對每個點給出與應用g然后h相同的結果。 因此，例如，是將f應用于7，然后g，然后h：但這與完全相同 也可以通過對結果應用f得到7，g，結果為h。 我們現在最終提出了定義一個群體group的公理。

Definition 10.5. Group Axioms 組是一個非空集G，具有組合運算符?，這樣：
?- ?G在?下關閉。 也就是說，對于所有g，h∈G，g?h∈G;?
?- 有一個身份id∈G。也就是說，對于所有g∈G，g?id=id?g= g;?
?- ?G的每個元素g具有逆g-1，使得
?- ?是滿足結合律的。 也就是說，對于所有f，g，h∈G，（f?g）?h=f?（g?h）。

Definition 10.6. Order of a Group?組G的順序是集合G中的元素的數量。它由 |G| 表示。

Example 10.7.?棋盤{id，x，y，d1，d2，r90，r180，r270}的對稱組形成一組8階。我們有r90-1 = r270，r270-1 = r90，以及所有其他元素 g是自反的，即g-1 = g。 棋盤組是非交換的，因為d1?r90= x但是r90?d1= y。在約束規劃的大多數應用中，組不是可交換的。注意，我們省略了與組相關的操作，即置換組合（permutation composition）:這通常在不會引起混淆的地方進行。

注意，我們對組的(完全標準的)定義沒有提到組元素所做的操作。理解組元素可以以兩種不同的方式運行是非常重要的。首先，組元素(即對稱)在其作用的點上有作用。在棋盤的例子中，點數是1…9，我們用??表示g作用于p點的結果。這就是我們到目前為止所強調的。其次，group元素g由組合操作符操作，以排列組中其他元素的值。也就是說，f?g給出了另一個組元素。 后一種操作是群論中大多數研究的重點。 相反，正是群體行為對我們來說更為重要，因為正是這個動作代表了約束問題中變量和值的對稱性。

對于排列，操作?是如上所述的組合。 我們已經證明存在一個同一性排列，所有排列都有逆，并且排列的組合是相關的。 最后的條件是關閉。 我們已經證明兩種排列的組成是另一種排列。然而，對于形成組的一組排列，我們必須具有任何兩個排列的組合在集合中。 這取決于我們選擇的排列集。 有一種簡單的方法可以保證閉包，即采取一組排列并產生所有排列，這些排列是由任意組合而產生的。

Definition 10.8. The Generators of a Group 群的生成器

設S是可以由組操作?組成的任何元素集（例如，排列）（例如，置換組合）。 如果G的每個元素都可以寫成S中元素的乘積，并且S的任何元素序列的每個乘積都在G中，則集合S生成G.集合S被稱為G的一組生成符，我們寫G =<S>。

Example 10.9. Generators of Chessboard Symmetries

棋盤對稱性由{r90，d1}生成，因為：

給定任意一組排列，我們總是可以處理由該集合生成的組，因為根據定義它是封閉的。查找并使用生成器是表示組的一種非常重要的方法。如果一個組中有|G|個元素，則總是有一個大小為或更小的生成集。

Definition 10.10. Subgroup 子群

G組的子組H是G的子集，H本身就是一個組，具有與G相同的組合運算符。兩個簡單且通用的子組示例是G始終是G的子組，{id}也是如此。

Example 10.11.?棋盤對稱子組：
集合{id，r90，r180，r270}形成順序4的子組。從例10.1可以看出，這可以由元素r90生成。

【陪集coset】

給定G組的子組H和G的元素g，（右）陪集H?g是元素集{h?g|h∈H}。 用不同元素構造的G中的兩個H的陪集是不相交的或相同的，即因此，H的陪集cosets分割了G的元素。此外，H的所有陪集都具有大小| H |。陪集數被稱為G中的H的索引，并且由| G：H |表示。 如果從H的每個陪集中選擇一個元素，則形成一組陪集代表，該集合是正確的橫向。 G組是通過組合H的元素與這些陪集代表形成的陪集的結合。

Example 10.12. Cosets of Chessboard Symmetries

G組是全部的棋盤對稱可能，H組是棋盤的旋轉對稱。那么H的兩個coset是:{id, r90, r180, r270}和{d1, x, d2, y}，其中H = H?id和H = H?d1。一組coset表示是{id, d1}，但是總共有16個可能的coset表示集，由每個coset中的一個元素組成。

G中一個點的軌道是該點可以通過G的元素映射到的不同點的集合。

Definition 10.13. Orbit

G中的點δ的軌道是集合

Example 10.14. Orbits of Points on Chessboard

回顧實例10.1中給出的棋盤對稱圖，可以計算給定點的軌道。 例如，1的軌道是{1,3,7,9}，因為，并且因為所有其他組元素將1映射到這些點中的一個。

點的穩定器是固定或穩定該點的一組元素。 它指示哪些元素可以應用于某個點，這不會導致該點的值移動。

Definition 10.15. Stabiliser 穩定器

設G是作用于（尤其）點β的置換群。 G中β的穩定器定義為： 穩定器Gβ是G組的亞組。

Example 10.16. Stabilisers of chessboard symmetries

從棋盤對稱性的圖10.2中，可以識別任何給定點的穩定器。 例如，點1的穩定器是，因為這些元素將點1映射回自身。 點5的穩定器是整個組G，即，因為沒有一個對稱點移動點5。

10.1.1 Group Theory in Constraint Programming

每當約束問題具有對稱性時，我們就可以構造一個組來表示問題中的對稱性。 該組的元素置換點，取決于特定問題的對稱性。 組的元素作用的點通常是變量值對。

Example 10.17.?表示圖10.1中的國際象棋問題的對稱性

• 變量Variables - ?CSP具有與棋盤方塊對應的個變量，表示變量需要個標簽
• 值Values - 棋盤的每個方格有5個可能的值：白色女王，黑色女王，白色女王，黑色女王，或者是空的。
• 變量值Variable-Value - 變量有個可能的標簽，變量有5個可能的標簽，表示變量值對需要5個點。

有一組特別重要的排列。 n個對象的所有排列的集合Sn形成一個組，在n個元素上稱為對稱組。 組Sn的大小為n！。 這個組經常出現在約束中，因為我們經常有n個彼此無法區分的對象，因此它們被Sn作用。它也以組合形式出現。例如，我們將看到一個常見的情況是一個二維的變量矩陣，我們可以自由地排列m列(保留行)和n行(保留列)。因為我們可以先排列列，然后是行，所以我們有一個組合稱為直接乘積Sm×Sn。

10.1.2 Computational Group Theory

計算組理論是數學和計算機科學領域的一個大型跨學科研究領域。 巴特勒寫了一本關于這個領域使用的算法的教科書[17]和霍爾特等人。 [65]最近寫了一本計算組理論手冊。 計算組理論有兩個主要的包，稱為GAP [46]和Magma [14]。使用對稱性的約束程序員通常可以使用GAP或Magma作為外部函數。 但是，如果不可用或不合適，理解計算組理論算法很重要。 最重要的算法是Schier Sims算法，我們給出了一個非常簡短的概述。

利用Schreier Sims算法[108]構造了一個穩定鏈G0, G1，…， Gn如下:

'

根據定義，

Schreier Sims算法還計算了一組coset表示Ui。這些是Gi中i的軌道:Ui = iGi。

根據定義，Ui是一組值，i被G中的所有對稱性映射到這些值，這些對稱性至少為0…(i - 1)不變。

在約束編程術語中，穩定器可能是上面概述的最有用的概念。 變量/值對的穩定器顯示在搜索期間將該值分配給給定變量后未對稱的對稱性。 關于GAP-SBDS，在10.5.4節中對此進行了更詳細的解釋。 穩定器鏈表示在搜索期間分配了變量集合之后保留的對稱性。

?

?

?

?

?

?

總結

以上是生活随笔為你收集整理的Chapter 10 Symmetry in Constraint Programming 10.1 Symmetries and Group Theory的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。