Description: "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, email@example.com.
Unlike latter code which is an adaptation from a 1980 ACM algorithm in Fortran IV, this is original code written directly according to , and specially for MATLAB (and very portable across different R's of MATLAB). It has only few, hence efficient lines.
dlT¬ help bghungar
BGHUNGAR "Hungarian algorithm" to solve the square assignment problem
C = a square profit/cost matrix.
[izSol, ifail, D] = bghungar(C);
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) 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.
Related: Adaptation, across different, adapted, Algorithm, acm algorithm, according to, Notes, 63 3d, 720 for, algorithm subsection, Approach, annotated, provided, assignment maximizes, and very, specially
O/S:BSD, Linux, Solaris, Mac OS X
File Size: 10.0 KB