Венгерский алгоритм: как покрыть 0 элементов с минимальными строками?

Ответ 1

Проверьте третий шаг алгоритма в статье в Википедии (раздел Матрица), они объясняют способ вычисления минимального количества строк для охвата всех 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 per row and the number of 0 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 to count in either rows or colums...
        while (!isZero(zerosPerRow) && !isZero(zerosPerCol)) { 
            // Search the largest count of 0 in both arrays
            int max = -1;
            Line lineWithMostZeros = null;
            for (int i = 0; i < SIZE; i++) {
                // If exists another count of 0 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 count
            // iterate over it elements and substract the 0 from the other lines 
            // Example:
            //                          0 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 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();
        }   
    }
}   

Важной частью является метод getMinLines, он возвращает List с строками, которые покрывают записи матрицы 0'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:
- - - - - - 
- - - - - - 
- - - - - - 
- - - - - - 
- - - - - - 
- - - - - -    

Я надеюсь, что это даст вам импульс, остальная часть венгерского алгоритма не должна быть сложной для реализации

Ответ 2

Я знаю, что этот вопрос был решен давно, но я хотел бы поделиться своей реализацией для шага 3, где минимальные строки должны быть составлены таким образом, чтобы покрывались все нули.

Вот краткое объяснение того, как работает мой алгоритм для этого шага:

• Петля на всех ячейках, ячейке, которая имеет нулевое значение, нам нужно провести проходящую мимо линию, а ее соседи
• Чтобы узнать, в каком направлении следует рисовать линию, я создал метод maxVH(), который будет считать нули вертикально vs по горизонтали и возвращает целое число. Если целое число положительное, нарисуйте вертикальную линию, иначе, если нуль или отрицательный, нарисуйте горизонтальную линию.
• colorNeighbors() метод будет рисовать линии и будет считать их также. Кроме того, он будет размещать 1 на элементах, где линия проходит вертикально. -1 на элементах, где линия проходит горизонтально. 2 на элементах, где проходят две пересекающиеся линии (горизонтальные и вертикальные).

Преимущество этих трех методов состоит в том, что мы знаем элементы, которые охватываются дважды, мы знаем, какие элементы покрыты и которые не покрыты. Кроме того, при рисовании строк мы увеличиваем количество счетчиков строк.

Для полной реализации венгерского алгоритма + пример: 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