bghungar
"Hungarian algorithm" to solve the square assignment problem (original & pure MATLAB implementation). The Hungarian algorithm can also be used as a sub-solver in a B&B solver for the travelling salesman problem.
How to match N (e.g. N=6) pairs of signals from 2 experiments? Build full reordering lists based on the PERMS(1:N) MATLAB function? But the complexity of this approach would be N! = prod(1:6) = 720 for a single run! That of the Hungarian algorithm is just N^3 = 6^3 = 216
i.e. it is many times more efficient!
This code is similar in purpose to the central part of assignprob: hungarian.m, v1.0 96-06-14, adapted by Niclas Borlin, niclas@cs.umu.se.
Unlike latter code which is an adaptation from a 1980 ACM algorithm in Fortran IV, this is original code written directly according to [1], and specially for MATLAB (and very portable across different R's of MATLAB). It has only few, hence efficient lines.
» help bghungar
BGHUNGAR "Hungarian algorithm" to solve the square assignment problem
========
For:
--------
C = a square profit/cost matrix.
the call:
--------
[izSol, ifail, D] = bghungar(C);
Returns:
--------
izSol = the optimal assignment: MAXIMIZES total profit
ifail = 0: success;
> 0: various failure triggers, according to the algorithm's sub-section
D = the square matrix equivalent to C at the end of iteration [1]
========
*** Notes:
1) For assignments that MINIMIZE cost, just invert
the sign of the cost matrix:
... = bghungar(-C);
2) Coding decisions are annotated, and debugging commands are provided
(just remove the comments) to resolve intricate use cases.
Cite As
Nedialko I. Krouchev (2024). bghungar (https://www.mathworks.com/matlabcentral/fileexchange/2795-bghungar), MATLAB Central File Exchange. Retrieved .
MATLAB Release Compatibility
Platform Compatibility
Windows macOS LinuxCategories
Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.
Version | Published | Release Notes | |
---|---|---|---|
1.2.0.0 | this is a major new release:
|
||
1.1.0.0 | #0 Added the line:
See also the author's note from January 17th 2011, in the reviews' section. |
||
1.0.0.0 | This is a substantially changed version.
|