algorithm - 匈牙利算法 : finding minimum number of lines to cover zeroes?

Question

我正在尝试实现 Hungarian Algorithm但我卡在 step 5 上了.基本上，给定一个 n X n数字矩阵，如何找到最小数量的垂直+水平线，以便覆盖矩阵中的零点？

在有人将此问题标记为 this 的副本之前，那里提到的解决方案不正确，其他人also ran into the bug in the code posted there 。

我不是在寻找代码，而是在寻找可以用来绘制这些线条的概念...

编辑:请不要发布简单(但错误)的贪心算法:鉴于此输入:

(0, 1, 0, 1, 1)
(1, 1, 0, 1, 1)
(1, 0, 0, 0, 1)
(1, 1, 0, 1, 1)
(1, 0, 0, 1, 0)

我显然选择了第 2 列(0 索引):

(0, 1, x, 1, 1)
(1, 1, x, 1, 1)
(1, 0, x, 0, 1)
(1, 1, x, 1, 1)
(1, 0, x, 1, 0)

现在我可以选择第 2 行或第 1 列，它们都有两个“剩余”零。如果我选择 col2，我最终会沿着这条路得到不正确的解决方案:

(0, x, x, 1, 1)
(1, x, x, 1, 1)
(1, x, x, 0, 1)
(1, x, x, 1, 1)
(1, x, x, 1, 0)

正确的解决方案是使用 4 行:

(x, x, x, x, x)
(1, 1, x, 1, 1)
(x, x, x, x, x)
(1, 1, x, 1, 1)
(x, x, x, x, x)

Answer 1

更新

我已经按照您发布的链接提供的相同步骤实现了匈牙利算法:Hungarian algorithm

这是带有注释的文件: Github

步骤 3 的算法(改进的贪婪算法):(此代码非常详细，有助于理解选择要绘制的线的概念:水平与垂直。但请注意，此步骤代码在我的代码在 Github )

• 计算输入矩阵中每个 xy 位置垂直与水平零的最大数量，并将结果存储在名为 m2 的单独数组中。
• 在计算时，如果水平零点 > 垂直零点，则计算的数字将转换为负数。 (只是为了区分我们选择哪个方向，以备后用)
• 遍历 m2 数组中的所有元素。如果值为正数，则在数组m3中绘制一条竖线，如果值为负数，则在数组m3
中绘制一条水平线

按照下面的示例+代码来了解更多算法:

创建 3 个数组:

• m1:第一个数组，保存输入值
• m2:第二个数组，在每个 x,y 位置保存 maxZeroes(vertical,horizo​​ntal)
• m3:第三个数组，保存最后几行(0 索引未覆盖，1 索引覆盖)

创建 2 个函数:

• hvMax(m1,行,列);返回水平或垂直零的最大数量。 (正数表示垂直，负数表示水平)
• clearNeighbours(m2, m3,row,col); void 方法，如果 row col indexes 的值为负，它将清除水平邻居，如果为正，则清除垂直邻居。此外，它将通过将零位翻转为 1 来设置 m3 数组中的行。

代码

public class Hungarian {
    public static void main(String[] args) {
        // m1 input values
        int[][] m1 = { { 0, 1, 0, 1, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 0, 0, 1 },
                { 1, 1, 0, 1, 1 }, { 1, 0, 0, 1, 0 } };

        // int[][] m1 = { {13,14,0,8},
        // {40,0,12,40},
        // {6,64,0,66},
        // {0,1,90,0}};

        // int[][] m1 = { {0,0,100},
        // {50,100,0},
        // {0,50,50}};

        // m2 max(horizontal,vertical) values, with negative number for
        // horizontal, positive for vertical
        int[][] m2 = new int[m1.length][m1.length];

        // m3 where the line are drawen
        int[][] m3 = new int[m1.length][m1.length];

        // loop on zeroes from the input array, and sotre the max num of zeroes
        // in the m2 array
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                if (m1[row][col] == 0)
                    m2[row][col] = hvMax(m1, row, col);
            }
        }

        // print m1 array (Given input array)
        System.out.println("Given input array");
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                System.out.print(m1[row][col] + "\t");
            }
            System.out.println();
        }

        // print m2 array 
        System.out
                .println("\nm2 array (max num of zeroes from horizontal vs vertical) (- for horizontal and + for vertical)");
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                System.out.print(m2[row][col] + "\t");
            }
            System.out.println();
        }

        // Loop on m2 elements, clear neighbours and draw the lines
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                if (Math.abs(m2[row][col]) > 0) {
                    clearNeighbours(m2, m3, row, col);
                }
            }
        }

        // prinit m3 array (Lines array)
        System.out.println("\nLines array");
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                System.out.print(m3[row][col] + "\t");
            }
            System.out.println();
        }
    }

    // max of vertical vs horizontal at index row col
    public static int hvMax(int[][] m1, int row, int col) {
        int vertical = 0;
        int horizontal = 0;

        // check horizontal
        for (int i = 0; i < m1.length; i++) {
            if (m1[row][i] == 0)
                horizontal++;
        }

        // check vertical
        for (int i = 0; i < m1.length; i++) {
            if (m1[i][col] == 0)
                vertical++;
        }

        // negative for horizontal, positive for vertical
        return vertical > horizontal ? vertical : horizontal * -1;
    }

    // clear the neighbors of the picked largest value, the sign will let the
    // app decide which direction to clear
    public static void clearNeighbours(int[][] m2, int[][] m3, int row, int col) {
        // if vertical
        if (m2[row][col] > 0) {
            for (int i = 0; i < m2.length; i++) {
                if (m2[i][col] > 0)
                    m2[i][col] = 0; // clear neigbor
                m3[i][col] = 1; // draw line
            }
        } else {
            for (int i = 0; i < m2.length; i++) {
                if (m2[row][i] < 0)
                    m2[row][i] = 0; // clear neigbor
                m3[row][i] = 1; // draw line
            }
        }

        m2[row][col] = 0;
        m3[row][col] = 1;
    }
}

输出

Given input array
0   1   0   1   1   
1   1   0   1   1   
1   0   0   0   1   
1   1   0   1   1   
1   0   0   1   0   

m2 array (max num of zeroes from horizontal vs vertical) (- for horizontal and + for vertical)
-2  0   5   0   0   
0   0   5   0   0   
0   -3  5   -3  0   
0   0   5   0   0   
0   -3  5   0   -3  

Lines array
1   1   1   1   1   
0   0   1   0   0   
1   1   1   1   1   
0   0   1   0   0   
1   1   1   1   1   

PS:您所指向的示例永远不会出现，因为正如您所见，第一个循环通过取最大值(水平、垂直)并将它们保存在 m2 中进行计算。因此不会选择 col1，因为 -3 表示绘制水平线，而 -3 是通过取水平零点与垂直零点之间的最大值计算得出的。因此，在元素的第一次迭代中，程序检查了如何绘制线条，在第二次迭代中，程序绘制线条。