匈牙利算法的最小行数

Question

我想知道匈牙利算法覆盖所有零的最小行数。我点击了这个链接，但那里的代码很贪婪。

匈牙利算法：如何用最少的行覆盖 0 个元素？

例如

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

此案例失败。我应该得到输出 3。但是此解决方案给出的输出是 4。

任何其他解决它的方法都将是一个很大的帮助。

谢谢

Answer 1

简介

我无法访问CPP编译器或java运行时。使用我的浏览器使用 ES2017 编写了这个。至少它可以在您的浏览器中运行！如果你需要，我可以用其他语言(cpp，java，php，python(编写它。

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

我正在推动这段代码并在 Github 存储库中进行测试。因此，您可以在此处触发更多信息，代码，文档

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

索引0表示行，索引1表示列。

步骤 1

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

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

步骤 2

在下一步中，我们将逐行检查。#matrixPower[0]中值大于 0 的每一行都是包含零的行，我们从现在开始将它们称为powered。

循环遍历电源行并检查0上与当前powered行交叉的每一列！如果有任何具有 1 次幂的列，那么我们就在该行上画线！并将每个交叉列的功率降低 1 .因为它被当前行覆盖了！

计算进度中的行数。

对所有行执行此操作！

注意：当一列在zero上与一行交叉时，由于十字中的zero，功率至少为 1！

步骤 3

如果还有powered列，我们应该在它们上面画线！

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

注意：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);

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

平均暴力破解时间：0.036653s

优化算法的平均时间：0.000019s

蛮力总时间：3.9180s

优化算法总时间：0.0025s

我百次测试蛮力花了~4秒，但算法只花了2.5毫秒

我相信这可以通过更多的工作得到更多的优化。