来源于并修改自 这个出色的解释。

使用方法

将以下内容添加到您的 Cargo.toml 文件中

[dependencies]
hungarian = "1.1.1"

将以下内容添加到您的二进制文件或库的顶部

extern crate hungarian;

use hungarian::minimize;

然后您就可以开始使用了！ 更多信息请参阅文档。

近期更改

• 1.1.1
  • 版本号增加，以便在 crates.io 上显示 pathfinding 重定向。
• 1.1.0
  • 性能大幅优化（在5x5到100x100矩阵的基准测试中提高了2-4倍）
  • 现在使用 num-trait 来处理泛型整数权重
  • 现在由 ndarray 支持，以更好地处理更大的输入
• 1.0.0
  • 源代码文档得到大幅改进
  • 将 hungarian 函数重命名为 minimize
  • 现在可以处理任意矩形矩阵
  • 添加了更多测试用例以覆盖非正方形矩阵
  • 现在返回 Vec<Option<Usize>> 来处理不是所有列都被分配给行的情况
• 0.1.0
  • 初始发布
  • 基础算法正在工作，但仅适用于正方形矩阵。
  • 文档不足

备注

为了避免在多个文件和辅助函数中重复拆分逻辑，我尝试将上述解释简化并压缩成一个单一、简单的函数，同时保持其正确性。在网上搜索了多个测试用例后，我相当自信我的实现是正确的，尽管最终的结果看起来相当不同。

如果您发现任何错误，请告诉我！

性能

使用 Criterion.rs 获得了以下两种类型的成本矩阵的基准测试结果：

     Worst Case           |       Generic Case
                          |
   -------------          |       -------------
   | 1 | 2 | 3 | ...      |       | 1 | 2 | 3 |
   -------------          |       -------------
   | 2 | 4 | 6 | ...      |       | 4 | 5 | 6 |
   -------------          |       -------------
   | 3 | 6 | 9 | ...      |       | 7 | 8 | 9 |
   -------------          |       -------------
     .   .   .            |
     .   .   .            |
     .   .   .            |
                          |
C(i, j) = (i + 1)(j + 1)  |  C(i, j) = (i * width) + j

基准测试结果

在四核 2.6GHz Intel(R) i7-6700HQ 处理器和 16GB RAM 的系统上测量；使用 Ubuntu 16.04 Linux x86_64 4.8.0-53-generic