gpt4 book ai didi

java - 匈牙利算法 : How to cover 0 elements with minimum lines?

转载 作者:搜寻专家 更新时间:2023-10-30 19:45:37 24 4
gpt4 key购买 nike

我正在尝试用 Java 实现匈牙利算法。我有一个 NxN 成本矩阵。我正在关注 this逐步指导。所以我有 costMatrix[N][N] 和 2 个数组来跟踪覆盖的行和覆盖的列 - rowCover[N]、rowColumn[N](1 表示覆盖,0 表示未覆盖)

如何用最少的行数覆盖 0?谁能指出我正确的方向?

如有任何帮助/建议,我们将不胜感激。

最佳答案

Wikipedia article (section Matrix Interpretation) 中检查算法的第 3 步,他们解释了一种计算最小行数以覆盖所有 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 方法,它返回一个 List,其中包含覆盖矩阵 0 条目的行。对于示例矩阵打印:

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:
- - - - - -
- - - - - -
- - - - - -
- - - - - -
- - - - - -
- - - - - -

我希望这能给你带来动力,匈牙利算法的其余部分应该不难实现

关于java - 匈牙利算法 : How to cover 0 elements with minimum lines?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14795111/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com