三维匹配问题(3DM)是六个经典NP完全问题之一,是经典的“婚姻问题”的推广,“婚姻问题”的提法是:有几个未婚男子和几个未婚女子以及一张列出双方都表示愿意结合在一起的一对对男子和女子的表格,问是否能安排几对婚姻使得每个人都与自己愿意接受的配偶结婚并且不出现重婚?
此条目没有列出任何参考或来源。 (2012年11月2日) |
在三维匹配问题中,可以用集合,和对应于“三个”不同的性别,属于。用集合中的每一个三元组对应一对这三个成员都能接受的“三方婚姻”。普通的婚姻问题可以在多项式时间内解决,而3DM是NP完全的。
Remove ads
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.
Remove ads