# bghungar

Version 1.2.0.0 (3.79 KB) by
Hungarian algorithm to solve the square assignment problem.
Updated 20 Jan 2011

"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.