📄 assignment.html
字号:
<html>
<body>
<h2><font color="#000080">
ALGORITHMS FOR THE ASSIGNMENT PROBLEM
</font></h2>
<h3><font color="#000080">
Introduction
</font></h3>
With this package, I provide some MATLAB-functions regarding the
rectangular assignment problem. This problem appears for example in
tracking applications, where one has M existing tracks and N new
measurements. For each possible assignment, a cost or distance is computed.
All cost values form a matrix, where the row index corresponds to the
tracks and the column index corresponds to the measurements. The provided
functions return an optimal or suboptimal assignment - in the sense of
minimum overall costs - for the given matrix.<br><br>
In the process of gating, typically very unlikely assignments are
forbidden. The given functions can handle forbidden assignments, which are
marked by setting the corresponding assignment cost to infinity.<br><br>
The optimal solution is computed using Munkres algorithm, also known as
Hungarian Algorithm.<br><br>
<h3><font color="#000080">
Functions contained in this package
</font></h3>
<b><font color="#000080">
assignmentallpossible.m
</font></b><br>
Computes the optimal assignment by recursively stepping over all possible
assignment vectors. Used for reference computation.<br><br>
<b><font color="#000080">
assignmentoptimal.m and assignmentoptimal.c
</font></b><br>
Computes the optimal assignment (minimum overall costs) using Munkres algorithm.<br><br>
<b><font color="#000080">
assignmentsuboptimal1.m and assignmentsuboptimal2.c
</font></b><br>
Computes a suboptimal solution. Good for cases with many forbidden assignments.<br><br>
<b><font color="#000080">
assignmentsuboptimal1.m and assignmentsuboptimal2.c
</font></b><br>
Computes a suboptimal solution. Good for cases without forbidden assignments.<br><br>
<b><font color="#000080">
testassign.m
</font></b><br>
Compares the algorithms regarding performance and optimality of solutions.<br><br>
<h3><font color="#000080">
Usage
</font></h3>
The first four functions are called like the following:<br><br>
<font face="Courier New">[assignment, cost] = assignment_xx(distMatrix);</font><br><br>
(Replace "_xx" by "optimal", for example). Type "help assignment_xx" for more hints to the
different algorithms.<br><br>
Take care that all costs/distances are positive or zero!<br><br>
<h3><font color="#000080">
How to use mex-files
</font></h3>
The C language source files are so-called mex-files for MATLAB. You should be able to compile
these functions manually on all systems by typing<br><br>
<font face="Courier New">mex assignmentoptimal.c</font><br>
<font face="Courier New">mex assignmentsuboptimal1.c</font><br>
<font face="Courier New">mex assignmentsuboptimal2.c</font><br><br>
in MATLAB. If you have never used the mex-command before, you first have to
select a compiler. I suggest to use one of the built-in compilers that
come with Matlab.<br><br>
The mex-command creates a file with a system-dependent extension, in Windows it is <font face="Courier New">.mexw32</font>. As
soon as this file in generated, you can use it as you would call a MATLAB function. When both
mex- and m-file of the same name are on the MATLAB path, the mex-file is chosen.<br><br>
The mex-files can save computation time up to a factor of 10 or 20. Use the test functions
testassignment.m with your own preferences and have a look at the profiler output. <br><br>
By the way, you will find that in some cases the mex-implementations of the suboptimal
algorithms need a longer computation time than the optimal algorithm. The functions are much
faster than the MATLAB-implementations, but they can still be improved (If you do, please let
me know).<br><br>
<h3><font color="#000080">
Using the functions from C
</font></h3>
The mex-files always contain a function called "mexFunction" that is needed for MATLAB and
a function called "assignment_xx". You can use the second if you want to apply the algorithms
directly from C. If you do not have MATLAB installed, you have to replace the mx-functions
(e.g. mxCalloc) by ordinary C-functions and delete the two include lines.<br><br>
If you decide to use the functions in C, you might need the column indices to start from 0,
not from 1 as in MATLAB. Just delete the definition of ONE_INDEXING and you are done. If you
do not need to handle infinite values in your applications, also delete the definition of
CHECK_FOR_INF. <br><br>
Two more points to take care of when using C: The assignment vector is defined as a double
precision array, as MATLAB uses double precision values anyway. When referencing elements
with the computed assignment vector in C, you have to change all function declarations to use
integer values. Further, the distance or cost matrix of size MxN is defined as a double
precision array of N*M elements. Matrices are saved MATLAB-internally in row-order (i.e. the
matrix [1 2; 3 4] will be stored as a vector [1 3 2 4], NOT [1 2 3 4]).<br><br>
<h3><font color="#000080">
Problems
</font></h3>
I have not tested the functions on any other system than Windows with MATLAB 6.5.1. But as I do
not use any sophisticated functions or special toolboxes, I expect the functions to run on all
systems without problems. If you have problems anyway, feel free to contact me.<br><br>
If you find any bugs or errors, please give me the chance to correct them and drop me an
<a href="mailto:mb_matlab@gmx.de?subject=multicore">E-mail</a>.
<h3><font color="#000080">
Contact
</font></h3>
Dipl.-Ing. Markus Buehren<br>
Stuttgart, Germany<br>
<br>
<a href="mailto:mb_matlab@gmx.de?subject=assignment package">mb_matlab@gmx.de</a><br>
<a href="http://www.markusbuehren.de">http://www.markusbuehren.de</a><br>
<h3><font color="#000080">
Version
</font></h3>
Last modified 30.01.2008<br>
Latest version on <a href="http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=6543">Matlab Central</a>.
</body>
</html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -