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

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 与实体 3、4 和 5 兼容，在第一列中用 1 表示。矩阵沿对角线镜像，因为如果实体 1 与实体 3 兼容，那么实体 3 也将与条目 1 兼容。

现在我基本上想做的是找到一种方法，使最大数量的兼容实体配对，而无需重复。例如，如果实体 0 已与实体 3 配对，则不应与实体 4 配对。但是，如果实体 3 具有另一个兼容实体而实体 4 没有，则实体 0 应与实体 4 而不是实体配对3.

最终目标是找出未配对的实体数量。我可能可以暴力解决这样的解决方案，但由于它更多的是数学问题而不是编程问题，我想知道是否有一种有效的方法来解决它。

Answer 1

看来您拥有的是 adjacency matrix of an undirected graph. Graphs consist of nodes and edges between the nodes. Your problem can be summarized as finding the number of unmatched nodes in a maximum cardinality matching。 Python中有networkx API是处理图的，如果你愿意用它，问题就变得很简单了。

您首先从邻接矩阵构建一个图形对象；然后调用 max_weight_matching to find the maximum cardinality matching. It implements Edmonds' 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})

输出：

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

Find the maximum number of unique pairs from a matrix

python

graph-theory

matrix