matchpairs function in r2019a
显示 更早的评论
I used matchpairs function to solve linear assignment problem but was wondering which algorithm it implemented and the time complexity. Is it Hungarian?
Thank you
采纳的回答
Christine Tobler
2019-5-2
0 个投票
The algorithm solves the same problem as the Hungarian algorithm, but it's not the same algorithm. The Hungarian algorithm has complexity O(N^4), while the algorithm used here has complexity O(N^3*log(N)) for dense matrices, and O(nnz*N*log(N)) for sparse matrices.
These are worst-case complexities, for many matrices the performance will be better, as simple cases are treated in a preprocessing step.
If you type 'edit matchpairs', there is a reference to a paper describing the algorithm used in that file.
3 个评论
Lingyao Meng
2019-5-2
Steven Lord
2019-5-2
The paper is also listed in the References section of the documentation page for matchpairs. That way you avoid the chance of accidentally modifying matchpairs.m.
Mingxing
2021-10-8
Thanks for your answer. I checked the algorithm file of 'matchpairs' and I found that there is a 'matlab.internal.graph.perfectMatching' function to perform matching (no further explainations). I am wondering what exactly it is.
And I also checked the reference paper, the paper actually gave several algorithms.
更多回答（0 个）
类别
在 帮助中心 和 File Exchange 中查找有关 Creating and Concatenating Matrices 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
