有效地选择互斥对 [英] Choosing mutually exclusive pairs efficiently

问题描述

这是一个问题，可能与某些类型的蛮力算法来完成，但我不知道是否有这样做的一些有效的方法。

This is a problem that could be done with some type of brute-force algorithm, but I was wondering if there are some efficient ways of doing this.

假设我们有以下的整数对

Let's assume that we have the following pairs of integers

 (1, 3), (2, 5), (4, 7), (2, 7), (10, 9)

我们想弄清楚是互斥对的最大数目。

We want to figure out what is the maximum number of mutually exclusive pairs.

通过相互排斥的一对，我的意思是对使得它们不具有任何 常见的整数。

By mutually exclusive pair, I mean pairs such that they do not have any common integer.

例如，我们不能选择两者（2,5），（2,7），因为两对含有2。

For instance, we cannot choose both (2, 5), (2, 7) since both pairs contain 2.

在上述情况下，4。将溶液作为我们可以选择以下互斥对

In the above case, 4 would be a solution as we can choose the following mutually exclusive pairs:

      (1, 3), (2, 5), (4, 7), (10, 9)  

因此​​4最大的双总和。

thus 4 maximum pairs total.

我想知道是否有这样做的有效方法。

I was wondering if there are efficient ways of doing so.

推荐答案

您的问题就相当于找到一个最大匹配上的图表。您的图的节点是整数，​​和你的对（A，B）是该图的边。的匹配是一套成对的非相邻边缘的，这等于说相同的整数不会出现在两个边缘。

Your question is equivalent to finding a maximum matching on a graph. The nodes of your graph are integers, and your pairs (a, b) are edges of the graph. A matching is a set of pairwise non-adjacent edges, which is equivalent to saying the same integer doesn't appear in two edges.

一个多项式时间解决这个问题是花算法也被称为爱德蒙算法。这是相当过于复杂，包括的细节在这里答案。

A polynomial time solution to this problem is the Blossom algorithm also known as Edmond's algorithm. It's rather too complicated to include the details in the answer here.

这篇关于有效地选择互斥对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！