匈牙利算法 (HungarianAlgorithm)

这个包包含匈牙利算法（也称为 Munkres 分配算法）的高效实现，它是计算二维矩形分配问题的最优解的方法。该算法的时间复杂度为 O(n^3)。它已被推广到适用于任意大小（不一定是正方形）以及具有正成本和负成本的成本矩阵。

有关该算法的历史和用途的更多信息，请参阅其维基百科页面。

近年来，匈牙利算法已被用于深度学习方法，例如 Facebook 的 DETR，并且在 Python 的 scipy 库中有一个广泛使用的实现。然而，迄今为止，尽管机器学习在 IOS 移动应用程序中的使用日益增长，但在 Swift 中仍然没有该方法（使用 Jonker-Volgenant 变体）的快速实现。这个包试图弥补这一点。

您可以通过修改您的 Package.swift 文件，将 HungarianAlgorithm 安装到本地 Swift 环境中。

import PackageDescription

 let package = Package(
    name: "YOUR_PROJECT_NAME",
    dependencies: [
        .package(
            url: "https://github.com/spencermyoung513/HungarianAlgorithm",
        )
    ],
    targets: [
        .target(
            name: "YOUR_PROJECT_NAME",
            dependencies: [
                .product(name: "HungarianAlgorithm", package: "hungarianalgorithm"),
            ])
    ]
)

要使用该算法，首先指定一个成本矩阵。该矩阵的 [i, j] 条目定义了将工人 i 分配给工作 j 的成本。必须使用高度优化的 LASwift package 中定义的约定来创建矩阵，如下所示：

let costMatrix = Matrix([
    Vector([1.0, 2.0, 3.0]),
    Vector([4.0, 5.0, 6.0]),
    Vector([7.0, 8.0, 12.0]),
])

接下来，只需使用具有定义的成本矩阵的 HungarianAlgorithm.findOptimalAssignment 方法。这将分别返回行索引和列索引，这些索引指示最佳分配 -- (rowIndices[0], columnIndices[0]) 是第一对，依此类推。

(rowIndices, columnIndices) = HungarianAlgorithm.findOptimalAssignment(costMatrix)

有关其他示例，请参阅 Tests/HungarianAlgorithmTests 中的单元测试。

要添加到此存储库，请创建一个分支，推送您的更改，并提交合并请求。我们将在合并前进行审核。

Spencer Young, spencermyoung513@gmail.com

此包可在 MIT 许可下无条件使用。 有关更多信息，请参见 LICENSE.md。