匈牙利算法 - 维基百科方法不适用于此示例

Question

我正在尝试用 C 实现匈牙利算法。

我有矩阵：

35  0  0  0
 0 30  0  5
55  5  0 10
 0 45 30 45

我已经到了必须找到覆盖所有零的最少行数的阶段（尽可能多地分配）。显然，通过检查这是第 1 列和第 3 列以及第 1 行。

Wikipedia suggests the following method:

第 1 行有三个零：选择任意一个（我选择第一个）并分配它
第 2 行：分配第一个零
第 3 行：分配第三个零
第 4 行未分配（因为唯一的零位于已经分配了零的列中）

如果我按照上面的矩阵进行操作，我会得到：

35   0'  0   0
 0' 30   0   5
55   5   0' 10
 0  45  30  45

其中零素数是指定的零。然后，按照维基百科下面的说明，我标记第 4 行（未分配的零）、第 1 列（带有未分配的零的列），然后是第 2 行（标记列中带有零的行）。

因此这表明达到全零的最小行是：

+--------
|
+--------
|

但这并没有在 (2, 3) 处达到零。相关C代码：

for (i = 0; i < M->size; i++) {
    for (j = 0; j < M->size; j++) {
        if (M->values[i][j] == 0) {
            if (assigned_cols[j] == 0) {
                assigned_cols[j] = 1; // We've assigned something in this col
                assigned_rows[i] = 1; // We've assigned something in this row.
                marked_rows[i] = 0;
                total--;
                break; // Go to the next row
            } else {
                marked_cols[j] = 1; // Then there exists a zero in this col in an unassigned row
                mark_col(M, j); // marks all elements in column j
                total++;
            }
        }
    }
}

此代码选择哪些零是零素数（分配零）。

然后此代码标记在新标记的列中具有分配的所有行：

 for (i = 0; i < M->size; i++) {
    if (marked_cols[i] == 1) {
        for (j = 0; j < M->size; j++) {
        //iterating through rows
            if (M->values[j][i] == 0) {
                // then (j,i) is a zero in a marked col
                // mark the row
                if (marked_rows[j] != 1) {
                    total++;
                    marked_rows[j] = 1;
                }
                break; // no need to continue more
            }
        }
    }
}

但是这个（以及维基百科的解释）对于我上面的矩阵来说是失败的。怎么会？

Answer 1

维基百科对算法缺少解释，作业将在最后一步完成！

第 0 步

35  0  0  0
 0 30  0  5
55  5  0 10
 0 45 30 45

第 1-2 步所有行-列至少有一个 0 所以第 1 步让数组保持不变

35  0  0  0
 0 30  0  5
55  5  0 10
 0 45 30 45

第 3 步
必须通过标记尽可能少的行 and/or 列

来覆盖矩阵中的所有零

- - - -
|   |
|   |
|   |

请注意，到目前为止还没有完成作业，您需要完成 all zeros。您的封面未覆盖零 (2,3) 个！！

现在取未覆盖的最小元素，例如 5（取位置 (2,4) 处的 5）

-减少（5）所有未覆盖的元素。
- 增加（5）两条线交叉的所有元素。
-其余保持不变
所以数组：

40  0  5  0
 0 25  0  0
55  0  0  5
 0 40 30 40

现在再次检查所需的最少行数：现在您需要 4 行（等于数组行的大小 n=4，所以我们停止）。

最后的作业：从只有一个零的行开始，这肯定会被分配：

40  0  5  _
 0 25  _  0
55  _  0  5
 _ 40 30 40

存在多个赋值（我用_赋值）。

更具体地说，我们得到了两个任务：（上面提到的一个总成本为 5）和：

40  _  5  0
 0 25  0  _
55  0  _  5
 _ 40 30 40

还有5块钱！

编辑

根据评论，我似乎没有得到 op 要求的确切部分，所以我将回答这个特定部分，保留上面算法的一般描述。

错误（由于错误的维基百科描述）在这里：

Where zero prime is the assigned zero. Then, following Wikipedia's instructions below, I mark row 4 (unassigned zero), column 1 (col with the unassigned zero), then row 2 (row with a zero in a marked col).

到现在为止完全同意但是...还没有完成！！！

When correctly marking row2 you need to go to step 2 (of Wikipedia) and check again for columns with zeros in this case column 3 should also been marked, this also causes the row 3 to be marked as well (due to assigned zero in the newly marked column 3) and there you stop (no other rows or columns should be marked)!!

总的来说，标记的列和行：

 +       +
35   0'  0   0
 0' 30   0   5  +
55   5   0' 10  +
 0  45  30  45  +

以及通过选择标记的列和未标记的行得到的行：

- - - -
|   |
|   |
|   |

这是答案第一部分中描述的正确答案，并会在下一阶段产生正确的结果（也在上面解释过）。

可以在 mathstackexchange:

上找到一个非常相似的 post

finding the minimum number of lines to cover all zeros in an assignment probem

匈牙利算法 - 维基百科方法不适用于此示例

Hungarian Algorithm - Wikipedia method doesn't work for this example

c

algorithm

hungarian-algorithm

编辑