如何高效生成中国邮路问题中奇顶点的所有完美匹配？

核心递归生成算法 #

这是生成所有完美匹配的经典方法，逻辑清晰且能覆盖所有可能的配对组合：

• 固定顶点集中的第一个顶点，遍历剩余所有顶点，依次与它配对
• 每确定一对顶点后，从原集合中移除这两个顶点，递归处理剩下的顶点子集
• 当顶点子集为空时，记录当前的完整配对组合

伪代码示例：

def generate_perfect_matches(vertices):
    if not vertices:
        yield []
        return
    first_vertex = vertices[0]
    for idx in range(1, len(vertices)):
        current_pair = (first_vertex, vertices[idx])
        remaining_vertices = vertices[1:idx] + vertices[idx+1:]
        for sub_match in generate_perfect_matches(remaining_vertices):
            yield [current_pair] + sub_match

关键优化点 #

• 避免重复配对：通过固定第一个顶点的配对对象，能自然避免生成重复的匹配组合（比如将(a,b)和(b,a)视为同一配对，减少冗余计算）
• 规模限制提醒：完美匹配的总数是双阶乘 (n-1)!! = (n-1)*(n-3)*...*1，当n=12时就有10395种组合，n=14时达到135135种。若顶点数量超过10，不建议枚举所有匹配，应直接用最优解算法跳过枚举步骤

更高效的最优解思路（无需枚举所有匹配） #

既然你的最终目标是找到总距离最小的配对，完全不需要生成所有完美匹配。可以将问题转化为完全图的最小权完美匹配问题：

• 构建一个完全图，顶点为原问题中的奇顶点，边权设为两个顶点在原图中的最短路径距离
• 使用专门的最小权完美匹配算法（如Kuhn-Munkres算法的变种、Edmonds算法）直接求解最优配对，时间复杂度远低于枚举所有可能，适合顶点数量较多的场景

内容的提问来源于stack exchange，提问作者Iced Elixir