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

检查维基百科文章中算法的第3步（矩阵解释部分），他们解释了一种计算最小行量以覆盖所有0的方法

更新：以下是获取覆盖的最小行数的另一种方法：0's

import java.util.ArrayList;
import java.util.List;

public class MinLines { 
    enum LineType { NONE, HORIZONTAL, VERTICAL }

    private static class Line {
        int lineIndex;
        LineType rowType;
        Line(int lineIndex, LineType rowType) { 
            this.lineIndex = lineIndex;
            this.rowType = rowType;
        }      
        LineType getLineType() {
            return rowType;
        }

        int getLineIndex() { 
            return lineIndex; 
        }
        boolean isHorizontal() {
            return rowType == LineType.HORIZONTAL;
        }
    }

    private static boolean isZero(int[] array) {
        for (int e : array) {
            if (e != 0) {
                return false;
            }
        }
        return true;
    }

    public static List<Line> getMinLines(int[][] matrix) {
        if (matrix.length != matrix[0].length) {
            throw new IllegalArgumentException("Matrix should be square!");
        }

        final int SIZE = matrix.length;
        int[] zerosPerRow = new int[SIZE];
        int[] zerosPerCol = new int[SIZE];

        // Count the number of 0's per row and the number of 0's per column        
        for (int i = 0; i < SIZE; i++) { 
            for (int j = 0; j < SIZE; j++) { 
                if (matrix[i][j] == 0) { 
                    zerosPerRow[i]++;
                    zerosPerCol[j]++;
                }
            }
        }

        // There should be at must SIZE lines, 
        // initialize the list with an initial capacity of SIZE
        List<Line> lines = new ArrayList<Line>(SIZE);

        LineType lastInsertedLineType = LineType.NONE;

        // While there are 0's to count in either rows or colums...
        while (!isZero(zerosPerRow) && !isZero(zerosPerCol)) { 
            // Search the largest count of 0's in both arrays
            int max = -1;
            Line lineWithMostZeros = null;
            for (int i = 0; i < SIZE; i++) {
                // If exists another count of 0's equal to "max" but in this one has
                // the same direction as the last added line, then replace it with this
                // 
                // The heuristic "fixes" the problem reported by @JustinWyss-Gallifent and @hkrish
                if (zerosPerRow[i] > max || (zerosPerRow[i] == max && lastInsertedLineType == LineType.HORIZONTAL)) {
                    lineWithMostZeros = new Line(i, LineType.HORIZONTAL);
                    max = zerosPerRow[i];
                }
            }

            for (int i = 0; i < SIZE; i++) {
                // Same as above
                if (zerosPerCol[i] > max || (zerosPerCol[i] == max && lastInsertedLineType == LineType.VERTICAL)) {
                    lineWithMostZeros = new Line(i, LineType.VERTICAL);
                    max = zerosPerCol[i];
                }
            }

            // Delete the 0 count from the line 
            if (lineWithMostZeros.isHorizontal()) {
                zerosPerRow[lineWithMostZeros.getLineIndex()] = 0; 
            } else {
                zerosPerCol[lineWithMostZeros.getLineIndex()] = 0;
            }

            // Once you've found the line (either horizontal or vertical) with the greater 0's count
            // iterate over it's elements and substract the 0's from the other lines 
            // Example:
            //                          0's x col:
            //           [ 0  1  2  3 ]  ->  1
            //           [ 0  2  0  1 ]  ->  2
            //           [ 0  4  3  5 ]  ->  1
            //           [ 0  0  0  7 ]  ->  3
            //             |  |  |  | 
            //             v  v  v  v
            // 0's x row: {4} 1  2  0 

            //           [ X  1  2  3 ]  ->  0
            //           [ X  2  0  1 ]  ->  1
            //           [ X  4  3  5 ]  ->  0
            //           [ X  0  0  7 ]  ->  2
            //             |  |  |  | 
            //             v  v  v  v
            //            {0} 1  2  0 

            int index = lineWithMostZeros.getLineIndex(); 
            if (lineWithMostZeros.isHorizontal()) {
                for (int j = 0; j < SIZE; j++) {
                    if (matrix[index][j] == 0) {
                        zerosPerCol[j]--;
                    }
                }
            } else {
                for (int j = 0; j < SIZE; j++) {
                    if (matrix[j][index] == 0) {
                        zerosPerRow[j]--;
                    }
                }                    
            }

            // Add the line to the list of lines
            lines.add(lineWithMostZeros); 
            lastInsertedLineType = lineWithMostZeros.getLineType();
        }
        return lines;
    }

    public static void main(String... args) { 
        int[][] example1 = 
        { 
           {0, 1, 0, 0, 5},
           {1, 0, 3, 4, 5},
           {7, 0, 0, 4, 5},
           {9, 0, 3, 4, 5},
           {3, 0, 3, 4, 5} 
        };

        int[][] example2 = 
        {
           {0, 0, 1, 0},
           {0, 1, 1, 0},
           {1, 1, 0, 0},
           {1, 0, 0, 0},
        };

        int[][] example3 = 
        {
           {0, 0, 0, 0, 0, 0},
           {0, 0, 0, 1, 0, 0},
           {0, 0, 1, 1, 0, 0},
           {0, 1, 1, 0, 0, 0},
           {0, 1, 0, 0, 0, 0},
           {0, 0, 0, 0, 0, 0}
        };

        List<int[][]> examples = new ArrayList<int[][]>();
        examples.add(example1);
        examples.add(example2);
        examples.add(example3);

        for (int[][] example : examples) {
            List<Line> minLines = getMinLines(example);
            System.out.printf("Min num of lines for example matrix is: %d\n", minLines.size());
            printResult(example, minLines);
            System.out.println();
        }
    }

    private static void printResult(int[][] matrix, List<Line> lines) {
        if (matrix.length != matrix[0].length) {
            throw new IllegalArgumentException("Matrix should be square!");
        }

        final int SIZE = matrix.length;
        System.out.println("Before:");
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                System.out.printf("%d ", matrix[i][j]);
            }
            System.out.println();
        }

        for (Line line : lines) {
            for (int i = 0; i < SIZE; i++) {
                int index = line.getLineIndex();
                if (line.isHorizontal()) {
                    matrix[index][i] = matrix[index][i] < 0 ? -3 : -1;
                } else {
                    matrix[i][index] = matrix[i][index] < 0 ? -3 : -2;
                }
            }
        }   

        System.out.println("\nAfter:");
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                System.out.printf("%s ", matrix[i][j] == -1 ? "-" : (matrix[i][j] == -2 ? "|" : (matrix[i][j] == -3 ? "+" : Integer.toString(matrix[i][j]))));
            }
            System.out.println();
        }   
    }
}   

重要的部分是方法，它返回一个，其中包含覆盖矩阵条目的行。对于示例矩阵打印：getMinLinesList0's

Min num of lines for example matrix is: 3
Before:
0 1 0 0 5 
1 0 3 4 5 
7 0 0 4 5 
9 0 3 4 5 
3 0 3 4 5 

After:
- + - - - 
1 | 3 4 5 
- + - - - 
9 | 3 4 5 
3 | 3 4 5 

Min num of lines for example matrix is: 4
Before:
0 0 1 0 
0 1 1 0 
1 1 0 0 
1 0 0 0 

After:
| | | | 
| | | | 
| | | | 
| | | | 

Min num of lines for example matrix is: 6
Before:
0 0 0 0 0 0 
0 0 0 1 0 0 
0 0 1 1 0 0 
0 1 1 0 0 0 
0 1 0 0 0 0 
0 0 0 0 0 0 

After:
- - - - - - 
- - - - - - 
- - - - - - 
- - - - - - 
- - - - - - 
- - - - - -    

我希望这能给你一个提升，匈牙利算法的其余部分应该不难实现

我知道这个问题很久以前就已经解决了，但我想分享我对步骤3的实现，其中最小线应该以覆盖所有零的方式绘制。

以下是有关此步骤的算法如何工作的简要说明：

• 循环所有单元格，值为零的单元格，我们需要绘制一条经过它的线，以及它的邻居
• 为了知道应该在哪个方向上绘制线条，我创建了一个名为maxVH（）的方法，该方法将垂直与水平计算零，并返回一个整数。如果整数为正数，则绘制一条垂直线，否则，如果为零或负数，则绘制一条水平线。
• colorNeighbors（） 方法将绘制线条并对其进行计数。此外，它将在直线垂直通过的元素上放置1。-1 在直线水平经过的元素上。2 在 2 条相交线经过的元素上（水平和垂直）。

拥有这3种方法的优点是，我们知道被覆盖了两次的元素，我们知道哪些元素被覆盖，哪些元素没有被覆盖。此外，在绘制线条时，我们增加了线条计数器的数量。

对于匈牙利算法的完整实现+示例：Github

代码 + 步骤 3 的详细注释：

/**
     * Step 3.1
     * Loop through all elements, and run colorNeighbors when the element visited is equal to zero
     * */
    public void coverZeros(){
        numLines = 0;
        lines = new int[values.length][values.length];

        for(int row=0; row<values.length;row++){
            for(int col=0; col<values.length;col++){
                if(values[row][col] == 0)
                    colorNeighbors(row, col, maxVH(row, col));
            }
        }
    }

    /**
     * Step 3.2
     * Checks which direction (vertical,horizontal) contains more zeros, every time a zero is found vertically, we increment the result
     * and every time a zero is found horizontally, we decrement the result. At the end, result will be negative, zero or positive
     * @param row Row index for the target cell
     * @param col Column index for the target cell
     * @return Positive integer means that the line passing by indexes [row][col] should be vertical, Zero or Negative means that the line passing by indexes [row][col] should be horizontal
     * */
    private int maxVH(int row, int col){
        int result = 0;
        for(int i=0; i<values.length;i++){
            if(values[i][col] == 0)
                result++;
            if(values[row][i] == 0)
                result--;
        }
        return result;
    }

    /**
     * Step 3.3
     * Color the neighbors of the cell at index [row][col]. To know which direction to draw the lines, we pass maxVH value.
     * @param row Row index for the target cell
     * @param col Column index for the target cell
     * @param maxVH Value return by the maxVH method, positive means the line to draw passing by indexes [row][col] is vertical, negative or zero means the line to draw passing by indexes [row][col] is horizontal
     * */
    private void colorNeighbors(int row, int col, int maxVH){
        if(lines[row][col] == 2) // if cell is colored twice before (intersection cell), don't color it again
            return;

        if(maxVH > 0 && lines[row][col] == 1) // if cell colored vertically and needs to be recolored vertically, don't color it again (Allowing this step, will color the same line (result won't change), but the num of line will be incremented (wrong value for the num of line drawn))
            return;

        if(maxVH <= 0 && lines[row][col] == -1) // if cell colored horizontally and needs to be recolored horizontally, don't color it again (Allowing this step, will color the same line (result won't change), but the num of line will be incremented (wrong value for the num of line drawn))
            return;

        for(int i=0; i<values.length;i++){ // Loop on cell at indexes [row][col] and its neighbors
            if(maxVH > 0)   // if value of maxVH is positive, color vertically
                lines[i][col] = lines[i][col] == -1 || lines[i][col] == 2 ? 2 : 1; // if cell was colored before as horizontal (-1), and now needs to be colored vertical (1), so this cell is an intersection (2). Else if this value was not colored before, color it vertically
            else            // if value of maxVH is zero or negative color horizontally
                lines[row][i] = lines[row][i] == 1 || lines[row][i] == 2 ? 2 : -1; // if cell was colored before as vertical (1), and now needs to be colored horizontal (-1), so this cell is an intersection (2). Else if this value was not colored before, color it horizontally
        }

        // increment line number
        numLines++;
//      printMatrix(lines); // Monitor the line draw steps
    }//End step 3