多假设跟踪中的高效匈牙利算法研究

赵伟康; 韩一娜; 张浩宇; 杨益新; 刘清宇

doi:10.11993/j.issn.2096-3920.2018.05.011

多假设跟踪中的高效匈牙利算法研究

doi: 10.11993/j.issn.2096-3920.2018.05.011

1.
西北工业大学航海学院, 陕西西安, 710072
2.
海军研究院, 北京, 100073

基金项目: 国家重点研发计划(2016YFC1400200); 国家自然科学基金面上项目(61671388)

详细信息

作者简介:
赵伟康(1995-), 男, 在读硕士, 主要研究融合跟踪算法。

中图分类号: TJ67; O224
计量
- 文章访问数: 677
- HTML全文浏览量: 1
- PDF下载量: 910
- 被引次数: 0
出版历程
- 收稿日期: 2016-11-19
- 修回日期: 2016-12-18
- 刊出日期: 2018-10-31

An Improved Hungarian Algorithm for Multiple Hypothesis Tracking

1.
School of Marine and Technology, Northwestern Polytechnical University, Xi’an 710072, China
2.
Naval Research Academy, Beijing 100073, China

摘要

摘要: 作为多假设跟踪技术中的一项核心算法, 匈牙利算法占用了多假设跟踪中大部分的运算时间。考虑到多假设跟踪中的指派问题具有其特殊性, 即其效率矩阵是稀疏的, 文中提出了一种对效率矩阵进行降维的处理方法, 给出了运算流程, 对比了该方法与传统匈牙利算法在处理较大效率矩阵时的耗时, 结果表明, 在确保与传统匈牙利算法结果一致的前提下, 该方法能够大幅度降低运算量。
- 多假设跟踪 /
- 匈牙利算法 /
- 指派问题
Abstract: Hungarian algorithm is a core algorithm in multiple hypothesis tracking technology, and it takes up most of the computation time in multiple hypothesis tracking(MHT). Considering that the assignment problem in the MHT has particularity, i.e., the efficiency matrix is sparse, this paper proposes a method for reducing the dimension of the efficiency matrix, and the computation flow is given. Comparison of the time consumption between the proposed method and traditional Hungarian algorithm in dealing with larger efficiency matrix shows that the proposed method greatly reduces the amount of computation while ensuring consistency with the results of the Hungarian algorithm.
- multiple hypothesis tracking(MHT) /
- Hungarian algorithm /
- assignment problem

HTML全文

参考文献(10)

[1]	翟海涛. 多假设跟踪算法研究及其应用[J]. 信息化研究. 2010, 36(8): 25-27. Zhai Hai-tao. Reseach on Multiple Hypothesis Tracking Algorithm and Its Application[J]. Informatization Research, 2010, 36(8): 25-27.
[2]	Murty K G. An Algorithm for Ranking All the Assignments in Order of Increasing of Cost[J]. Operations Research, 1968, 16: 682-687.
[3]	Miller M L, Stone H S, Cox I J. Optimi¬z¬i¬n¬g Murty’s Ranked Assignment Method[J]. NEC Research Institute, Technical Report, 1997, 33(3): 851-862.
[4]	钱颂迪. 运筹学[M]. 北京: 清华大学出版社, 1998.
[5]	Chin-Jung Huang. Integrate the Hungarian Method and Genetic Algorithm to Solve the Shortest Distance Prob-lem[C]//2012 Third International Conference on Digital Manufacturi¬ng & Automation. Guilin, China: IEEE, 2012: 496-499.
[6]	Patel R R, Desai T T, Patel S J. Scheduling of Jobs based on Hungarian Method in Cloud Computing[C]//2017 International Conference on Inventive Communication and Computational Technologies(ICI¬C-C¬T). Coimbatore, India: IEEE, 2017: 6-9.
[7]	Yan Chao-bo, Zhao Qian-chuan. Advances in Assignment Problem and Comparison of Algorithns[C]//27th Chinese Control Conference. Kunming, China: IEEE, 2008: 607-611.
[8]	张新辉. 任务多于人数的指派问题[J]. 运筹与管理. 1997, 6(3): 20-25. Zhang Xin-hui. Assignment Problem with Tasks More than the Number of Persons[J]. Operations Research and Manage- ment Science, 1997, 6(3): 20-25.
[9]	李延鹏, 钱彦岭, 李岳. 基于改进匈牙利算法的多技能人员调度方案[J]. 国防科技大学学报, 2016, 38(2): 144-149. Li Yan-peng, Qian Yan-ling, Li Yue. Multi-skilled Labor Allocating Method Based on Improved Hungary Algorithm[J]. Journal of National University of Defense Technology, 2016, 38(2): 144-149.
[10]	马晓娜.“人少任务多”型指派问题的一种新算法[J]. 重庆工商大学学报(自然科学版), 2014, 31(12): 68-75. Ma Xiao-na. A New Algorithm for Assignment Problems with “Tasks More Than the Number of Persons”[J]. Journal of Chongqing Technology and Business University: Natural Science Edition, 2014, 31(12): 68-75.