LAP#

在 NVIDIA CUDA 显卡上实现匈牙利算法的 O(n^3) 交替树变体。

此实现解决了一批共 k 个线性分配问题 (LAP)，每个问题具有 nxn 的单精度浮点成本值矩阵。在最优条件下，该算法会产生具有最低成本的分配。

该 API 可用于查询批处理中每个子问题的最优原始成本和对偶成本、最优分配向量以及最优行/列对偶向量。

cuGraph 公开了匈牙利算法，实际实现包含在 RAFT 库中，该库包含 cuGraph 和 cuML 之间共享的一些常用工具和内核。

以下参数可用于调整算法性能

  1. epsilon: (在 raft/lap/lap_kernels.cuh 中) 此参数控制浮点精度容差。将其设置得过小将导致求解时间增加，因为算法会寻找精确解。将其设置得过高可能会导致一些不准确性。

  2. BLOCKDIMX, BLOCKDIMY: (在 raft/lap/lap_functions.cuh 中) 这些参数控制沿给定维度使用的 threads_per_block。根据设备规格和占用率计算设置这些参数。

此库根据 Apache License 2.0 获得许可。如果此库对您的研究有帮助，请引用我们的论文。

  • Harvard 引用样式

    Date, K. and Nagi, R., 2016. GPU-accelerated Hungarian algorithms for the Linear Assignment Problem. Parallel Computing, 57, pp.52-72.

  • 要在 LaTeX 参考文献文件中使用的 BibTeX 引用块

@article{date2016gpu,
  title={GPU-accelerated Hungarian algorithms for the Linear Assignment Problem},
  author={Date, Ketan and Nagi, Rakesh},
  journal={Parallel Computing},
  volume={57},
  pages={52--72},
  year={2016},
  publisher={Elsevier}
}

该论文可在 ScienceDirect 上在线获取。

本页