匈牙利算法的最小行数

Question

匈牙利算法的最小行数

3

我想知道匈牙利算法覆盖所有零元素所需的最小行数。我尝试了这个链接，但那里的代码是贪心算法。

例如，

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

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

如果有其他解决方法，将是非常有帮助的。

谢谢

- user650521

2

试试http://codegolf.stackexchange.com/我认为这个问题更相关。 - dmi3y

1

@dmi3y 我怀疑。Code Golf 的目的是编写尽可能少的代码行数或尽可能快地执行程序，而不是针对算法问题的一般方法。 - Bernhard Barker

是的，TS提到了算法的最小行数，这就是为什么我认为在Code Golf上比在SF上更有帮助。 - dmi3y

@dmi3y，你误解了问题。OP想要用最少的线覆盖0。请参阅维基百科上的匈牙利算法。 - kinokijuf

@pathikrit 你想用什么编程语言？对于你来说，C++、JavaScript和Java有什么区别吗？ - Alijvhr

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alijvhr · Accepted Answer

介绍

我没有CPP编译器或Java运行时环境。使用 ES2017 在浏览器中编写此代码。至少它可以在你的浏览器上运行！如果需要，我可以用其他语言编写它（cpp、java、php、python）。

我必须补充说，我不知道“匈牙利算法”，我只是创建了一种找到最佳最小优化行的算法！

我正在Github仓库中推送这个代码和测试。因此，您可以在这里获取更多信息、代码和文档。

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

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

步骤1

遍历input数组并计算零的数量，将其存储在一个二维数组中。

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

步骤2

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

循环遍历powered行并检查每个跨越当前powered行的列上的0！如果有任何幂为1的列，则在该行上画线！并将每个交叉列的功率减少1。因为它被当前行覆盖！

计算进展中的线路数。

对所有行执行此操作！

注意：当一列在zero上穿过一行时，由于交叉处的zero，功率至少为1。

第三步

如果仍有任何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%正常！

暴力算法平均时间：0.036653秒

优化算法平均时间：0.000019秒

暴力算法总时间：3.9180秒

优化算法总时间：0.0025秒

我进行了一百次测试，暴力算法用了约4秒，而算法只用了2.5毫秒

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