Java でハンガリー語のアルゴリズムを実装しようとしています。NxN コスト マトリックスがあります。私はこのガイドを順を追って進めています。したがって、costMatrix[N][N] と、カバーされた行とカバーされた列を追跡する 2 つの配列があります - rowCover[N]、rowColumn[N] (1 はカバーされていることを意味し、0 はカバーされていないことを意味します)
最小行数で 0 をカバーするにはどうすればよいですか? 誰かが私を正しい方向に向けることができますか?
ヘルプ/提案をいただければ幸いです。
ウィキペディアの記事 (セクションMatrix Interpretation )のアルゴリズムの 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();
}
}
}
重要な部分は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 の実装を共有したいと思います。
このステップのアルゴリズムがどのように機能するかについての簡単な説明は次のとおりです。
これらの 3 つの方法を使用する利点は、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
これは@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
}