匈牙利算法实现（from scipy.optimize import linear_sum_assignment）

linear_sum_assignment 是 SciPy 库中 scipy.optimize 模块提供的一个函数，专门用于解决线性分配问题，也被称为匈牙利算法。这个问题通常出现在任务分配中，例如将一组工人分配给一组任务，以最小化总成本或最大化总收益。

代码解释

from scipy.optimize import linear_sum_assignment

这行代码导入了 linear_sum_assignment 函数。

什么是线性分配问题？

假设有一个矩阵 cost_matrix，其中 cost_matrix[i, j] 表示将第 i 个工人分配给第 j 个任务的成本（或收益的负值）。目标是找到一种分配方式，使得所有工人的总分配成本最小。

示例

假设有以下成本矩阵：

import numpy as np
from scipy.optimize import linear_sum_assignment

cost_matrix = np.array([
    [4, 2, 8],
    [2, 3, 7],
    [3, 6, 9]
])

row_ind, col_ind = linear_sum_assignment(cost_matrix)

如何使用 linear_sum_assignment？

1. 输入：linear_sum_assignment(cost_matrix) 函数的输入是一个二维数组或矩阵 cost_matrix，其中每个元素表示将某个任务分配给某个工人的成本。

2. 输出：该函数返回两个数组 row_ind 和 col_ind，分别表示最优分配中行和列的索引。例如，在上面的代码中，row_ind 对应于工人，col_ind 对应于任务。

结果说明

如果你打印出 row_ind 和 col_ind，你会得到：

print(row_ind)  # [0 1 2]
print(col_ind)  # [1 0 2]

这意味着：

• 第 0 个工人应被分配给第 1 个任务。
• 第 1 个工人应被分配给第 0 个任务。
• 第 2 个工人应被分配给第 2 个任务。

这是一种最小化总成本的分配方式。

总结

linear_sum_assignment 是解决任务分配优化问题的一个强大工具，特别适用于需要在二维代价矩阵中找到最低成本的分配方案的场景。