三维匹配问题

此條目需要精通或熟悉计算机科学、数学的编者参与及协助编辑。 (2021年9月22日) 請邀請適合的人士改善本条目。更多的細節與詳情請參见討論頁。 另見其他需要计算机科学專家關注的頁面。

此條目没有列出任何参考或来源。 (2012年11月2日) 維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。

三維匹配（縮寫3DM）是六个经典NP完全问题之一，是经典穩定婚姻問題的推广，婚姻问题是：有几个未婚男子和几个未婚女子以及一张列出双方都表示愿意结合在一起的一对对男子和女子的表格，问是否能安排几对婚姻使得每个人都与自己愿意接受的配偶结婚并且不出现重婚？

在三维匹配问题中，可以用集合${\displaystyle W}$，${\displaystyle X}$和${\displaystyle Y}$对应于“三个”不同的性别，${\displaystyle M}$属于${\displaystyle W*X*Y}$。用集合${\displaystyle M}$中的每一个三元组对应一对这三个成员都能接受的“三方婚姻”。普通的婚姻问题可以在多项式时间内解决，而3DM是NP完全的。

在數學學科的圖論中，三維匹配是二分圖匹配（也稱為二維匹配）推廣到三方超圖，它由超邊組成，每個超邊包含 3 個頂點（而不是普通圖中包含 2 個頂點的邊）。

三維匹配是最早證明為NP困難之一的問題。

設 X、Y 和 Z 為有限集合，並設 T 為 X × Y × Z 的子集。也就是說，T 由三元組 (x, y, z) 組成，其中 x ∈ X，y ∈ Y，且 z ∈ Z。現在，如果以下條件成立，則 M ⊆ T 是一個三維匹配：對於任何兩個不同的三元組 (x₁, y₁, z₁) ∈ M 和 (x₂, y₂, z₂) ∈ M，我們有 x₁ ≠ x₂，y₁ ≠ y₂，且 z₁ ≠ z₂。

右圖說明了三維匹配。集合 X 用紅色點標記，Y 用藍色點標記，Z 用綠色點標記。圖 (a) 顯示了集合 T（灰色區域）。圖 (b) 顯示了 |M| = 2 的三維匹配 M，圖 (c) 顯示了 |M| = 3 的三維匹配 M。

圖 (c) 中說明的匹配 M 是一個「最大三維匹配」，即它最大化 |M|。圖 (b)–(c) 中說明的匹配是「極大三維匹配」，即它們不能通過添加來自 T 的更多元素來擴展。

可以用完全類似的方式定義「二維匹配」。設 X 和 Y 為有限集合，並設 T 為 X × Y 的子集。現在，如果以下條件成立，則 M ⊆ T 是一個二維匹配：對於任何兩個不同的配對 (x₁, y₁) ∈ M 和 (x₂, y₂) ∈ M，我們有 x₁ ≠ x₂ 且 y₁ ≠ y₂。

在二維匹配的情況下，集合 T 可以解釋為二分圖 G = (X, Y, T) 中邊的集合；T 中的每條邊都將 X 中的一個頂點連接到 Y 中的一個頂點。然後，二維匹配是圖 G 中的一個匹配，即一組成對非相鄰的邊。

因此，三維匹配可以解釋為匹配對超圖的推廣：集合 X、Y 和 Z 包含頂點，T 的每個元素都是一條超邊，集合 M 由成對非相鄰的邊組成（沒有共同頂點的邊）。在二維匹配的情況下，我們有 Y = Z。

三維匹配是Set packing的一個特例：我們可以將 T 的每個元素 (x, y, z) 解釋為 X ∪ Y ∪ Z 的子集 {x, y, z}；那麼，三維匹配 M 由成對不相交的子集組成。

在計算複雜性理論中，三維匹配是以下判定問題的名稱：給定一個集合 T 和一個整數 k，判斷是否存在一個三維匹配 M ⊆ T，使得 |M| ≥ k。

這個判定問題已知是NP完全的；是卡普的二十一個NP-完全問題之一。^[1] 即使在 k = |X| = |Y| = |Z| 且每個元素最多包含在 3 個集合中，也就是說，當我們想要一個 3-正則超圖中的完美匹配時，它也是 NP 完全的。^[1][2][3] 在這種情況下，三維匹配不僅是一個Set packing，而且還是一個精確覆蓋：集合 M 恰好覆蓋 X、Y 和 Z 的每個元素一次。^[4] 這個證明是通過從3SAT簡化而來的。給定一個 3SAT 實例，我們構造一個 3DM 實例如下：^[2][5]

對於每個變量 x_i，都有一個形狀像輪子的「變量 gadget」。它由重疊的三元組組成。三元組的數量是 x_i 在公式中出現次數的兩倍。恰好有兩種方法可以覆蓋 gadget 中的所有頂點：一種是選擇所有偶數索引的三元組，另一種是選擇所有奇數索引的三元組。這兩種方法分別對應於將 x_i 設置為「真」或「假」。 「真」選擇在每個奇數索引的三元組中恰好留下一個未覆蓋的頂點，而「假」選擇在每個偶數索引的三元組中恰好留下一個未覆蓋的頂點。

對於每個子句 x_i u x_j u x_k，都有一個形狀像玫瑰的「子句 gadget」。它由三個重疊的三元組組成，每個子句中的每個變量一個。它可以被覆蓋，當且僅當至少一個節點被變量 gadget 的選擇留下未覆蓋。

由於可能留下兩個或多個未覆蓋的節點，我們還需要一個「垃圾收集 gadget」。它的形狀像一朵更大的玫瑰。它由幾個重疊的三元組組成，每個變量 gadget 中可能留下的每個未覆蓋的頂點一個。此類 gadget 的數量被確定，以便只有在存在令人滿意的分配時才能完全覆蓋它們。

存在用於求解稠密超圖中 3DM 的多項式時間算法。^[6][7] 存在用於求解稠密超圖中的3DM的多主題的時間間隔演算法。 卡爾賓斯基, 魯欽斯基 & 希曼斯卡 (2009) harvtxt模板錯誤: 無指向目標: CITEREF卡爾賓斯基魯欽斯基希曼斯卡2009 (幫助) Keevash, Knox & Mycroft (2013)

「最大三維匹配」是最大的三維匹配。在計算複雜性理論中，這也是以下優化問題的名稱：給定一個集合 T，找到一個最大化 |M| 的三維匹配 M ⊆ T。

由於上面描述的判定問題是 NP 完全的，因此這個優化問題是 NP困難 的，因此似乎沒有多項式時間算法可以找到最大三維匹配。但是，存在有效率的多項式時間算法可以找到最大二分圖匹配（最大二維匹配），例如霍普克羅夫特-卡普算法。

對於三維匹配，有一個非常簡單的多項式時間 3-近似算法：找到任何極大三維匹配。^[8] 就像極大匹配在最大匹配的 2 倍因子內一樣，^[9] 極大三維匹配在最大三維匹配的 3 倍因子內。

對於任何常數 ε > 0，都有一個用於三維匹配的多項式時間 (4/3 + ε)-近似算法。^[10]

但是，獲得更好的近似因子可能很難：這個問題是 APX完全 的，也就是說，很難在某個常數內近似。^[11][12][8]

對於最大 3-d 匹配，很難實現 95/94 的近似因子，對於最大 4-d 匹配，很難實現 48/47 的近似因子。即使限制為每個元素恰好出現兩次的實例，這種困難仍然存在。^[13]

在大規模並行通信模型中，存在各種用於 3-d 匹配的算法。^[14]

• NP完全問題列表
• 彩虹獨立集 – 可以從三維匹配簡化的一個問題。
• 數值三維匹配

• Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, 2003 .
• Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard, Maximum 3-dimensional matching, A Compendium of NP Optimization Problems, 2000 .
• Kann, Viggo, Maximum bounded 3-dimensional matching is MAX SNP-complete, Information Processing Letters, 1991, 37 (1): 27–35, doi:10.1016/0020-0190(91)90246-E .
• Karp, Richard M., Reducibility among combinatorial problems, Miller, Raymond E.; Thatcher, James W. (编), Complexity of Computer Computations, Plenum: 85–103, 1972 .
• Karpinski, Marek; Rucinski, Andrzej; Szymanska, Edyta, The Complexity of Perfect Matching Problems on Dense Hypergraphs, ISAAC '09 Proceedings of the 20th International Symposium on Algorithms, Lecture Notes in Computer Science, 2009, 5878: 626–636, ISBN 978-3-642-10630-9, doi:10.1007/978-3-642-10631-6_64 .
• Keevash, Peter; Knox, Fiachra; Mycroft, Richard, Polynomial-time perfect matchings in dense hypergraphs, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing: 311–320, 2013, Bibcode:2013arXiv1307.2608K, ISBN 9781450320290, S2CID 5393523, arXiv:1307.2608 , doi:10.1145/2488608.2488647 .
• Papadimitriou, Christos H.; Steiglitz, Kenneth, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998 .

一個用 JavaScript 實現的互動式視覺化