标签：#匹配 (圖論)

三维匹配问题

三維匹配（縮寫3DM）是六个经典NP完全问题之一，是经典穩定婚姻問題的推广，婚姻问题是：有几个未婚男子和几个未婚女子以及一张列出双方都表示愿意结合在一起的一对对男子和女子的表格，问是否能安排几对婚姻使得每个人都与自己愿意接受的配偶结婚并且不出现重婚？ 在三维匹配问题中，可以用集合W，X和Y对应于“三个”不同的性别，M属于WXY。用集合M中的每一个三元组对应一对这三个成员都能接受的“三方婚姻”。普通的婚姻问题可以在多项式时间内解决，而3D…