多目标跟踪中用到的求解线性分配问题(Linear Assignment Problem,LAP)C++
flyfish
python实现,说的比这里详细
lapjv.h和lapjv.cpp代码在https://github.com/shaoshengsong/DeepSORT
C++代码调用
#include <iostream>
#include <vector>
#include "lapjv.h"// 打印分配结果
void print_assignment(const std::vector<std::vector<int>>& cost_matrix, const std::vector<int>& assignment) {int n = cost_matrix.size();std::cout << "Custom LAPJV Assignment:" << std::endl;for (int i = 0; i < n; ++i) {std::cout << "Worker " << i + 1 << " is assigned to Job " << assignment[i] + 1 << std::endl;}
}int main() {// 成本矩阵std::vector<std::vector<int>> cost_matrix = {{9, 11, 14, 11, 7},{6, 15, 13, 13, 10},{12, 13, 6, 8, 8},{11, 9, 10, 12, 9},{7, 12, 14, 10, 14}};// 将成本矩阵转换为cost_t类型的矩阵int n = cost_matrix.size();std::vector<std::vector<cost_t>> cost_matrix_cost_t(n, std::vector<cost_t>(n));for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {cost_matrix_cost_t[i][j] = static_cast<cost_t>(cost_matrix[i][j]);}}// 将成本矩阵转化为指针数组以适应lapjv函数std::vector<cost_t*> cost_matrix_ptrs(n);for (int i = 0; i < n; ++i) {cost_matrix_ptrs[i] = cost_matrix_cost_t[i].data();}// 调用lapjv_internal函数解决线性分配问题std::vector<int_t> x(n), y(n);lapjv_internal(n, cost_matrix_ptrs.data(), x.data(), y.data());// 打印分配结果print_assignment(cost_matrix, x);return 0;
}
Custom LAPJV Assignment:
Worker 1 is assigned to Job 5
Worker 2 is assigned to Job 1
Worker 3 is assigned to Job 3
Worker 4 is assigned to Job 2
Worker 5 is assigned to Job 4