匈牙利算法:寻找最小行数来覆盖零？
我正在尝试实现匈牙利算法，但我被困在了步骤5上。基本上，给定一个数字的n X n矩阵，如何才能找到vertical+horizontal行的最小数目，使矩阵中的零被覆盖？
在有人将这个问题标记为 这的副本之前，这里提到的解决方案是不正确的，而其他人则是 在那里发布的代码中也遇到了错误。。
我不是在找代码，而是我可以画这些线的概念.
编辑:请不要发布简单(但错误)的贪婪算法:给定以下输入：
(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)回答 6
Stack Overflow用户
发布于 2014-05-02 07:55:47
更新
我在您发布的链接匈牙利算法提供的相同步骤中实现了匈牙利算法
下面是带有注释的文件：Github
算法(改进贪心)用于步骤3: (此代码非常详细，有助于理解选择绘制直线的概念:水平与垂直。但是请注意，这一步代码在我的Github代码中得到了改进)
- 对于输入矩阵中的每个xy位置，垂直计算最大零点数，然后将结果存储在一个名为
m2的单独数组中。 - 在计算时，如果水平零点>垂直零点，则计算的数字将转换为负数。(只是为了区分我们选择了哪个方向供以后使用)
- 循环遍历
m2数组中的所有元素。如果值为正，则在数组m3中画一条垂直线，如果值为负值，则在m3中绘制一条水平线。
按照下面的示例+代码来理解更多的算法：
创建3个数组：
- m1:第一个数组，保存输入值
- m2:第二个数组，在每个x，y位置保存maxZeroes(垂直的，水平的)
- m3:第三个数组，保存最后一行(未发现0索引，覆盖了1个索引)
创建两个函数：
- 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:您所指向的示例永远不会发生，因为正如您所看到的，第一个循环通过取最大值(水平、垂直)并将它们保存在m2中来完成计算。因此不会选择col1，因为-3表示绘制水平线，而-3是通过取水平与垂直零点之间的最大值来计算的。因此，在元素的第一次迭代中，程序检查了如何绘制线条，在第二次迭代中，程序绘制了线条。
Stack Overflow用户
发布于 2015-04-29 01:17:40
贪婪的算法在某些情况下可能行不通。
首先，可以将问题重新表述如下:给定二分图，找到一个最小顶点覆盖。在这个问题中，有2n个节点，n表示行，n表示列。如果对应列和行的交点处的元素为零，则两个节点之间有一个边。顶点覆盖是一组节点(行和列)，这样每个边都会从该集合中转移到某个节点(每个零被行或列覆盖)。
这是一个众所周知的问题，可以在O(n^3)中找到一个最大匹配来解决。查看维基百科以获取详细信息
Stack Overflow用户
发布于 2015-01-02 23:50:39
在一些情况下，埃米尔的代码失败了。
考虑以下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次迭代，我想这些情况中的大多数只需要两次迭代，除非有一组嵌套在领带中的绑定。我试着想出一个，但它变得很难管理。
可悲的是，这还不够好，因为会有一些案件将永远被捆绑在一起。特别是在有一组“不相交的捆绑细胞”的情况下。除了画出以下两个例子之外，不知道如何描述这一点：
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行/cols。唯一新添加的零是新行和新列交叉的位置。为了清晰的描述。
用我描述的迭代方法，这些矩阵将被捕获在一个无限循环中。零将始终保持平局(计算数与行数)。在这一点上，在领带的情况下任意选择一个方向是有意义的，至少从我所能想象的角度来看是这样的。
我遇到的唯一问题是设置循环的停止条件。我不能假设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);
endhttps://stackoverflow.com/questions/23379660
复制相似问题
腾讯云开发者
