从矩阵中找到最大数量的唯一对数

Question

因此，我正在尝试解决Python中的问题，并且能够生成形式的矩阵：

[
 [ 0, 0, 0, 1, 1, 1 ],
 [ 0, 0, 1, 0, 1, 1 ],
 [ 0, 1, 0, 0, 0, 1 ],
 [ 1, 0, 0, 0, 1, 1 ],
 [ 1, 1, 0, 1, 0, 0 ],
 [ 1, 1, 1, 1, 0, 0 ],
]

这只是数组数组。矩阵是一个方形矩阵，其对角线总是为0，因为它实际上代表了两个实体之间的兼容性。例如，实体0与第一列中1代表的实体3、4和5兼容。矩阵沿对角线镜像，因为如果实体1与实体3兼容，那么实体3也将与条目1兼容。

现在，我本质上想要做的就是找到一种最大数量的兼容实体数量，而无需重复配对， 。例如，如果实体0已与实体3配对，则不应将其与实体4配对。但是，如果实体3具有另一个兼容实体，但实体4却没有，那么实体0应该与实体4配对，而不是实体4 3。

最终目标是找出将保持不配对的实体数量。我可能会强迫这样的解决方案，但是由于它比编程问题更像是一个数学问题，所以我想知道是否有一种有效的方法可以解决。

Answer 1

看来您拥有的是 ateackency matrix 无方向的图形。图由节点之间的节点和边缘组成。您的问题可以总结为在a

您首先从邻接矩阵构建图对象；然后致电找到最大的基数匹配。它实现 edmonds's edmonds's blossom algorithm 。

# pip install networkx
import networkx as nx
G = nx.from_numpy_matrix(data)
tmp = nx.max_weight_matching(G)

这将输出最大的基数匹配：

{(0, 5), (1, 2), (3, 4)}

从那里，如果您想找到无与伦比的节点的数量，则可以找到节点和匹配的节点之间的区别：

out = len(G.nodes - {x for pair in list(tmp) for x in pair})

输出：输出：

0