跳至內容

三維匹配問題

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

三維匹配問題(3DM)是六個經典NP完全問題之一,是經典的「婚姻問題」的推廣,「婚姻問題」的提法是:有幾個未婚男子和幾個未婚女子以及一張列出雙方都表示願意結合在一起的一對對男子和女子的表格,問是否能安排幾對婚姻使得每個人都與自己願意接受的配偶結婚並且不出現重婚?

在三維匹配問題中,可以用集合對應於「三個」不同的性別,屬於。用集合中的每一個三元組對應一對這三個成員都能接受的「三方婚姻」。普通的婚姻問題可以在多項式時間內解決,而3DM是NP完全的。