基于对称成本矩阵的双向节点配对最低成本求解方案问询

你的问题本质是无向图的最小权重完美匹配问题，允许节点自环（对应自身配对），每个节点恰好被匹配一次（要么和另一个节点双向配对，要么自环）。匈牙利算法不适用是因为它针对的是二分图的有向分配问题，无法直接输出无向的双向配对结果，下面的方法能完美解决你的需求：

高效算法选择 #

• Blossom算法（开花算法）：这是解决一般无向图最小权重完美匹配的标准算法，完全适配你的场景。它能直接处理无向边的配对，自动满足双向链接的要求，同时可以包含自环（将自环的权重设为矩阵中A[i][i]的值即可）。

现成Python库推荐 #

不用自己写遗传算法，直接用成熟库快速解决：

networkx #

这是Python最常用的图论工具库，内置了Blossom算法的实现，上手简单：

import networkx as nx
import numpy as np

# 示例对称成本矩阵
cost_matrix = np.array([
    [0, 8, 5],
    [8, 0, 6],
    [5, 6, 0]
])

# 构建无向图
graph = nx.Graph()
node_count = cost_matrix.shape[0]
graph.add_nodes_from(range(node_count))

# 添加所有边（包括自环）
for i in range(node_count):
    for j in range(i, node_count):
        graph.add_edge(i, j, weight=cost_matrix[i][j])

# 求解最小权重完美匹配
optimal_matching = nx.min_weight_matching(graph, maxcardinality=True)
print("最优配对方案：", list(optimal_matching))

输出结果里的每个元组就是配对组，比如(0,2)代表节点0和2双向配对，(1,1)代表节点1自环。如果实际场景不允许自环，把cost_matrix[i][i]设为一个极大值（比如1e9）即可。

ortools #

谷歌开源的运筹优化库，适合处理大规模节点的场景，性能比networkx更优。可以通过最小费用流模型转化问题求解，或者直接使用其匹配模块。

blossom-v #

如果需要极致性能，可以用这个基于C++实现的Blossom算法库，有Python绑定，专门针对大规模图的匹配问题做了优化。

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