这是一个可以用某种类型的暴力算法完成的问题,但我想知道是否有一些有效的方法来做到这一点.
我们假设我们有以下整数对
(1, 3), (2, 5), (4, 7), (2, 7), (10, 9)
我们想弄清楚互斥对的最大数量是多少.
通过互斥对,我的意思是它们没有任何公共整数.
例如,我们不能同时选择(2,5),(2,7),因为两个对都包含2.
在上面的例子中,4将是一个解决方案,因为我们可以选择以下互斥对:
(1, 3), (2, 5), (4, 7), (10, 9)
因此总共有4对.
我想知道是否有有效的方法这样做.
Pau*_*kin 13
您的问题等同于在图表上找到最大匹配.图形的节点是整数,您的对(a,b)是图形的边缘.匹配是一组成对的非相邻边,这相当于说同一个整数不会出现在两个边上.
该问题的多项式时间解决方案是Blossom算法,也称为Edmond算法.在这里将答案中的细节包含在内是相当复杂的.