匈牙利匹配算法

DeepSort中匈牙利匹配算法解决的是线性和分配问题，也称为二部图的最小权重匹配，针对的是有权图，不是简单的无权图。

1. 匈牙利匹配算法功能

输入：代价矩阵（有权图）
输出：行列不重复的最佳匹配

2. 匈牙利匹配算法过程

匈牙利算法由以下四个步骤组成。前两个步骤执行一次，而步骤 3 和 4 重复执行，直到找到最佳匹配。该算法的输入是一个 n * n 的代价矩阵，只有非负元素。

• 步骤 1：减去行最小值

​ 对于每行，找到最小的元素，然后从该行中的每个元素中减去它。

• 步骤 2：减去列最小值

​ 对于每列，找到最小的元素，然后从该列中的每个元素中减去它。

• 步骤 3：用最少的行列数覆盖所有零

​ 使用最少数量的水平线和垂直线覆盖结果矩阵中的所有零。

​ 如果需要 n 行，则零之间存在最优赋值。算法停止。

​ 如果需要的行数少于 n，请继续执行步骤 4。

• 步骤 4：创建其他零

​ 在步骤 3 中查找行未覆盖的最小元素（称为 k）。

​ 从所有未覆盖的元素中减去 k，并将 k 加到覆盖两次的所有元素中。

3. 匈牙利匹配算法示例

问题描述：四个工作（J1、J2、J3 和 J4）需要由四个辅助角色（W1、W2、W3 和 W4）执行，每个辅助角色做一个工作。下面的矩阵显示了将特定工作人员分配给特定工作的成本。目标是将分配的总成本降至最低。

下面我们将使用此示例解释匈牙利算法。

步骤 1：减去行最小值

我们从每行减去行的最小值开始。例如，第一行中的最小元素为 69。因此，我们从第一行中的每个元素中减去 69。…，依次生成的矩阵为：

步骤 2：减去列最小值

类似地，我们从每列中减去列的最小值，得到以下矩阵：

步骤 3：用最少的行数覆盖所有零

现在，我们将确定覆盖矩阵中所有零所需的最小行数（水平或垂直）。所有零都可以使用3行覆盖：

由于所需的行数 （3） 小于矩阵的大小 （n=4），因此我们继续执行步骤 4。

步骤 4：创建其他零

首先，我们发现最小的未覆盖数字是6。我们从所有未覆盖的元素中减去此数字，并将其添加到覆盖两次的所有元素中。这将生成以下矩阵：

现在我们返回到步骤 3。

步骤 3：用最少的行列数覆盖所有零

同样，我们确定覆盖矩阵中所有零所需的最小行数。现在需要 4 行：

由于所需的行数 （4） 等于矩阵的大小 （n=4），因此矩阵中的零之间存在最优赋值。因此，该算法停止。

最佳分配

以下零涵盖最佳分配：

这对应于原始成本矩阵中的以下最佳分配：

因此，工作人员 1 应执行工作 3，工作人员 2 应执行工作 2，工作人员 3 应执行工作 1，工作人员 4 应执行工作 4。此最佳分配的总成本为 69 + 37 + 11 + 23 = 140。

4. 匈牙利匹配算法代码

DeepSort中匈牙利匹配算法，即解决线性和分配问题或二部图的最小权重匹配，

在scipy.optimize.linear_sum_assignment中已封装实现，可以直接调包。

import numpy as np
from scipy.optimize import linear_sum_assignment as linear_assignment


cost_matrix = np.array([[82,83,69,92],
                        [77,37,49,92],
                        [11,69,5,86],
                        [8,9,98,23]])
row_indices, col_indices = linear_assignment(cost_matrix)
print(row_indices)
print(col_indices)
# [0 1 2 3]
# [2 1 0 3]
# 与手动推理完全一致

本文作者： 崔玉君
版权声明： 转载请注明出处！

Enjoy!

If you like TeXt, don’t forget to give me a star.