匈牙利算法：如何用最小的线覆盖0个元素？
我正在尝试用Java实现匈牙利语算法。 我有一个NxN成本矩阵。 我正在逐步遵循本指南。 所以我有costMatrix [N] [N]和2个数组来跟踪被覆盖的行和覆盖的cols – rowCover [N]，rowColumn [N]（1表示覆盖，0表示未覆盖）
如何以最小行数覆盖0？ 谁能指出我正确的方向？
任何帮助/建议将不胜感激。
检查维基百科文章（ 矩阵解释部分）中算法的第3步，他们解释了计算覆盖所有0的最小线数的方法
更新：以下是另一种获取覆盖0's最小行数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 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 lines = new ArrayList (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 // | | | | // vvvv // 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 // | | | | // vvvv // {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 examples = new ArrayList(); examples.add(example1); examples.add(example2); examples.add(example3); for (int[][] example : examples) { List 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 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: - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
我希望这会给你一个提升，其余的匈牙利算法应该不难实现
我知道这个问题很久以前就已经解决了，但是我想分享我对第3步的实现，其中应该以覆盖所有零的方式绘制最小线。
以下是我的算法步骤的简要说明：
- 循环所有单元格，具有零值的单元格，我们需要绘制一条经过它的线及其邻居
- 为了知道应该在哪个方向绘制线，我创建了一个名为maxVH（）的方法，它将垂直和水平地计算零，并返回一个整数。 如果整数为正，则绘制一条垂直线，否则，如果为零或负，则绘制一条水平线。
- colorNeighbors（）方法将绘制线条并将计算它们。 此外，它将在线垂直通过的元素上放置1。 在线水平通过的元素上为-1。 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 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 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