bghungar

Hungarian algorithm to solve the square assignment problem.
3.1K Downloads
Updated 20 Jan 2011

View License

"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
Created with R11
Compatible with any release
Platform Compatibility
Windows macOS Linux
Categories
Find more on Traveling Salesman (TSP) in Help Center and MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes
1.2.0.0

this is a major new release:
see also the author's comments at the MathWorks file-exchange page.

1.1.0.0

#0 Added the line:
The <em>i-th row</em> is matched to the <em>iz(i)-th column </em>.
into the Description

See also the author's note from January 17th 2011, in the reviews' section.

1.0.0.0

This is a substantially changed version.
No more inf. loops with infeasible problems.
Note the slight change in calling syntax.
Thanks for the useful comments by reviewers.