如何编写高效的配对匹配算法？

Question

我需要一种算法的帮助，该算法可以有效地将人们分成两对，并确保不会重复之前的两对。

例如，假设我们有 10 位候选人；

candidates = [0,1,2,3,4,5,6,7,8,9]

并且假设我们有一个以前匹配的字典，这样每个键值对，即 candidate:matches 代表一个候选人和到目前为止已经配对的候选人数组；

prev_matches = {0: [6, 5, 1, 2], 1: [4, 9, 0, 7], 2: [9, 8, 6, 0], 3: [5, 4, 8, 9], 4: [1, 3, 9, 6], 5: [3, 0, 7, 8], 6: [0, 7, 2, 4], 7: [8, 6, 5, 1], 8: [7, 2, 3, 5], 9: [2, 1, 4, 3]}

所以对于Candidate 0，他们首先与Candidate 6配对，在随后的配对轮次中，他们分别与Candidate 5、Candidate 1、[=配对18=]。字典中的其他键值对也是如此。

已经进行了四轮比赛，如prev_matches中所有比赛的长度所示。我如何编写一个算法来创建第五、第六...第 n（最多 numberOfCandidates - 1）轮匹配，以便候选人没有重复对？

因此 Candidate 0 不能再与 Candidate 6、Candidate 5、Candidate 1 和 Candidate 2 配对。在可能的第五轮比赛之后，我们可以 prev_matches 这样：

prev_matches: {0: [6, 5, 1, 2, 3], 1: [4, 9, 0, 7, 2], 2: [9, 8, 6, 0, 1], 3: [5, 4, 8, 9, 0], 4: [1, 3, 9, 6, 7], 5: [3, 0, 7, 8, 9], 6: [0, 7, 2, 4, 8], 7: [8, 6, 5, 1, 4], 8: [7, 2, 3, 5, 8], 9: [2, 1, 4, 3, 5]}.

这是我尝试过的一个天真的解决方案：

def make_match(prev_matches):
    paired_candidates = set()
    for candidate, matches in prev_matches.items():
        i = 0
        while i < 10:
            if i != candidate and i not in matches and i not in paired_candidates and candidate not in paired_candidates:
                prev_matches[candidate].append(i)
                prev_matches[i].append(candidate)
                paired_candidates.add(candidate)
                paired_candidates.add(i)
                break
            i += 1
    return prev_matches

它在第五轮工作并返回以下内容：

prev_matches = {0: [6, 5, 1, 2, 3], 1: [4, 9, 0, 7, 2], 2: [9, 8, 6 0, 1], 3: [5, 4, 8, 9, 0], 4: [1, 3, 9, 6, 5], 5: [3, 0, 7, 8, 4], 6: [0, 7, 2, 4, 8], 7: [8, 6, 5, 1, 9], 8: [7, 2, 3, 5, 6], 9: [2, 1, 4, 3, 7]}

然而，对于第六轮，由于一些候选人（7 和 8）找不到有效的配对，它失败了：

prev_matches = {0: [6, 5, 1, 2, 3, 4], 1: [4, 9, 0, 7, 2, 3], 2: [9, 8, 6, 0, 1, 5], 3: [5, 4, 8, 9, 0, 1], 4: [1, 3, 9, 6, 5, 0], 5: [3, 0, 7, 8, 4, 2], 6: [0, 7, 2, 4, 8, 9], 7: [8, 6, 5, 1, 9], 8: [7, 2, 3, 5, 6], 9: [2, 1, 4, 3, 7, 6]}

因此，它既不是可靠的，也不是可接受的解决方案。

我正在考虑将其视为一个回溯问题，这样我就会探索所有可能的配对，直到我在第 n 轮之后找到一个完全可接受且有效的解决方案。但是这里的问题是如何让它高效地工作。

如果能得到任何帮助，我将不胜感激。

Answer 1

使用模块 networkx 计算图中最大匹配的解决方案：

from networkx import Graph
from networkx.algorithms.matching import max_weight_matching, is_perfect_matching

def next_rounds(candidates, prev_matches):
    G = Graph()
    G.add_nodes_from(candidates)
    G.add_edges_from((u,v) for u,p in prev_matches.items() for v in candidates.difference(p).difference({u}))
    m = max_weight_matching(G)
    while is_perfect_matching(G, m):
        yield m
        G.remove_edges_from(m)
        m = max_weight_matching(G)

for r in next_rounds({0,1,2,3,4,5,6,7,8,9},
                     {0: [6, 5, 1, 2], 1: [4, 9, 0, 7], 2: [9, 8, 6, 0], 3: [5, 4, 8, 9], 4: [1, 3, 9, 6],  5: [3, 0, 7, 8], 6: [0, 7, 2, 4], 7: [8, 6, 5, 1], 8: [7, 2, 3, 5], 9: [2, 1, 4, 3]}):
    print(r)

输出：

{(2, 7), (8, 1), (0, 9), (4, 5), (3, 6)}
{(2, 4), (3, 7), (8, 0), (9, 5), (1, 6)}
{(0, 7), (8, 4), (1, 5), (9, 6), (2, 3)}
{(9, 7), (0, 4), (8, 6), (2, 5), (1, 3)}
{(1, 2), (0, 3), (8, 9), (5, 6), (4, 7)}

如何编写高效的配对匹配算法？

How do I write an efficient Pair Matching algorithm?

python

algorithm

backtracking