域描述

结合子目录包含将不同的数据(包括多个观测数据)联系在一起的包，以便提高观测的准确性或为现有的观测提供新的维度或见解。

中心页面

• hungarian_assigner

hungarian_assigner

目的/用例

我们需要一种将不同数据关联在一起的方法。

这可以包括多个观察，但主要用例是将观察与跟踪相关联，即跟踪对象。

选择匈牙利算法而不是全球最近邻 (GNN) 算法，因为 GNN 算法假设欧几里得成本函数，而匈牙利算法可以采用任意成本。

这里的主要权衡是匈牙利算法是 O(N^3) 而不是 GNN 的 O(N log N)。

设计

这个包是 O(N^3 ) 匈牙利算法的一个相当标准的实现（见外部链接），但是我们在簿记方面做了一些小的改动以节省一些工作：

• 权重可以并且应该并行设置，其中线程拥有整行的所有权
• 任何特定的分配都应该只设置一次权重（或至少为后续的设置操作减少权重）。 这使我们可以知道连续的最小重量
• 所有循环都是有界的，这增加了一些计算工作以换取严格的运行时
• 每个外循环仅发现一次未覆盖的行/列

此外，我们实现的匈牙利算法可以支持不平衡分配问题和丢失权重（即非法分配）。

矩阵

使用了矩阵类的以下功能：

• 固定大小的矩阵
• 索引到矩阵
• 矩阵/数组子块/段
• 对块的操作：赋值、加法、减法（就地）

假设/已知限制

• 通过模板参数固定最大容量，可以选择以下之一：
  • 16
  • 32
  • 64
  • 96
  • 128
  • 192
  • 256
• 假设用户在通过以下方式填充矩阵之前知道工人和任务（行和列）的数量 set_weight()
• 假设用户知道未分配的任务数
• 假设 set_weight() 对于给定的索引对只出现一次
• 用户必须设置行和列，使得列数 >= 行数
• 如果一行没有可能的分配和/​​或 assign() 失败并返回 false，则假定用户将需要检查 UNASSSIGNED 分配

输入/输出/API

基本用法：

输入：

• 问题大小
• 分配权重（+隐式不可能分配）

输出：

• 分配（从行映射到分配的列）
• 未分配的任务（哪些列是未分配的列）

错误检测和处理

通过命中循环边界来检测不可能的分配。 在某些情况下，我们还可以在进行计算之前检查是否不可能进行赋值（例如，如果一列完全为空）。

在上述情况下，完整的算法将运行，但 assign() 将返回 false。 这是向用户发出的信号，他们需要检查 get_assignment() 值的结果 UNASSIGNED

对于索引（例如 set_size() , set_weight() ），可能由于索引错误而引发异常。

对于某些内部循环，理论上应该保证某些条件（例如，增广路径的最大尺寸、循环的最大迭代次数等）。

如果不满足这些条件，就会抛出异常。

安全注意事项

由安全专家待定。

参考/外部链接

• 百度的 Apollo 参考实现
• 算法的散文描述
• 单元测试 1 的工作示例
• 单元测试 2 的工作示例

未来的扩展/未实现的部分

不适用

相关问题

• #1152：初始实施
• #1266：重构以删除特征依赖项
• #1337：支持部分分配
• ＃1394：删除多余的ment调用
• #1559：更新设计文档格式以匹配文档样式指南