我正在尝试在Java中实现匈牙利算法。 我有一个NxN的成本矩阵。我按照这个指南逐步操作。因此，我有costMatrix [N] [N]和两个数组来跟踪覆盖的行和列-rowCover [N]，rowColumn [N]（1表示已覆盖，0表示未覆盖）。
如何用最少的线覆盖0？ 有人能指点我一下吗？
任何帮助/建议都将不胜感激。
如何用最少的线覆盖0？ 有人能指点我一下吗？
任何帮助/建议都将不胜感激。
3个回答
6
请查看维基百科文章中第三步算法的矩阵解释部分，他们解释了一种计算覆盖所有0的最小行数的方法。更新：以下是另一种获取覆盖
我希望这能给你提供一些帮助，剩下的匈牙利算法实现起来应该不难。
0的最少行数的方法：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();
}
}
}
重要的是getMinLines方法，它返回一个包含覆盖矩阵0条目的行的List。对于示例矩阵，打印如下：
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:
- - - - - -
- - - - - -
- - - - - -
- - - - - -
- - - - - -
- - - - - -
我希望这能给你提供一些帮助，剩下的匈牙利算法实现起来应该不难。
- higuaro
8
0
这是对 @higuaro 答案的改进，但用 Swift 编写（适用于 [[0,94,2,91,57,0,115,2,99],[113,19,7,32,42,13,0,35,16],[109,11,31,56,38,29,16,31,0],[81,51,39,0,10,37,24,67,40],[94,0,34,59,23,42,27,30,11],[71,37,39,0,0,47,32,71,48],[71,41,43,4,0,43,28,71,44],[80,110,0,153,137,0,113,0,97],[0,94,0,89,57,8,121,0,105]]
)：
func modifiedGetMinLines(_ matrix: [[Int]]) -> Set<Line> { // O(N^4)
// Using the algorithm found here - https://www.youtube.com/watch?v=rrfFTdO2Z7I
func drawLinesWhileIsolatedZerosExist(_ matrix: inout [[Int]]) -> Set<Line> { // O(N^3)
let N = matrix.count
var lines: Set<Line> = []
var unprocessedTableChange = true
while unprocessedTableChange { // While loop occurs 2N-1 times max!...each time a line in a matrix must be crossed out to continue
unprocessedTableChange = false
for i in 0..<N { // rows
var zeroCount = 0
var columnOfLastZero = -1
for j in 0..<N {
if matrix[i][j] == 0 {
zeroCount += 1
columnOfLastZero = j
}
}
if zeroCount == 1 {
unprocessedTableChange = true
var selectedCol = Line(columnOfLastZero, .VERTICAL)
for i in 0..<N {
if matrix[i][columnOfLastZero] == 0 {
selectedCol.coord.insert(i)
}
matrix[i][columnOfLastZero] = -1 // Cross line out
}
lines.insert(selectedCol)
}
}
for i in 0..<N { // columns
var zeroCount = 0
var rowOfLastZero = -1
for j in 0..<N {
if matrix[j][i] == 0 {
zeroCount += 1
rowOfLastZero = j
}
}
if zeroCount == 1 {
unprocessedTableChange = true
var selectedRow = Line(rowOfLastZero, .HORIZONTAL)
for i in 0..<N {
if matrix[rowOfLastZero][i] == 0 {
selectedRow.coord.insert(i)
}
matrix[rowOfLastZero][i] = -1 // Cross line out
}
lines.insert(selectedRow)
}
}
}
return lines
}
func zerosToProcessExist(_ array: [Int]) -> Bool { // O(N)
for e in array {
if e > 0 { return true }
}
return false
}
var matrix = matrix
let N = matrix.count
var lines: Set<Line> = drawLinesWhileIsolatedZerosExist(&matrix) // O(N^3)
var zerosPerRow = Array(repeating: 0, count: N)
var zerosPerCol = Array(repeating: 0, count: N)
for i in 0..<N { // O(N^2)
for j in 0..<N {
if matrix[i][j] == 0 {
zerosPerRow[i] += 1
zerosPerCol[j] += 1
}
}
}
while zerosToProcessExist(zerosPerRow) || zerosToProcessExist(zerosPerCol) { // While loop occurs 2N-1 times max!...each time a line in a matrix must be crossed out to continue
var max = 0
var lineWithMostZeros: Line?
var linesWithMaxZeros: Set<Line> = []
for i in 0..<N { // O(N)
if zerosPerRow[i] > max {
linesWithMaxZeros = []
linesWithMaxZeros.insert(Line(i, LineType.HORIZONTAL))
max = zerosPerRow[i]
} else if zerosPerRow[i] == max && max > 0 {
linesWithMaxZeros.insert(Line(i, LineType.HORIZONTAL))
}
if zerosPerCol[i] > max {
linesWithMaxZeros = []
linesWithMaxZeros.insert(Line(i, LineType.VERTICAL))
max = zerosPerCol[i]
} else if zerosPerCol[i] == max && max > 0 {
linesWithMaxZeros.insert(Line(i, LineType.VERTICAL))
}
}
if linesWithMaxZeros.count == 1 {
lineWithMostZeros = linesWithMaxZeros.first
} else {
var minScore = Int.max
var minScoreLine: Line?
for l in linesWithMaxZeros {
var score = 0
if l.isHorizontal() {
for j in 0..<N {
if matrix[l.lineIndex][j] == 0 {
for k in 0..<N {
if matrix[k][j] == 0 { score += 1 }
}
}
}
} else {
for j in 0..<N {
if matrix[j][l.lineIndex] == 0 {
for k in 0..<N {
if matrix[j][k] == 0 { score += 1 }
}
}
}
}
if score < minScore {
minScore = score
minScoreLine = l
}
}
lineWithMostZeros = minScoreLine
}
let index = lineWithMostZeros!.lineIndex
var temp: Set<Int> = []
if lineWithMostZeros!.isHorizontal() { // O(N)
zerosPerRow[index] = 0
for j in 0..<N {
if matrix[index][j] == 0 {
zerosPerCol[j] -= 1
temp.insert(j)
}
matrix[index][j] = -1
}
} else {
zerosPerCol[index] = 0
for j in 0..<N {
if matrix[j][index] == 0 {
zerosPerRow[j] -= 1
temp.insert(j)
}
matrix[j][index] = -1
}
}
lineWithMostZeros!.coord = temp
lines.insert(lineWithMostZeros!)
}
return lines
}
- ToxicAbe
0
我知道这个问题早就被解决了，但我想分享一下我的实现方式，以便在绘制最少行的情况下覆盖所有零。
以下是我用于此步骤的算法的简要说明：
- 循环遍历所有单元格，如果单元格的值为零，则需要通过它和它的邻居绘制一条线。
- 为了知道应该向哪个方向绘制线条，我创建了一个名为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<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
- CMPS
1
4这个实现对于一些情况也不适用。请尝试运行以下代码：int[][] values = {
{17, 10, 13, 2, 12, 11, 0},
{5, 8, 9, 0, 3, 5, 5},
{0, 2, 0, 6, 9, 8, 13},
{26, 1, 11, 12, 0, 0, 13},
{17, 0, 20, 17, 25, 25, 23},
{0, 0, 4, 0, 10, 11, 0},
{12, 11, 0, 20, 12, 6, 14}
}; - LocalHorst
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
0010 0110 1100 1000。你的代码会先选择第四列（有四个零），但接下来可能会选择第一行（还剩两个零），然后是第四行（还剩两个零），接着是第二行（还剩一个零），最后是第三行（还剩一个零），总共选取了五行。 - Justin Wyss-Gallifent