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

Question

我正在尝试实施匈牙利算法，但我被困在第 5 步。基本上，给定一个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)

我显然选择了第 2 列（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)

现在我可以选择第 2 行或第 1 列，它们都有两个“剩余”零。如果我选择 col2，我最终会得到不正确的解决方案：

(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)

score 13 · Accepted Answer

更新

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

这是带有评论的文件： Github

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

计算输入矩阵中每个 xy 位置的垂直与水平零的最大数量，并将结果存储在一个名为的单独数组中m2。
计算时，如果水平零 > 垂直零，则计算的数字将转换为负数。（只是为了区分我们选择了哪个方向供以后使用）
循环遍历m2数组中的所有元素。如果值为正，则在数组中画一条垂直线m3，如果值为负，则在数组中画一条水平线m3

按照下面的示例+代码来了解更多算法：

创建 3 个数组：

m1：第一个数组，保存输入值
m2：第二个数组，在每个 x,y 位置保存 maxZeroes(vertical,horizontal)
m3：第三个数组，保存最后一行（0 索引未覆盖，1 索引已覆盖）

创建 2 个函数：

hvMax(m1,row,col); 返回水平或垂直的最大零数。（正数表示垂直，负数表示水平）
clearNeighbors(m2, m3,row,col); void方法，如果row col索引的值为负，它将清除水平邻居，如果为正则清除垂直邻居。此外，它将通过将零位翻转为 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 是通过取水平与垂直零之间的最大值来计算的。因此，在元素的第一次迭代中，程序检查了如何绘制线条，在第二次迭代中，程序绘制了线条。

score 5 · Accepted Answer

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

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

这是一个众所周知的问题，可以通过找到最大匹配在 O(n^3) 内解决。查看维基百科了解详情

score 4 · Accepted Answer

第 5 步：对矩阵中的线的绘制进行对角线评估，最大评估矩阵的长度。

基于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();

score 4 · Accepted Answer

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

考虑以下 m1：

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

Amir 的代码将给出以下 m2：

结果将在第一行绘制两条垂直线以及一条线。

在我看来，问题在于打破平局的情况：

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

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

第一行移到底部的位置，因为清除功能将在到达这些单元格之前清除 m2 中的 -2 值。在第一种情况下，首先命中 -2 值，因此通过第一行绘制一条水平线。

我一直在努力解决这个问题，这就是我所拥有的。在平局的情况下，不要设置任何值，也不要在这些单元格中画线。这涵盖了我上面提到的矩阵的情况，我们在这一步完成。

显然，在某些情况下，仍有未发现的 0。下面是另一个在 Amir 方法 (m1) 中失败的矩阵示例：

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

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：

然后我们不断重复这个过程（忽略关系），直到我们找到一个解决方案。重复一个新的 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 次迭代，我想大多数情况下只需要两次迭代，除非在关系集中嵌套了关系集。我试图想出一个，但它变得难以管理。

可悲的是，这还不够好，因为有些案件将永远捆绑在一起。特别是在存在“不相交的一组绑定单元”的情况下。除了绘制以下两个示例之外，不知道如何描述这一点：

或者

这两个示例中的左上角 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

score 2 · Accepted Answer

使用下面提到的步骤进行分配：

如果一行只有一个 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 xx _ 1), (1 1 x 1 1), (1 xx 1 _)

完成分配后的矩阵看起来像上面显示的矩阵

现在按照上面提到的 5 个步骤来获得覆盖所有 0 的最小行数

勾选第 3 行，因为它尚未分配
由于第 3 行第 2 列中有 0，请勾选第 2 列
由于第 2 列在第 1 行有分配，请勾选第 1 行
现在通过未勾选的行（即第 0、2、4 行）和勾选的列（即第 2 列）画线
这 4 行将覆盖所有的 0

希望这可以帮助：）

PS：对于由于每行和每列中有多个 0 而无法进行初始赋值的情况，可以通过任意赋值来处理（对于每行和每列中存在多个 0 的情况，很可能更多比一个可能的分配会产生一个最佳解决方案）

score 0 · Accepted Answer

@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)

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

6 回答 6

Related

Reference