三維匹配問題(3DM)是六個經典NP完全問題之一,是經典的「婚姻問題」的推廣,「婚姻問題」的提法是:有幾個未婚男子和幾個未婚女子以及一張列出雙方都表示願意結合在一起的一對對男子和女子的表格,問是否能安排幾對婚姻使得每個人都與自己願意接受的配偶結婚並且不出現重婚?
此條目沒有列出任何參考或來源。 (2012年11月2日) |
在三維匹配問題中,可以用集合,和對應於「三個」不同的性別,屬於。用集合中的每一個三元組對應一對這三個成員都能接受的「三方婚姻」。普通的婚姻問題可以在多項式時間內解決,而3DM是NP完全的。
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.