莫队算法复杂度（莫队算法是谁发明的）



一 简介

二 计算代价矩阵

以工作分配为例，计算代价矩阵。

假设现在有甲乙丙三个人，面对ABC三项工作。

例如甲做ABC工作的耗时分别为1时2时3时，那么第一行可以写为（1，2，3），若乙做ABC工作的耗时分别为2时4时6时，那么第二行可以写为（2，4，6），以此类推。

在本文中，将以（1，2，3），（2，4，6），（3，6，9）为例来进行求解。

三 求解具体步骤

Step 0

构建代价矩阵 costmatrix。

其可以为相邻帧中不同目标间的距离；又或者任务分配问题中，每个人做每个任务的耗时。

Step 1

每行减去该行的最小值。

to step 2

Step 2

遍历 costmatrix，找到结果中的0。

if 其所在的行列中均没有标记为1的0

将其标记为1。

to step 3

Step 3

if 某列包含标记为1的0

划掉该列

if 所有的列都被划掉了

to Done

else

to step 4

Step 4

找到没被划掉的0并将其标记为2。

if 这个被标记了2的 0(4_1)，其所在的行中没有标记为1的0

to step 5

else

划掉0(4_1)所在的行，找到 0(4_1)所在的行中那个被标记为1的0，取消划掉1所在的列。

重复操作，直到所有0都被划掉。

保留没被划掉的值中的最小值 valve_min。

to step 6

Step 5

构建如下点集：

将第4步中被标记为2的0，记为Z0。

将Z0所在的列中，被记为1的0，记为Z1。

将Z1所在的行中，被标记了2的0，记为Z2。

重复上述步骤，直到被标记为2的0其所在的列中，没有被标记为1的0。

将点集中所有被标记为1的0取消标记，将标记为2的0标记为1。

擦除所有被记为2的0，并将所有被划掉的行和列取消划除。

to step 3

Step 6

将所有被划掉的行中的元素都加上 valve_min（find in step 4）

将所有没被划掉的列中的元素都减去 valve_min。

to step 4

四 步骤图示

五 代码

六 总结

以上已经讲解了代价矩阵的构建方法和匈牙利解的求解方法，那么其和目标匹配存在怎样的关系。

其实只要计算相邻帧间目标的代价，然后使用上述的求解方法进行计算就可以了。

例如第1帧中有三个目标T1i (i = 1,2,3)，第2帧中有三个目标T2i (i = 1,2,3)。

那么他们之间的匹配关系如何，可以根据不同的方案计算代价矩阵求解。

例如，你可以选择第1帧和第2帧中目标的几何距离来作为代价。

分别计算T11和T21，T22，T23的几何距离获得矩阵的第一行，计算T12和T21，T22，T23的几何距离获得矩阵的第二行，以此类推构建代价矩阵。

除了距离信息之外，还可以考虑类别信息和航向信息等作为补充。

例如，两个目标间的航向差别大到超过某个阈值，代价值增加一定的量；两个目标间的类别不相同，代价增加一定的量，甚至如果你确信感知结果正确，也可以直接把类别不同的目标的代价值置为无穷大。

最后，求解构建的代价矩阵，就能获得综合考虑了类别，距离，航迹的全局最优匹配结果啦。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/25261.html