Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

algorithm - 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.

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

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)  

thus 4 maximum pairs total.

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

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...