如何找到覆盖矩阵中所有零的最少行数？
sir*_*hot 3 algorithm graph-theory matrix hungarian-algorithm
I\xe2\x80\x99m 正在解决一个问题，我有一个nxn矩阵，我需要确定覆盖矩阵中所有零的最小行数（水平和垂直）。本质上，我想找到一种分配这些线路的最佳方法，以最大限度地减少总覆盖范围。
\n这是一个例子：
\n(0, 1, 0, 1, 1)\n(1, 1, 0, 1, 1)\n(1, 0, 0, 0, 1)\n(1, 1, 0, 1, 1)\n(1, 0, 0, 1, 0)\n解决方案必须是：
\n(x, x, x, x, x)\n(1, 1, x, 1, 1)\n(x, x, x, x, x)\n(1, 1, x, 1, 1)\n(x, x, x, x, x)\n在这种情况下，最小行数为 4。
\n有什么算法可以解决吗？
\n我尝试创建一个二维数组，在其中我可以看到一行中的零之和并且可以。
\n上面示例的数组：
\n{ \n [0, 1, 2, 5, 1, 1]\n [2, 0, 0, 0, 0, 0]\n [1, 0, 0, 0, 0, 0]\n [3, 0, 0, 0, 0, 0]\n [1, 0, 0, 0, 0, 0]\n [3, 0, 0, 0, 0, 0]\n}\n在我的算法中，我选择了数组中最大的一个并覆盖了该行（将它们设置为 false），这样我就无法再访问它们了。并将 Linelength 加 1。但它不适用于较长的线路和队列。
\n用大数字覆盖列后：
\n{ \n [0, 1, 2, 0, 1, 1]\n [1, 0, 0, 0, 0, 0]\n [0, 0, 0, 0, 0, 0]\n [2, 0, 0, 0, 0, 0]\n [0, 0, 0, 0, 0, 0]\n [2, 0, 0, 0, 0, 0]\n}\n想象一下二分图，其中左侧部分包含列号Xi，右侧部分包含行号Yi，矩阵中的每个零定义相应行和列之间的边。
K\xc5\x91nig 定理说最大匹配（蓝色边缘）等于最小顶点覆盖（红色列或行），因此每个边缘（矩阵中的零） - 蓝色和灰色 - 都被一些红色顶点（列或行）覆盖排）。
\n因此，应用最大二分匹配算法的任何合适的实现（例如Python networkx库中的maximum_matching ）
\n