匈牙利算法：如何找到覆盖零的最小行数？

Question

我正在尝试实现匈牙利算法，但我卡在了第五步。基本上，给定一个n x n的数字矩阵，我该如何找到最少数量的垂直+水平线条，以便覆盖矩阵中的零？

在有人将这个问题标记为此问题的副本之前，请注意，那里提到的解决方案是不正确的，另外其他人也遇到了代码中的错误。

我不是在寻找代码，而是要理解如何绘制这些线条的概念...

编辑： 请勿发布简单（但错误）的贪心算法：给定以下输入：

(0, 1, 0, 1, 1)
(1, 1, 0, 1, 1)
(1, 0, 0, 0, 1)
(1, 1, 0, 1, 1)
(1, 0, 0, 1, 0)

我选择第二列，显然是第二个 (从0开始计数):

(0, 1, x, 1, 1)
(1, 1, x, 1, 1)
(1, 0, x, 0, 1)
(1, 1, x, 1, 1)
(1, 0, x, 1, 0)

现在我可以选择第二行或第一列，它们都有两个“剩余”的零。如果我选择第二列，就会得到这条路径上的错误解决方案：

(0, x, x, 1, 1)
(1, x, x, 1, 1)
(1, x, x, 0, 1)
(1, x, x, 1, 1)
(1, x, x, 1, 0)

正确解决方案需使用4行代码：

(x, x, x, x, x)
(1, 1, x, 1, 1)
(x, x, x, x, x)
(1, 1, x, 1, 1)
(x, x, x, x, x)

- pathikrit

---

如果需要帮助，请查阅此Wikipedia文章的第三步骤。 - Mohit Jain

在发布这篇文章之前，我查看了维基百科的文章，但它并没有帮助我解决问题。当他们在第三步骤中说“最初尽可能分配多个任务，然后执行以下操作”时，它太高级了。 - pathikrit

复制我的现在丢失的评论：有一种漂亮的方法可以测试匈牙利算法（或任何其他原始对偶算法）。修改实现以返回每行和每列的潜力。检查潜力是否有效：每个矩阵条目大于或等于（对于最小成本匹配）行潜力和列潜力之和。检查与匹配相对应的条目是否等于行潜力和列潜力之和。 - David Eisenstat

你所寻找的是矩阵的“零项秩”。 - Anne van Rossum

我想你两个链接的内容是从第一个评论中链接的维基百科文章抄袭来的，而这篇文章（在我看来）并不是很好。 - David Eisenstat

Answer 1

更新

我已经按照您发布的链接提供的相同步骤实现了匈牙利算法：匈牙利算法

以下是附带注释的文件： Github

第3步中的算法（改进的贪心算法）：（这段代码非常详细，有助于理解选择绘制线的概念：水平与垂直。但请注意，在我的代码中，此步骤的代码已得到改进，在Github中）

• 计算输入矩阵中每个xy位置的垂直零数与水平零数的最大值，并将结果存储在一个名为m2的单独数组中。
• 在计算时，如果水平零数>垂直零数，则转换为负数。（仅用于区分后续使用的选择方向）
• 循环遍历m2数组中的所有元素。如果值为正，则在数组m3中绘制垂直线，如果值为负，则在m3中绘制水平线。

请根据以下示例+代码进一步了解算法：

创建3个数组：

• m1：第一个数组，保存输入值
• m2：第二个数组，在每个x，y位置上保存最大零数（垂直、水平）
• m3：第三个数组，保存最终线条（0索引未覆盖，1索引已覆盖）

创建2个函数：

• hvMax(m1，row，col)：返回水平或垂直零的最大数量。（正数表示垂直，负数表示水平）
• clearNeighbours(m2，m3，row，col)：void方法，如果行列索引处的值为负数，则清除水平邻居，或者如果为正数，则清除垂直邻居。此外，它将通过翻转零位为1，在m3数组中设置线条。

代码

public class Hungarian {
    public static void main(String[] args) {
        // m1 input values
        int[][] m1 = { { 0, 1, 0, 1, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 0, 0, 1 },
                { 1, 1, 0, 1, 1 }, { 1, 0, 0, 1, 0 } };

        // int[][] m1 = { {13,14,0,8},
        // {40,0,12,40},
        // {6,64,0,66},
        // {0,1,90,0}};

        // int[][] m1 = { {0,0,100},
        // {50,100,0},
        // {0,50,50}};

        // m2 max(horizontal,vertical) values, with negative number for
        // horizontal, positive for vertical
        int[][] m2 = new int[m1.length][m1.length];

        // m3 where the line are drawen
        int[][] m3 = new int[m1.length][m1.length];

        // loop on zeroes from the input array, and sotre the max num of zeroes
        // in the m2 array
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                if (m1[row][col] == 0)
                    m2[row][col] = hvMax(m1, row, col);
            }
        }

        // print m1 array (Given input array)
        System.out.println("Given input array");
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                System.out.print(m1[row][col] + "\t");
            }
            System.out.println();
        }

        // print m2 array 
        System.out
                .println("\nm2 array (max num of zeroes from horizontal vs vertical) (- for horizontal and + for vertical)");
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                System.out.print(m2[row][col] + "\t");
            }
            System.out.println();
        }

        // Loop on m2 elements, clear neighbours and draw the lines
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                if (Math.abs(m2[row][col]) > 0) {
                    clearNeighbours(m2, m3, row, col);
                }
            }
        }

        // prinit m3 array (Lines array)
        System.out.println("\nLines array");
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                System.out.print(m3[row][col] + "\t");
            }
            System.out.println();
        }
    }

    // max of vertical vs horizontal at index row col
    public static int hvMax(int[][] m1, int row, int col) {
        int vertical = 0;
        int horizontal = 0;

        // check horizontal
        for (int i = 0; i < m1.length; i++) {
            if (m1[row][i] == 0)
                horizontal++;
        }

        // check vertical
        for (int i = 0; i < m1.length; i++) {
            if (m1[i][col] == 0)
                vertical++;
        }

        // negative for horizontal, positive for vertical
        return vertical > horizontal ? vertical : horizontal * -1;
    }

    // clear the neighbors of the picked largest value, the sign will let the
    // app decide which direction to clear
    public static void clearNeighbours(int[][] m2, int[][] m3, int row, int col) {
        // if vertical
        if (m2[row][col] > 0) {
            for (int i = 0; i < m2.length; i++) {
                if (m2[i][col] > 0)
                    m2[i][col] = 0; // clear neigbor
                m3[i][col] = 1; // draw line
            }
        } else {
            for (int i = 0; i < m2.length; i++) {
                if (m2[row][i] < 0)
                    m2[row][i] = 0; // clear neigbor
                m3[row][i] = 1; // draw line
            }
        }

        m2[row][col] = 0;
        m3[row][col] = 1;
    }
}

输出

Given input array
0   1   0   1   1   
1   1   0   1   1   
1   0   0   0   1   
1   1   0   1   1   
1   0   0   1   0   

m2 array (max num of zeroes from horizontal vs vertical) (- for horizontal and + for vertical)
-2  0   5   0   0   
0   0   5   0   0   
0   -3  5   -3  0   
0   0   5   0   0   
0   -3  5   0   -3  

Lines array
1   1   1   1   1   
0   0   1   0   0   
1   1   1   1   1   
0   0   1   0   0   
1   1   1   1   1   

PS: 你指出的那个例子永远不会发生，因为你可以看到第一个循环通过取max(horizontal, vertical)来进行计算，并将它们保存在m2中。 因此，col1将不被选择，因为-3表示画水平线，而-3是通过水平与垂直零点之间的最大值计算得出的。 因此，在元素的第一次迭代中，程序已检查如何绘制线条，在第二次迭代中，程序绘制线条。

- CMPS

---

@wrick 如果水平和垂直方向的零相等，那么在哪个方向绘制线条就无所谓了。在我的代码中，当两个方向具有相同数量的零时，线条将被水平绘制。您可以在上面的maxVH()方法中看到这一点：return vertical > horizontal ? vertical : horizontal * -1;。在我在github上的完整实现中，我也考虑了这种情况以绘制水平线。 - CMPS

您的实现有误。我在我的系统上运行了一下，它没有解决这个http://www.wikihow.com/Use-the-Hungarian-Algorithm特定示例的问题。线条绘制算法存在问题。 - Rohan Sood

@RohanSood 更正：我明白你在说什么，也找到了问题所在。请给我一些时间来修复它，并在这里和Github上发布。 - CMPS

这个解决方案仍然有问题。行计算不正确。似乎每一步中的行重新计算都是错误的。 - Bence Végert

行覆盖逻辑不正确。在某些情况下，它并未使用最少数量的行。 - Gurwinder Singh

Answer 2

贪心算法可能无法适用于某些情况。

首先，可以将您的问题重新表述为：给定一个二分图，找到一个最小的顶点覆盖。在这个问题中，有2n个节点，n个行和n个列。如果相应的列和行的交叉处的元素为零，则两个节点之间存在一条边。顶点覆盖是一个节点集合（行和列），使得每条边都与该集合中的某个节点相关联（每个零由行或列覆盖）。

这是一个众所周知的问题，可以通过查找最大匹配来在O(n^3)时间内解决。有关详细信息，请参见wikipedia。

- Wanderer

---

整个匈牙利算法的时间复杂度为O(n^3)。它的一个子步骤怎么可能是O(N^3)呢？ - pathikrit

@wrick 说匈牙利算法找到最大匹配有点误导人，它实际上找到了多个最大匹配，每次从上一个更有效地计算出下一个，而不是从头开始。 - David Eisenstat

O(n^3)只是一个上限。如果你有一个算法，其中一步是O(n)，一步是O(n^3)，然后另一步是O(n)，那么整个算法就是O(n^3)，因为n + n + n^3小于3n^3，而3n^3是O(n^3)。 - Psymunn

Answer 3

有些情况下，Amir的代码会失败。

考虑以下m1：

 0  0  1

 0  1  1

 1  0  1

最好的解决方案是在前两列中绘制竖线。

Amir的代码将给出以下m2：

-2 -2  0

 2  0  0

 0  2  0

结果将会绘制出两条垂直线以及第一行中的一条线。

我认为问题在于决胜情况：

return vertical > horizontal ? vertical : horizontal * -1;

由于代码的编写方式，非常相似的m1不会失败：

 0  1  1

 1  0  1

 0  0  1

当第一行被移动到底部时，清除函数将在到达这些单元格之前清除m2中的-2值。在第一个案例中，-2值首先被击中，因此会在第一行上绘制一条水平线。

我已经做了一些工作，并且得出了以下结论：如果存在平局，则不要设置任何值，也不要在那些单元格上画线。这涵盖了我提到的矩阵的情况，在这一步骤中我们完成了。

显然，仍然会有0未被覆盖的情况。下面是另一个矩阵的示例，Amir的方法会失败（m1）：

 0 0 1 1 1
 0 1 0 1 1
 0 1 1 0 1
 1 1 0 0 1
 1 1 1 1 1

最佳方案是前四行，例如前四列。

Amir的方法得到了m2：

 3 -2  0  0  0
 3  0 -2  0  0
 3  0  0 -2  0
 0  0 -2 -2  0
 0  0  0  0  0

这将在前四行和第一列绘制线条（错误的解决方案，会产生5 条线）。再次，关键是如何处理平局。我们通过不为平局设置值并迭代该过程来解决此问题。

如果我们忽略平局，我们得到了一个 m2：

 3 -2  0  0  0
 3  0  0  0  0
 3  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0

这会导致仅覆盖第一行和第一列。然后我们将被覆盖的0移除，得到新的m1:

 1 1 1 1 1
 1 1 0 1 1
 1 1 1 0 1
 1 1 0 0 1
 1 1 1 1 1

然后我们不断重复这个过程（忽略平局），直到达到一个解决方案。对于新的m2，再次重复此过程：

 0  0  0  0  0
 0  0  2  0  0
 0  0  0  2  0
 0  0  0  0  0
 0  0  0  0  0

这导致第二和第三列出现两条竖线。现在所有的0都被覆盖，只需要四条线（这是与前四列对齐的另一种方法）。上述矩阵只需要2次迭代，我想大多数情况下只需要2次迭代，除非有嵌套在嵌套中的平局集。我试图想出一个解决方案，但变得难以控制。

不幸的是，这还不够好，因为会有一些情况会永远保持平局。特别是在存在“不相交的平局单元集”的情况下。不确定如何描述这个问题，除了画出以下两个例子：

 0 0 1 1
 0 1 1 1
 1 0 1 1
 1 1 1 0

或者

 0 0 1 1 1
 0 1 1 1 1
 1 0 1 1 1
 1 1 1 0 0
 1 1 1 0 0

这两个示例中左上角的3x3子矩阵与我的原始示例相同，我已经在底部和右侧添加了1或2行/列。新添加的零仅出现在新行和列交叉的地方，为了清晰起见进行描述。

使用我描述的迭代方法，这些矩阵将陷入无限循环。零将始终保持链接（列计数与行计数）。在这一点上，在平局情况下任意选择一个方向是有意义的，至少就我所想象的而言。

我遇到的唯一问题是设置循环停止标准。我不能假设2次迭代足够（或任何n），但我也无法确定如何检测矩阵是否仅剩下无限循环。我仍然不确定如何在计算上描述这些不连通的链接集合。

这里是目前我想出来的代码（MATLAB脚本）：

function [Lines, AllRows, AllCols] = FindMinLines(InMat)

%The following code finds the minimum set of lines (rows and columns)
%required to cover all of the true-valued cells in a matrix. If using for
%the Hungarian problem where 'true-values' are equal to zero, make the
%necessary changes. This code is not complete, since it will be caught in 
%an infinite loop in the case of disjoint-tied-sets

%If passing in a matrix where 0s are the cells of interest, uncomment the
%next line
%InMat = InMat == 0;

%Assume square matrix
Count = length(InMat);
Lines = zeros(Count);

%while there are any 'true' values not covered by lines

while any(any(~Lines & InMat))
    %Calculate row-wise and col-wise totals of 'trues' not-already-covered
    HorzCount = repmat(sum(~Lines & InMat, 2), 1, Count).*(~Lines & InMat);
    VertCount = repmat(sum(~Lines & InMat, 1), Count, 1).*(~Lines & InMat);

    %Calculate for each cell the difference between row-wise and col-wise
    %counts. I.e. row-oriented cells will have a negative number, col-oriented
    %cells will have a positive numbers, ties and 'non-trues' will be 0.
    %Non-zero values indicate lines to be drawn where orientation is determined
    %by sign. 
    DiffCounts = VertCount - HorzCount;

    %find the row and col indices of the lines
    HorzIdx = any(DiffCounts < 0, 2);
    VertIdx = any(DiffCounts > 0, 1);

    %Set the horizontal and vertical indices of the Lines matrix to true
    Lines(HorzIdx, :) = true;
    Lines(:, VertIdx) = true;
end

%compute index numbers to be returned. 
AllRows = [find(HorzIdx); find(DisjTiedRows)];
AllCols = find(VertIdx);

end

- mhermher

---

看起来如果标签以垂直（正）方式绑定，整个问题就会消失？ - nigelhenry

Answer 4

第五步： 在矩阵中绘制的线条被对角线评估，最大评估长度为矩阵的长度。

基于http://www.wikihow.com/Use-the-Hungarian-Algorithm，仅使用步骤1至8。

运行代码片段并在控制台中查看结果

控制台输出

horizontal line (row): {"0":0,"2":2,"4":4}
vertical line (column): {"2":2}

Step 5: Matrix
0  1  0  1  1  
1  1  0  1  1  
1  0  0  0  1  
1  1  0  1  1  
1  0  0  1  0  

Smallest number in uncovered matrix: 1
Step 6: Matrix
x  x  x  x  x  
1  1  x  1  1  
x  x  x  x  x  
1  1  x  1  1  
x  x  x  x  x

JSFiddle: http://jsfiddle.net/jjcosare/6Lpz5gt9/2/

// http://www.wikihow.com/Use-the-Hungarian-Algorithm

var inputMatrix = [
  [0, 1, 0, 1, 1],
  [1, 1, 0, 1, 1],
  [1, 0, 0, 0, 1],
  [1, 1, 0, 1, 1],
  [1, 0, 0, 1, 0]
];

//var inputMatrix = [
//      [10, 19, 8, 15],
//      [10, 18, 7, 17],
//      [13, 16, 9, 14],
//      [12, 19, 8, 18],
//      [14, 17, 10, 19]
//    ];

var matrix = inputMatrix;
var HungarianAlgorithm = {};

HungarianAlgorithm.step1 = function(stepNumber) {

  console.log("Step " + stepNumber + ": Matrix");

  var currentNumber = 0;
  for (var i = 0; i < matrix.length; i++) {
    var sb = "";
    for (var j = 0; j < matrix[i].length; j++) {
      currentNumber = matrix[i][j];
      sb += currentNumber + "  ";
    }
    console.log(sb);
  }
}

HungarianAlgorithm.step2 = function() {
  var largestNumberInMatrix = getLargestNumberInMatrix(matrix);
  var rowLength = matrix.length;
  var columnLength = matrix[0].length;
  var dummyMatrixToAdd = 0;
  var isAddColumn = rowLength > columnLength;
  var isAddRow = columnLength > rowLength;

  if (isAddColumn) {
    dummyMatrixToAdd = rowLength - columnLength;
    for (var i = 0; i < rowLength; i++) {
      for (var j = columnLength; j < (columnLength + dummyMatrixToAdd); j++) {
        matrix[i][j] = largestNumberInMatrix;
      }
    }
  } else if (isAddRow) {
    dummyMatrixToAdd = columnLength - rowLength;
    for (var i = rowLength; i < (rowLength + dummyMatrixToAdd); i++) {
      matrix[i] = [];
      for (var j = 0; j < columnLength; j++) {
        matrix[i][j] = largestNumberInMatrix;
      }
    }
  }

  HungarianAlgorithm.step1(2);
  console.log("Largest number in matrix: " + largestNumberInMatrix);

  function getLargestNumberInMatrix(matrix) {
    var largestNumberInMatrix = 0;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      for (var j = 0; j < matrix[i].length; j++) {
        currentNumber = matrix[i][j];
        largestNumberInMatrix = (largestNumberInMatrix > currentNumber) ?
          largestNumberInMatrix : currentNumber;
      }
    }
    return largestNumberInMatrix;
  }
}

HungarianAlgorithm.step3 = function() {
  var smallestNumberInRow = 0;
  var currentNumber = 0;

  for (var i = 0; i < matrix.length; i++) {
    smallestNumberInRow = getSmallestNumberInRow(matrix, i);
    console.log("Smallest number in row[" + i + "]: " + smallestNumberInRow);
    for (var j = 0; j < matrix[i].length; j++) {
      currentNumber = matrix[i][j];
      matrix[i][j] = currentNumber - smallestNumberInRow;
    }
  }

  HungarianAlgorithm.step1(3);

  function getSmallestNumberInRow(matrix, rowIndex) {
    var smallestNumberInRow = matrix[rowIndex][0];
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[rowIndex][i];
      smallestNumberInRow = (smallestNumberInRow < currentNumber) ?
        smallestNumberInRow : currentNumber;
    }
    return smallestNumberInRow;
  }
}

HungarianAlgorithm.step4 = function() {
  var smallestNumberInColumn = 0;
  var currentNumber = 0;

  for (var i = 0; i < matrix.length; i++) {
    smallestNumberInColumn = getSmallestNumberInColumn(matrix, i);
    console.log("Smallest number in column[" + i + "]: " + smallestNumberInColumn);
    for (var j = 0; j < matrix[i].length; j++) {
      currentNumber = matrix[j][i];
      matrix[j][i] = currentNumber - smallestNumberInColumn;
    }
  }

  HungarianAlgorithm.step1(4);

  function getSmallestNumberInColumn(matrix, columnIndex) {
    var smallestNumberInColumn = matrix[0][columnIndex];
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[i][columnIndex];
      smallestNumberInColumn = (smallestNumberInColumn < currentNumber) ?
        smallestNumberInColumn : currentNumber;
    }
    return smallestNumberInColumn;
  }
}

var rowLine = {};
var columnLine = {};
HungarianAlgorithm.step5 = function() {
  var zeroNumberCountRow = 0;
  var zeroNumberCountColumn = 0;

  rowLine = {};
  columnLine = {};
  for (var i = 0; i < matrix.length; i++) {
    zeroNumberCountRow = getZeroNumberCountInRow(matrix, i);
    zeroNumberCountColumn = getZeroNumberCountInColumn(matrix, i);
    if (zeroNumberCountRow > zeroNumberCountColumn) {
      rowLine[i] = i;
      if (zeroNumberCountColumn > 1) {
        columnLine[i] = i;
      }
    } else if (zeroNumberCountRow < zeroNumberCountColumn) {
      columnLine[i] = i;
      if (zeroNumberCountRow > 1) {
        rowLine[i] = i;
      }
    } else {
      if ((zeroNumberCountRow + zeroNumberCountColumn) > 2) {
        rowLine[i] = i;
        columnLine[i] = i;
      }
    }
  }

  var zeroCount = 0;
  for (var i in columnLine) {
    zeroCount = getZeroNumberCountInColumnLine(matrix, columnLine[i], rowLine);
    if (zeroCount == 0) {
      delete columnLine[i];
    }
  }
  for (var i in rowLine) {
    zeroCount = getZeroNumberCountInRowLine(matrix, rowLine[i], columnLine);
    if (zeroCount == 0) {
      delete rowLine[i];
    }
  }

  console.log("horizontal line (row): " + JSON.stringify(rowLine));
  console.log("vertical line (column): " + JSON.stringify(columnLine));

  HungarianAlgorithm.step1(5);

  //if ((Object.keys(rowLine).length + Object.keys(columnLine).length) == matrix.length) {
    // TODO:
    // HungarianAlgorithm.step9();
  //} else {
  //  HungarianAlgorithm.step6();
  //  HungarianAlgorithm.step7();
  //  HungarianAlgorithm.step8();
  //}

  function getZeroNumberCountInColumnLine(matrix, columnIndex, rowLine) {
    var zeroNumberCount = 0;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[i][columnIndex];
      if (currentNumber == 0 && !(rowLine[i] == i)) {
        zeroNumberCount++
      }
    }
    return zeroNumberCount;
  }

  function getZeroNumberCountInRowLine(matrix, rowIndex, columnLine) {
    var zeroNumberCount = 0;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[rowIndex][i];
      if (currentNumber == 0 && !(columnLine[i] == i)) {
        zeroNumberCount++
      }
    }
    return zeroNumberCount;
  }

  function getZeroNumberCountInColumn(matrix, columnIndex) {
    var zeroNumberCount = 0;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[i][columnIndex];
      if (currentNumber == 0) {
        zeroNumberCount++
      }
    }
    return zeroNumberCount;
  }

  function getZeroNumberCountInRow(matrix, rowIndex) {
    var zeroNumberCount = 0;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[rowIndex][i];
      if (currentNumber == 0) {
        zeroNumberCount++
      }
    }
    return zeroNumberCount;
  }
}

HungarianAlgorithm.step6 = function() {
  var smallestNumberInUncoveredMatrix = getSmallestNumberInUncoveredMatrix(matrix, rowLine, columnLine);
  console.log("Smallest number in uncovered matrix: " + smallestNumberInUncoveredMatrix);

  var columnIndex = 0;
  for (var i in columnLine) {
    columnIndex = columnLine[i];
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[i][columnIndex];
      //matrix[i][columnIndex] = currentNumber + smallestNumberInUncoveredMatrix;
      matrix[i][columnIndex] = "x";
    }
  }

  var rowIndex = 0;
  for (var i in rowLine) {
    rowIndex = rowLine[i];
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[rowIndex][i];
      //matrix[rowIndex][i] = currentNumber + smallestNumberInUncoveredMatrix;
      matrix[rowIndex][i] = "x";
    }
  }

  HungarianAlgorithm.step1(6);

  function getSmallestNumberInUncoveredMatrix(matrix, rowLine, columnLine) {
    var smallestNumberInUncoveredMatrix = null;;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      if (rowLine[i]) {
        continue;
      }
      for (var j = 0; j < matrix[i].length; j++) {
        if (columnLine[j]) {
          continue;
        }

        currentNumber = matrix[i][j];
        if (!smallestNumberInUncoveredMatrix) {
          smallestNumberInUncoveredMatrix = currentNumber;
        }

        smallestNumberInUncoveredMatrix =
          (smallestNumberInUncoveredMatrix < currentNumber) ?
          smallestNumberInUncoveredMatrix : currentNumber;
      }
    }
    return smallestNumberInUncoveredMatrix;
  }
}

HungarianAlgorithm.step7 = function() {
  var smallestNumberInMatrix = getSmallestNumberInMatrix(matrix);
  console.log("Smallest number in matrix: " + smallestNumberInMatrix);

  var currentNumber = 0;
  for (var i = 0; i < matrix.length; i++) {
    for (var j = 0; j < matrix[i].length; j++) {
      currentNumber = matrix[j][i];
      matrix[j][i] = currentNumber - smallestNumberInMatrix;
    }
  }

  HungarianAlgorithm.step1(7);

  function getSmallestNumberInMatrix(matrix) {
    var smallestNumberInMatrix = matrix[0][0];
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      for (var j = 0; j < matrix[i].length; j++) {
        currentNumber = matrix[i][j];
        smallestNumberInMatrix = (smallestNumberInMatrix < currentNumber) ?
          smallestNumberInMatrix : currentNumber;
      }
    }
    return smallestNumberInMatrix;
  }
}

HungarianAlgorithm.step8 = function() {
  console.log("Step 8: Covering zeroes with Step 5 - 8 until Step 9 is reached");
  HungarianAlgorithm.step5();
}

HungarianAlgorithm.step9 = function(){
  console.log("Step 9...");
}


HungarianAlgorithm.step1(1);
HungarianAlgorithm.step2();
HungarianAlgorithm.step3();
HungarianAlgorithm.step4();
HungarianAlgorithm.step5();
HungarianAlgorithm.step6();

- jjcosare

---

虽然你的代码非常易读，但你能用英语解释一下第五步做了什么吗？ - pathikrit

在矩阵中对对角线上的行进行评估，并分别记录在rowLine和columnLine中。在初始评估之后，两者都会有额外的行，通过将其与相反的行进行评估来删除多余的行。对于columnLine，我们需要检查rowLine是否已经覆盖了所有的零，如果是，则删除该columnLine，反之亦然。 - jjcosare

该算法对于单位矩阵或者对角线上只有一个元素的行列会失败。 - George Ogden

Answer 5

使用以下步骤完成任务：

- 如果一行中只有一个0，则分配该行，否则暂时跳过该行。 - 划掉已分配列中的0。 - 对每一列都执行相同的操作。

完成上述步骤后，请按照以下步骤获取覆盖所有0的最小行数：

- 步骤1 - 选择未分配的行。 - 步骤2 - 如果选择的行中有0，则选择相应的列。 - 步骤3 - 如果选择的列中有分配，则选择相应的行。 - 步骤4 - 重复步骤2和3，直到无法再进行选择为止。 - 步骤5 - 通过未选择的行和已选择的列划线。

对于您的情况：（行和列的索引从0开始）

- 跳过第0行，因为它有两个0。 - 分配第1行，并划掉第2列中的所有0。 - 跳过第2行，因为它有两个未划掉的0。 - 跳过第3行，因为它没有未划掉的0。 - 跳过第4行，因为它有2个未划掉的0。

分配列0。 - 跳过列1，因为它有两个未划掉的0（在第2行和第4行）。 - 跳过列2，因为它已经被分配了0。 - 分配列3，并划掉第2行中的0。 - 分配列4，并划掉第4行中的0。 - 已分配的0用“_”表示，“x”表示已划掉的0。

（ _ 1 x 1 1 ), ( 1 1 _ 1 1 ), ( 1 x x _ 1 ), ( 1 1 x 1 1 ), ( 1 x x 1 _ )

完成分配后，矩阵看起来像上面展示的那样。

现在按照上述5个步骤获取覆盖所有0的最小行数：

- 选择未分配的第3行。 - 由于第3行中有一个0位于第2列，因此选择第2列。 - 由于第2列在第1行中被分配，因此选择第1行。 - 现在通过未选择的行（即第0、2、4行）和已选择的列（即第2列）划线。 - 这4条线将覆盖所有0。

希望这可以帮到您：)

PS: 对于每行和每列都有多个0的情况，如果无法进行初始分配，则可以通过取任意一个分配来处理（对于每行和每列都有多个0的情况，很可能会有多个可能的分配导致最优解）。

- Yash Palriwal

---

如果没有只有一个0的行呢？ - tuket

无法找到以下矩阵的解决方案 ((0, 2, 2, 2), (0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 2))。谢谢您的答复。 - tuket

我正在浏览关于匈牙利算法的几个网页，但是没有一个清楚地说明 - 这是相当普遍的 - 我是否可以选择任何组合的覆盖线来覆盖矩阵中的零，并且使用最少数量的线。所以，@Yash Plvirwal，你能告诉我是否真的可以选择任何这样的组合吗？ - Caco

Answer 6

最佳选项

我找到了一个高效优化的算法。我专门创建了一个 Github 仓库 来介绍它。在这里你可以找到信息、代码、文档、基准测试等等。我已经使用 C++ 和 JavaScript 实现了它，还将实现其他版本。

它相当复杂，但我可以稍微解释一下。

正如我在仓库的 readme 中所说：

这个算法与 Hungarian Algorithm 没有任何关系。它只是一种在二维矩阵中找到最小行数的算法！

步骤1

循环遍历输入的 matrix，计算其中的零，并收集必要的信息。

• power 矩阵是一个辅助矩阵，用于指示每列或每行中零的数量。
• line 矩阵是一个辅助矩阵，用于指示哪些地方有线条，哪些地方没有。
• crosses 矩阵是一个辅助矩阵，包含特定行上的所有交叉线。
• sides 是一对数字，表示包含零的行和列的计数！

第二步

在下一步中，我们将通过水平和垂直两个方向循环遍历 matrix。使用 for 循环的主轴可以是 0: row 或 1: column。

首先，我们需要找到两条最弱的交叉线。弱意味着包含的零更少！

现在我们必须做出选择！

1. 如果最弱的交叉线功率为1，或者最弱的一对交叉线之和小于当前行：画当前行
2. 如果当前行的功率为1，那么交叉线可能更好：画交叉线
3. 如果我们在第二轴上，这意味着我们不会回头，并且不应该留下任何零元素没有画出来：

以需要较少线条的方向绘制直线！

每一步都只需检查并结束进度，如果：

• 线条数达到最短方向功率！
• 任何一侧缩小到零！

注意：当一列穿过一个带有0的行时，由于交叉处的0，功率至少为1！

注意：matrix是包含矩阵的变量！

long len[2];
len[0] = matrix.size();
len[1] = matrix[0].size();
powers[0] = iVec(matrix.size(), 0);
powers[1] = iVec(matrix.size(), 1);

crosses[0] = Matrix::create(len[0], 0, 0);
crosses[1] = Matrix::create(len[1], 0, 0);

crosses[0] = Matrix::create(len[0], 0, 0);
crosses[1] = Matrix::create(len[1], 0, 0);

lines[0] = bVec(len[0], false);
lines[1] = bVec(len[1], false);

minimum = 0;

auto lastRow = len[0] - 1;
sides[0] = 0;
sides[1] = 1;

// Step 1
for (auto row = 0; row < len[0]; row++) {
    for (auto col = 0; col < len[1]; col++) {
        if (matrix[row][col] == 0) {
            powers[0][row]++;
            powers[1][col]++;
            crosses[0][row].push_back(col);
            crosses[1][col].push_back(row);
        }
        if (row == lastRow) {
            if (powers[1][col])
                sides[1]++;
        }
    }
    if (powers[0][row])
        sides[0]++;
}
// LongSide
int ls = (sides[1] > sides[0]);
// ShortSide
int ss = !ls;
// Maximum Output
int maximum = sides[ss];
// OppositeMinimum: a pair of minimum cross powers in a line
int om[2];
// OppositePower: Sum of opposite power
int op;
// LineCrosses: crosses in a line
iVec &lc = crosses[0][0];
// Cross axis ID
int cross;
// CrossPower: power of the current cross
int cp;
// MainPower: power of the current cross
int mp;
// Determines if more zeros available
bool more = true;
for (int main = 0; main < 2 && more; main++) {
    cross = !main;
    for (int i = 0; i < len[main] && more; i++) {
        mp = powers[main][i];
        if (mp == 0) continue;
        lc = crosses[main][i];
        om[0] = maximum;
        om[1] = maximum;
        op = 0;
        if (mp > 1) {
            for (int j = 0; j < lc.size(); j++) {
                if (!lines[cross][lc[j]]) {
                    cp = powers[cross][lc[j]];
                    op += cp;
                    if (om[0] >= cp) {
                        om[1] = om[0];
                        om[0] = cp;
                    } else if (om[1] >= cp) {
                        om[1] = cp;
                    }
                }
            }
        }
        if (om[0] == 1 || (om[0] + om[1]) <= mp) {
            more = line(main, i);
        } else if (mp == 1) {
            more = crossLines(main, i);
        } else if (main == 1) {
            if (sides[main] < sides[cross]) {
                more = line(main, i);
            } else {
                more = crossLines(main, i);
            }
        }
        if (minimum >= maximum) {
            minimum = maximum;
            more = false;
        }
    }
}
if (minimum == 0) minimum = maximum;
std::cout << minimum;

我已经测试了这个算法，并与优化后的暴力算法进行了比较，结果令人惊讶。您可以在repository中查看基准测试结果。

- Alijvhr

Answer 7

您可以在蒙克雷斯的论文《分配和运输问题的算法》中找到一种逐步算法，其中包含了它有效性的证明。请特别参考第33页的步骤1-3。矩阵中的每个零可以被标记为星号或加上撇号，并且可以由水平线或垂直线覆盖。

初始化时，请按照某种顺序检查每个零。如果某个零在其行或列中没有其他被标记的零，则将其标记为星号。以您的示例为例，按自然顺序检查零如下：

（0*，1，0，1，1） （1，1，0*，1，1） （1，0*，0，0，1） （1，1，0，1，1） （1，0，0，1，0*）

然后，覆盖包含有星号零的每一列。这将覆盖上述矩阵中的第1、2、3和5列（从1开始索引）。接下来是主循环。

1. 步骤1：选择一个未被覆盖的零并将其标记为素数。如果其所在行没有被加星的零，则进入步骤2。否则，令Z为其所在行中的被加星的零。覆盖该行并揭示Z所在列的零。[在上面的示例中，这将移除第二行的竖直覆盖，并添加一个水平覆盖到第四行。] 对所有未被覆盖的零重复此步骤。[在我们的示例中，完成了。该算法生成了覆盖列1、3、5的竖线以及覆盖第三行的横线。]
2. 步骤2：这是最复杂的步骤，但实际上并不难。令Z0为唯一未被覆盖的素数零。从Z0开始，依次有一系列的被加星和素数零（可能只有一个元素）。定义如下：Z1是Z0所在列中的加星零（如果没有，则序列到此为止）。然后Z2是Z1所在行中的素数零，以此类推。一直继续，直到序列在一个素数零Z_2k处停止。现在取消标记该序列中的每个加星零，并将序列中的每个素数零标记为加星。擦除所有的素数，揭示每一行，并覆盖包含加星零的每一列。如果所有列都被覆盖，则完成。否则返回到步骤1。

- Jim Conant

Answer 8

@CMPS的答案在很多图形上都失败了。我认为我实现了一个解决问题的方案。

我按照维基百科关于匈牙利算法的文章进行了实现，看起来它似乎一直有效。 从维基百科，这是绘制最少数量线条的方法：

首先，尽可能多地分配任务。 标记所有没有分配任务的行。 在新标记的行中具有零的（未标记的）列。 标记在新标记的列中有任务分配的所有行。 对于所有未分配的行重复此过程。

这是我的Ruby实现：

def draw_lines grid
    #copies the array    
    marking_grid = grid.map { |a| a.dup }

    marked_rows = Array.new
    marked_cols = Array.new

    while there_is_zero(marking_grid) do 
        marking_grid = grid.map { |a| a.dup }

        marked_cols.each do |col|
            cross_out(marking_grid,nil, col)
        end

        marked = assignment(grid, marking_grid)    
        marked_rows = marked[0]
        marked_cols.concat(marked[1]).uniq!

        marking_grid = grid.map { |a| a.dup }

        marking_grid.length.times do |row|
            if !(marked_rows.include? row) then
                cross_out(marking_grid,row, nil)
            end
        end

        marked_cols.each do |col|
            cross_out(marking_grid,nil, col)
        end

    end


    lines = Array.new

    marked_cols.each do |index|
        lines.push(["column", index])
    end
    grid.each_index do |index|
        if !(marked_rows.include? index) then
            lines.push(["row", index])
        end
    end
    return lines
end


def there_is_zero grid
    grid.each_with_index do |row|
        row.each_with_index do |value|
            if value == 0 then
                return true
            end
        end
    end
    return false
end

def assignment grid, marking_grid 
    marking_grid.each_index do |row_index|
        first_zero = marking_grid[row_index].index(0)
        #if there is no zero go to next row
        if first_zero.nil? then
            next        
        else
            cross_out(marking_grid, row_index, first_zero)
            marking_grid[row_index][first_zero] = "*"
        end
    end

    return mark(grid, marking_grid)
end


def mark grid, marking_grid, marked_rows = Array.new, marked_cols = Array.new
    marking_grid.each_with_index do |row, row_index|
        selected_assignment = row.index("*")
        if selected_assignment.nil? then
            marked_rows.push(row_index)
        end
    end

    marked_rows.each do |index|
        grid[index].each_with_index do |cost, col_index|
            if cost == 0 then
                marked_cols.push(col_index)    
            end
        end
    end
    marked_cols = marked_cols.uniq

    marked_cols.each do |col_index|
        marking_grid.each_with_index do |row, row_index|
            if row[col_index] == "*" then
                marked_rows.push(row_index)    
            end
        end
    end

    return [marked_rows, marked_cols]
end


def cross_out(marking_grid, row, col)
    if col != nil then
        marking_grid.each_index do |i|
            marking_grid[i][col] = "X"    
        end
    end
    if row != nil then
        marking_grid[row].map! {|i| "X"} 
    end
end

grid = [
    [0,0,1,0],
    [0,0,1,0],
    [0,1,1,1],
    [0,1,1,1],
]

p draw_lines(grid)

- KNejad