匈牙利算法的最少行数

我想知道匈牙利算法覆盖所有零的最少行数。 我已经关注了这个链接，但是那里的代码是一个贪婪的代码。

匈牙利算法：如何用最少的行数覆盖0个元素？ https://stackoverflow.com/questions/14795111/hungarian-algorithm-how-to-cover-0-elements-with-minimum-lines

例如，

{0,0,1,1},
{1,0,0,1},
{1,0,1,0},
{1,1,1,1},

这个案子失败了。我应该得到输出 3。但是这个解决方案给出的输出是 4。

任何其他解决问题的方法都会有很大的帮助。

Thanks

介绍

我无法访问 CPP 编译器或 java 运行时。使用我的浏览器（使用 ES2017）编写此内容。至少它可以在您的浏览器中运行！如果您需要，我可以用其他语言（cpp、java、php、python）编写它。

我必须补充一点，我对此一无所知Hungarian Algorithm我刚刚创建了一个算法来找到最佳的最小优化线！

我正在推送这段代码并进行测试Github 仓库 https://github.com/alijvhr/HungarianAlgorithm。这样您就可以激发更多信息、代码、文档here https://github.com/alijvhr/HungarianAlgorithm

在矩阵数据表示中我使用：

index 0代表行和索引1代表列。

Step 1

经过input数组并计算零并将其存储在二维数组中。

The #matrixPower表示每列或行中零的数量。

Step 2

在下一步中，我们逐行检查。每行的值大于0 in #matrixPower[0]是一行包含零，我们称它们为powered今后。

循环通电行并检查与当前电流交叉的每一列powered row on 0！如果有任何柱子的功率为1所以我们在行上画线！并将每个交叉列的功率减少1。因为它被当前行覆盖了！

计算进度中的行数。

对所有行执行此操作！

Notice:当列与行交叉时zero功率至少是1因为zero在十字架上！

Step 3

If any powered列仍然存在，我们应该在他们身上划清界限！

就是这样！现在我们有了一张线路图和一些最小线路！

Note: inputMatrix是包含你的矩阵的变量！

let colLength = inputMatrix[0].length;
let rowLength = inputMatrix.length;
let matrixPower = [Array(rowLength).fill(0), Array(colLength).fill(0)];
let matrixLine = [Array(rowLength).fill(0), Array(colLength).fill(0)];

for (let row = 0; row < rowLength; row++) {
    for (let col = 0; col < colLength; col++) {
        if (inputMatrix[row][col] == 0) {
            matrixPower[0][row]++;
            matrixPower[1][col]++;
        }
    }
}
let minimum = 0;
let len = [matrixPower[0].length, matrixPower[1].length], cross;
for (let row = 0; row < len[0]; row++) {
    cross = [];
    for (let col = 0; col < len[0]; col++) {
        if (inputMatrix[row][col] == 0) {
            cross.push(col);
            if (matrixPower[1][col] < 2) {
                matrixLine[0][row] = 1;
            }
        }
    }
    if (matrixLine[0][row] == 1) {
        minimum++;
        for (let i = 0; i < cross.length; i++)
            matrixPower[1][cross[i]]--;
    }
}
for (let col = 0; col < len[1]; col++) {
    if (matrixPower[1][col] > 0) {
        matrixLine[1][col] = 1;
        minimum++;
    }
}

console.log(minimum);

我用随机的方式针对优化的强力函数测试了该算法 100 次12*10矩阵。结果100%OK！

平均暴力破解时间：0.036653s

优化算法平均时间：0.000019s

暴力破解总时间：3.9180s

优化算法总时间：0.0025s

我百测暴力工具〜4秒但该算法只需要2.5毫秒

我相信通过更多的工作可以进一步优化这一点。